Free-flowing logs of my thoughts, experiments, etc.
The problem statement is here.
Day 1
I read the statement. The maximization of path length on the 2-dimensional grids...?
I've solved a problem similar to this one!
RCO Nihombashi Half Marathon 2 Final : A - ぐるぐる庭園
(Note: The statement of this problem is only in Japanese, but perhaps you can guess the outline of the problem by seeing the animation attached to the following tweet.)
Aの input-1.txt の出力を動画で (10088点) #rco_procon pic.twitter.com/uLwVdfPFle
— yowa (@yowa) March 10, 2018
I remember this problem very well because it was a frustrating experience for me in the on-site contest. At that time I couldn't come up with slanted zigzags, then I dropped out from the struggle for the top. I think I have an advantage this time since I have know-how although problem-setting differs a little.
I try making a loop path of slanted zigzag like the left one in the above figure, then make it a long direct path by filling one cell on the loop. I choose a cell to fill by brute-force. I got about 60 pts with this solution while c7c7 scored around 95 pts. It seems to be more difficult to win than I thought.
I add a flip horizontal version of a slanted zigzag as a candidate.
This zigzag algorithm is weak when a field is dense with robots and targets since the zigzag wall gets to be worm-eaten. I should consider another solution for these cases.
I came up with a greedy method that tries pulling a wall straight from one cell away from another wall in the opposite direction. Finally, it tries to detect rectangles that consist of empty cells and fills them with a horizontal or vertical zigzag.
I introduce randomness to choose one from tie breaks and run it with all the time left. I adopt the best result from slanted zigzag solutions and greedy wall solutions for each test case. It got 69 pts.
Day 2
wleite implemented an interactive mode on the tester. To put it mildly, it's super useful!
My current slanted zigzag should get worse when it's worm-eaten with objects. To avoid it, I add some variations by sliding all walls by 1 or 2 cells horizontally or vertically. It works a little, got 74 pts.
Day 3
As we can see from the above "seed = 2" figure, there are many empty remaining cells that cleaners don't pass through. I'd like to make use of them.
Playing with the interactive mode, I found some patterns that can improve the score.
I fill up empty cells that cleaners don't pass through, and adopt the above pattern transformations including their rotations and inversion. Then I got 80 pts.
Day 4
On second thought, borders between two turning points can be moved freely.
For example, if it's assumed that cleaners pass through the lower left-hand path more than the upper right-hand one, a border should be moved to the upper right side to improve the score. I introduce this optimization greedily before the pattern transformation I implemented yesterday. Then I got 83 pts.
Day 5
I don't come up with anymore, so I adjust random values on the greedy method for small N. I didn't expect it achieves results, but actually my score rose imperceptibly and my rank has gone up by one! (nonsense)
Day 6
I really don't come up with anymore, so I just started to write this article.
Creating the zigzag figures on the section "First day", I noticed that there is less difference between two path lengths (slanted vs horizontal/vertical) than I thought. Should I try horizontal/vertical zigzag for small N...?
Hmm, you see, there is nothing better than organizing thoughts when getting stuck!
It didn't work well... I wonder if horizontal/vertical zigzag collides with more objects because it has more walls than slanted ones.
Day 7
I'm confirming that my solution doesn't get an invalid score by running with various seed just in case.
And finally, wleite has overtaken c7c7! How will the game play out...!?
After the end
I couldn't improve my score in the second half of the contest as usual...
It seems that the solution with a slanted zigzag loop is a pitfall?
最初ぐるぐる庭園に引きずられて斜めベースで初期解作っていたけど、それは罠だった
— tomerun (@tomerun) August 5, 2020
I see several people tried SA. Certainly, it sounds smarter in a smaller case.
I felt my solution is at the limit from about day 5. Perhaps it was the time to change the direction.
