Since there was no blog post, so I wrote it.
The contest starts in 12 minutes.
The registeration of Fun SRM ends in 7 minutes, so you can go to https://arena.topcoder.com and register it.
Good luck and have fun and let's discuss after the contest!
UPD: Congratulations for winners!
| Warsaw Regional | Fun SRM | ||
|---|---|---|---|
| tomekkulczynski | 1333.96 pts | sigma425 | 1492.01 pts |
| Pol-BoBaN | 1239.69 pts | ksun48 | 1293.74 pts |
| Marcin_smu | 1234.28 pts | snuke | 1249.58 pts |
| monsoon | 1206.17 pts | sugim48 | 1193.94 pts |
| fbudrowski | 1131.36 pts | anta | 1189.33 pts |
How to solve 1000?
I believe if there is a solution, it is unique (proof sketch, fill the grid in row major order).
In contest I didn't think solution was unique so I struggled to find how to maximize the maximum cycle.
I think to produce any solution, you can just do 2-SAT on the cells of the grid. Each cell that is not '.' has 2 choices and for each choice, it will impose some conditions (sometimes none) on which version of cell to choose for the adjacent cells. (add a border of '.' on all 4 directions to simplify things)
250 and 450 were worth maximum 100 points each, why so easy?
I guess the conversion of normal Topcoder SRM score is:
- Easy: Div2 300pts
- Medium: Easy one of Div1 250pts
- Hard: Div1 450pts
But, I felt like even Medium problem was interesting, so anyway it's good for me :)Strong tests for 1000: my solution didn't check if I'm actually producing cycles and still passed (test by square1001: {"DS", "US"}).
Lol, tests to 1000 are pathetic. During contest I discovered three bugs and decided to fix them, but it turns out that only one fix was needed. First thing is that in my first version I did not distinguish between ULRD, treated them in exactly same way. Yes, it passes. Another thing was that when it was "S" cell I was sometimes putting there two straight pipes as in
/\.\+\.\/example. In output such cross was printed as "-". It passes sytests with such bug also.