square1001's blog

Topcoder Warsaw Regional Round + Fun SRM 2017/09/02
By square1001, 7 years ago, In English

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

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 1000?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe if there is a solution, it is unique (proof sketch, fill the grid in row major order).

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

250 and 450 were worth maximum 100 points each, why so easy?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)
    → Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Strong tests for 1000: my solution didn't check if I'm actually producing cycles and still passed (test by square1001: {"DS", "US"}).

→ Reply
»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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.

→ Reply