Приглашение в игру «Жук» [марафонская задача, зеркало buglab.ru]

Привет Codeforces!

UPD. I_love_natalia сломал чекер своим лабиринтом на $$$10^9$$$ ходов. Проблема сейчас решена и все решения перетестированы. Система оценивания изменена. Подробнее

UPD 2: Официальный сайт https://buglab.ru/ был обновлен. Обратите внимание на комментарий.

UPD 3: Чекер был ускорен mfv в $$$2.2$$$ раза (по сравнению с моей версией, бенчмарк: $$$4$$$ секунды на $$$1$$$ млрд шагов на вкладке "Запуск"). Текущие рекордсмены:

$$$17$$$ млрд — sas4eka;
$$$14$$$ млрд — I_love_natalia;
$$$6.8$$$ млрд — maxplus (на buglab: 11.3 млрд).

UPD 4: Я обновил чекер: теперь поддерживаются лабиринты вплоть до $$$42$$$ миллиардов шагов до того, как чекер получит вердикт TLE. Лимит на время выполнения чекера на codeforces равен $$$1$$$ минуте. Я отправил лабиринт с числом шагов равным $$$42.015.084.960$$$ и ответ был вычислен за 59799 мс. Может кто-нибудь может посчитать ответ быстрее?

Я с радостью приглашаю вас принять участие в неофициальном зеркале игры «Жук». В этой игре от вас требуется сгенерировать $$$21 \times 31$$$ лабиринт с максимальным количеством ходов жука до выхода из него. Жук перемещается не оптимально и вы сможете увидеть описание алгоритма его перемещения в условии задачи. Основываясь на данном алгоритме, вы сможете создать свой лабиринт и отправить его!

Приватность: ваши решения (ваши лабиринты) будут видны только mfv.

Ссылка-приглашение: нажми сюда

Дата начала: 18 апреля, 2023, 00:00 MSK

Длительность: 2 недели, а затем дорешивание и виртуальное участие.

Система оценивания: если сгенерированный вами лабиринт заставит жука сделать $$$X$$$ ходов до выхода, то ваше решение получит $$$\frac{x}{10^5}$$$ очков.

Официальный сайт игры: нажми сюда

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

Комментарии (24)

Написать комментарий?

kekkule

13 месяцев назад, # |

What is the reason of creating of this mirror?

→ Ответить

dalex

13 месяцев назад, # ^ |

← 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

12 месяцев назад, # ^ |

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

12 месяцев назад, # |

+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

11 месяцев назад, # |

nice problems

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	pajenegod	145
9	SecondThread	145

Блог пользователя dmkz