Tparsa's blog

HARD
By Tparsa, 11 years ago, In English

Hello Everyone!

I Think Problem D in Div 2 RD225 = problem B in Div 1 RD225 too hard!!! because just 46 person got AC (2 person in Div 2 & 44 person in Div 1 !!)

and if you have some algorithm for this problem that got AC please share it here!

  • Vote: I like it
  • -24
  • Vote: I do not like it

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

It's mentioned that

"one needs to be good at "ad hoc" problems as well as have good algorithmic knowledge."

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

My idea was:

  • in each row, there are "good" intervals of cells that we can get to from (1, 1)

  • a volcano splits a good interval into 2 (one or both possibly empty); if there's no volcano between 2 cells from different good intervals, they're merged (more generally, if we can get to some cell, we can get to all cells to its right until a volcano (or the border of the map)

  • simulating this process efficiently (using set<>s for non-empty good intervals) for all rows is enough for comparably large n and m; for n large, merge chunks of empty rows into one

  • there are at most O(m) non-empty good intervals; each volcano now leads to operations that take time; the same time is taken by merging 2 good intervals, and there are O(m) empty rows (after the above mentioned merging), so the time is

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

I think my idea is right but i overlooked something.

If you imagine a graph where each node is a volcane and two volcanes share an edge if they share a common point, then you only need to check if (1, 1) is cut-off from (n, n).

You do this my imagineing that walls are also nodes in the graph and checking if coresponding walls are connected.

Edit: nevermind i got it, where i was wrong.

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

    That was my idea at first. Remember 325D - Reclamation? There was also this problem where you needed to find the smallest square such that blocking (free) cells in such square will separate the top left and bottom right corner, and it used a similar idea.

    I soon found a test case where this approach failed :D

    → Reply