mysterion's blog

TopCoder SRM #583
By mysterion, 11 years ago, In English

Hello,

SRM 583 will happen today at 19:10 MSK

More details here

Good luck everybody!

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

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What's idea in 900 div2?

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

    It's obvious that if first player chooses some cell (x, y), second player chooses a cell with a maximum distance to (x, y). So we need to minimize the maximum distance from other cells to chosen. We can precompute the d[x][y][x2][y2] — the minimum distance from (x, y) to (x2, y2). Then just iterate over all cells, and for each cell compute maximum distance from other cells to chosen. Then just get minimum. That's all.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    You can use a simple SPFA to pass it, it's an easy problem! We know that first person always choose the start point to minimize the longest shortest path from it. So we need to determind every point in the map and let it be the start point. Then we can use a SPFA to calculate all shortest path from this point and find the longest. At last we should return the smallest longest shortest path amaong all the nodes. We can think it just an O(N*N) algorithm. Because of N is at most 1600, so we can pass this problem now!

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

Sad my history. I tried to solve the 550's problem first and I did not have time to send 250's problem. Then, my solution was hacked because I forgot to write '<=' instead '<'. Is it a good idea try to solve the second problem and then to solve the first in Topcoder?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it

    I think it depends. Since the order of solving doesn't matter in Topcoder if you have enough time to solve both, either way is fine.

    If you solve easy problem first, you will get some certain points as well as a kind of warmup before going to the next ones.

    If you choose to start with the medium — like what I usually do, you will avoid lack of time for it in some cases, but some tricky 250 probably become more challenging if you switch into them too late. To prevent this from happening, use the scoreboard wisely. However, the main reason I stick with this strategy is because I do not learn much from solving a 250 only. Some times it works, the other you may end up with no problem solved. Yet I think keeping doing this way would help you improve your solving skill faster, as least in my own experience.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Well according to me it is always a good idea to first attempt the 500 problem because at the start you can give time to a better question as compared to a 250 point problem which on an average just requires at most 5-7 minutes (if it is not a tricky one).Well you can also take the help of the scoreboard to make a guess what is the level of the question and switch to the other question if required ....

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

Editorial

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it 
     swap(dx,dy); dy *= -1;

    Nice magic trick. Thanks!

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Magic? :) Just a rotation using complex numbers:

      // * (-i) <=> rotate 90 deg clockwise
(x + yi) * (-i) = (y - xi)
      → Reply