dmkz's blog

By dmkz, history, 11 months ago, In English

Hello Codeforces!

UPD. I_love_natalia crashed the checker by his maze with $$$10^9$$$ moves. The problem is resolved now and all of the solutions rejudged. Scoring is changed. More info

UPD 2: The official site https://buglab.ru/ was updated. See comment.

UPD 3: The checker has been speeded-up by mfv in $$$2.2$$$ times (in comparison with my checker. The new speed is equal to $$$4$$$ seconds for a $$$10^9$$$ moves in codeforces "Custom Invocation"). Current standings:

  1. $$$17\cdot 10^9$$$ — sas4eka;
  2. $$$14\cdot 10^9$$$ — I_love_natalia;
  3. $$$6.8 \cdot 10^9$$$ — maxplus (on the buglab: $$$11.3 \cdot 10^9$$$).

UPD 4: I updated the checker: now mazes up to $$$42$$$ billions are supported before checker got TL. Time limit of checker on codeforces platform is equal to $$$1$$$ minute. I submitted the maze with number of moves equal to $$$42.015.084.960$$$ and the result has been calculated in 59799 ms. Maybe someone can calculate the answer faster?

I'm happy to invite you to an unofficial mirror of Bug Game. In this game you need to generate a $$$21 \times 31$$$ maze with the maximum number of bug's moves to get out. The bug moves not optimally and you will see a description of algorithm of its movement in the statement of this problem. Based on given algorithm you will be able to create a maze and submit it.

Privacy: your solutions (your mazes) will be visible only for mfv.

Invitation link: click here

Date: April 18, 2023, 00:00 UTC+3

Duration: 2 weeks, then upsolving and virtual participation.

Scoring: if you will be able to generate the maze with $$$X$$$ moves to get out, then your solution will get $$$\frac{x}{10^5}$$$ points.

Official Russian site of Bug Game: click here

  • Vote: I like it
  • +76
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the reason of creating of this mirror?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I hope they have rewritten the checker and it can process 1 billion moves per second, not 1 million as on the original site.

    A score of several billions is more than real in this problem. Checker may TL. I would suggest to decrease size of the maze to lower scores and to make checker run faster (it is O(answer)).

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was not able to achieve 1 billion in 1 seconds. My checker can process 240 millions in 1.2 seconds. If someone can send to me faster checker, I can update the package at the polygon.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Input and Output will be explained in the problem statement right?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    i would also ask does we need to send labyrinth from . and #?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    BallBreaker, whymihere,

    Yes, but I can explain it here too.

    There is only one testcase. You need to print $$$21$$$ lines with $$$31$$$ chars in them. # is a wall, . is an empty cell. Start position is $$$(1,1)$$$ (in $$$0$$$-indexation), finish at $$$(19,29)$$$ (in $$$0$$$-indexation).

    Borders of maze must contain only walls. Start and finish cells must be empty. Your maze must contain a path from start to finish.

    Example of valid empty maze
    Example where is start and finish
    More difficult handmade maze with 416 steps
    More difficult handmade maze with 480 steps

    You can use PHP in submitting of your maze directly (without any code of printing, just copy-paste your maze, choose PHP and click submit).

»
11 months ago, # |
Rev. 5   Vote: I like it +16 Vote: I do not like it

I_love_natalia crashed the checker and got verdict Judgement failed. He built the maze with $$$1 \times 10^9$$$ steps and overflowed upper limit of codeforces points system.

Judgement failed message

UPD 2: When I tried to choose points in Polygon on the tab called "Tests", I saw a system message that points have to be less than $$$10^9$$$ and have at most $$$2$$$ digits after comma. So, the number $$$999999999.99$$$ is correct number of points in "Tests". This is why I divided by $$$100$$$. Then I added custom checker which was able to return score directly. Limitation for checker is $$$[-2000000.00001, 2000000.00001]$$$ on Codeforces site after adding the problem to mashup. Checker's testcase for a maze with out of Codeforces's range is passed on Polygon. I didn't have a $$$200$$$ million maze when tested the checker in Codeforces mashup.

Cf running system requires points to be $$$[-2000000.00001, 2000000.00001]$$$ with $$$5$$$ digits after decimal point.

And polygon requires points to be $$$[0,10^9]$$$ with 2 digits after decimal point.

I have decided to replace $$$\frac{x}{100}$$$ by $$$\frac{x}{10^5}$$$ for resolving this issue. At current time all of the submissions have been rejudged.

$$$10098.163$$$ means that I_love_natalia got $$$1.009.816.300$$$ steps.

$$$2393.864$$$ means that dmkz got $$$239.386.400$$$ steps.

UPD. I can say for my maze: it was achieved in $$$1$$$ week of trying some ideas and different approaches (started at 10th April, Monday) and auto-generated with my maze generator written in C++.

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Good luck everyone!

»
11 months ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

I modified the site https://buglab.ru so that it became possible to send mazes with a large number of bug moves. You can test your mazes there.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good news, thank you!

    I see also that number of participants has been reduced from $$$28\cdot 10^3$$$ to $$$1105$$$.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Yes, I decided not to display accounts with empty labyrinths in the rating. Many of them are robots.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got (+∞) points

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It is worth assuming that the decision with the result of 7,182,081,448 moves belongs to you. It was a good test for the site. The calculation of this value was obtained in 73 seconds. During this time, the result was displayed as +∞ (infinity). It's strange, but for some reason this solution has not been sent on this site so far, since at the moment the best solution has about 6.8 billion moves.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        It's strange, but for some reason this solution has not been sent on this site so far, since at the moment the best solution has about 6.8 billion moves

        fixed. I've got HTTP 503 problems when trying to submit CF gym solution yesterday.

        Also thanks a lot for the game, it is amazing.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is your server has the 64 bit architecture? My checker shows similar speed for 32 bit architecture, but for 64 bit it is $$$2\cdot 10^8$$$ per second. You can try this, maybe it can helpful on the site.

        How it is tested
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Today I submitted $$$45$$$ billions. How long such calculations take? For comparison, time limit of checker on codeforces platform is $$$60$$$ seconds and I got $$$42$$$ billions here (this is upsolving, the bottom of standings). $$$45$$$ billions is impossible to submit here now in a single submission.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The checker on the official site has been hanging for the last $$$8$$$ hours :(

    Got $$$572\cdot 10^6$$$ with a new idea and tried to submit

»
11 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Is there anyone who got e9 number of moves and is willing to provide your maze? I'm curious about the construction.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -31 Vote: I do not like it
    ###############################
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #.............................#
    #............................##
    #..........................#..#
    ###############################
    

    It takes more than $$$0.00000008e9$$$ moves to complete, I hope that's what you needed.

  • »
    »
    11 months ago, # ^ |
    Rev. 5   Vote: I like it +8 Vote: I do not like it

    This is constructive problem. I sent you my constructive pattern via codeforces messages with explanation of the main idea. Unfortunately, I don't have a constructive pattern which are used by top $$$3$$$ users. I sent my pattern to I_love_natalia and he said that there are at least $$$2$$$ problems in my pattern and I need to resolve them.

    UPD. Also he sent me optimal answers for smaller dimensions and said to achieve them firstly before start of constructing 21 x 31.

    UPD 2. Constructive algorithm written by I_love_natalia builds $$$10^9$$$ in $$$30$$$ minutes.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice problems