Tparsa's blog

HARD
By Tparsa, 10 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

»
10 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
»
10 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
»
10 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