hiddentesla's blog

need help in problem suma
By hiddentesla, history, 8 years ago, In English

problem link: https://open.kattis.com/problems/suma

so its ben 3 days since im stuck in solving this problem, i solved a similar problem called islands : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=360&page=show_problem&problem=2628

where my idea is do union find from backwards, (i.e start when all the land is flooded, then move time backwards, if for some time a land becomes unfloded, add it as a new single group, then if its neighbours are not flooded, do union() operation with its neighbour)

but in suma that does not apply, because if i work backwards, some trees would not stay "connected" permanently, because at some time, they will be different heights again, and im having troubles coming up with somthing. so can anybody give me some hints to solve this?

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

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

sorry... still no ideas :(

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

The problem is from COCI 2014 Contest #2, so you can find the solution there.

If you want a small hint only:

Any pair of trees will have the same height at only one specific moment, unless they have both the same growth and initial height. The idea would be to process specific time moments in which two adjacent trees become with the same height, however we have to be careful with large components of same growth/same initial height elements, as to not iterate them multiple times.

If you've been stuck on the problem for so long, though, you can just read the tutorial from COCI, it's nicely written.

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

    i dont get it... in the solution, we are asked to examine every two adjacent fields, so for example:

    a b c d e f

    so we are so examine the time where:

    ab are the same height, bc are the same height de,ef,ad,be,cf

    is the number of "events" not equal to m*n? why is it mentioned to be 4n?

    also, is the solution suggests making all the possible event times, for each time, i update the matrix accordingly, and then dfs to see the maximum connected component, but since there are m*n possible time at max, and updating the matrix takes m*n while dfs takes m*n (visiting all nodes), should the runtime complexity be O(m^2 * n^2)?

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

      You're right that the number of events can be O(n*m), but even then the total complexity is O(n*m) if we don't have pairs with equal height and growth. This is because when we fix some time moment we only visit 'edges' with that time moment which is amortised O(n*m). Since we have same height same growth pairs we need something like a persistent union-find, which we can implement naively.

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

        wait... when we fix some time moment, do we start our transversal from that time, or do we dfs the whole board? because how i understand the solution, since it says there are at most 4n events, im guessing the solution was to store all possible times when adj trees would become same height, then remove duplicates, then just try the board for all the remaining values, so for everytime we try a new value, we need m*n updates to update the board.

        if we start on the targeted node, doest that mean we are trying about m*n spots?. also 3 trees with different height and grow can become the same height at the same time, for example if initial height was 0 1 2, while growth speed is 3 2 1, they will become the same height after 1 second, so im guessing we still have to do some dfs if we start at the node we targeted to be the same height, which would add some complexities right? or do we mark "visited" so we dont visit a particular node again? (the only way i can think of is bool visited[x][y][time] which would be MLE)

        i really thought this out (my head even literally got hot), maybe the logic is not strong enough can it seems not trivial to me :|, could you give me some examples/

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

          Very busy, so I'm sorry that I can't give proper examples, but the idea is:

          Firstly, we deal with all pairs that are always the same (same growth and initial height). We build a union find of those only, and this is our base state that we will restore later on. Now we get all moments at which some adjacent pair will become the same and sort them chronologically. When we process some pair then all we do is merge the two sets in our union find. The trick is that each time we process an event such that the next event is not at the same time, we revert our union find to the base one that connects only those who always stay the same. In this way, in a way, we process blocks of events which happen at the same time.

          Now the only tricky part is reverting back to our base union find state quickly. Obviously if we do it in time proportional to the grid size then that would be too much, so we need a way to "undo" operations, which can be done quite naively with some book keeping. It can be proven that if you use the "merge smaller set to larger set" optimisation, then no Find operation will make many changes, and hence reverting the operations one-by-one is fast enough.

          You can refer to the author's code to see how he implements this idea.

          → Reply