Invitation to Bug Game [marathon problem, mirror of buglab.ru]

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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:

$$$17\cdot 10^9$$$ — sas4eka;
$$$14\cdot 10^9$$$ — I_love_natalia;
$$$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

############################### #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #.............................# #............................## #..........................#..# ###############################

Comments (24)

Write comment?

kekkule

19 months ago, # |

What is the reason of creating of this mirror?

→ Reply

dalex

19 months ago, # ^ |

← Rev. 2 →

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)).

dmkz

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.

I_love_natalia

found: 584479040

buglab 2 prepare your checker edition

whymihere

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

BallBreaker

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

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

###############################
#S............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#.............................#
#............................F#
###############################

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).

← Rev. 5 →

+16

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

java.lang.IllegalArgumentException: Argument points should be between -2000000.00001 and 2000000.00001.

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++.

_Crimson_

Good luck everyone!

bsn

+40

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.

Good news, thank you!

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

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

Got (+∞) points

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.

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.

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

It was tested on the tab custom test at the codeforces with compiler GNU G++20 11.2.0 (64 bit, winlibs) on my $$$239$$$ millions maze and has been finished in $$$1.2$$$ seconds:

239386428

=====
Used: 1248 ms, 0 KB

18 months ago, # ^ |

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.

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

NaOH_Frog

18 months ago, # |

+19

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

2147483648

-31

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

Oh, thank you! Don't come next time!

-26

Don't worry, I will definitely come next time!

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.

H-1

17 months ago, # |

nice problems

dmkz's blog