Ahmed_Morsy's blog

IOI 2014 Day 1 wall
By Ahmed_Morsy, 10 years ago, In English

i read the tutorial and other solutions on the internet but none of them described the lazy propagation , it seems a little bit complicated anyone ?

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

»
10 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

task is here

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

    i don't understand why this comment is downvoted so much. SEFI2 has just provided a link to statement of the problem mentioned in OP.
    EDIT: comment now has +7. :)

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

Look up the solution for UVa 11402 Ahoy Pirates. That's what worked for me...

http://nminhtu94.blogspot.com/2012/12/uva-11402-ahoy-pirates.html

http://ajmarin.alwaysdata.net/codes/problems/1274/

http://lbv-pc.blogspot.com/2012/10/ahoy-pirates_24.html etc

EDIT: Not sure if you were looking for a detailed solution for the problem. If you did, I feel like after understanding the technique behind Ahoy, Pirates, you'll be able to figure out the solution for 'wall' yourself.

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

It's a rather complicated tree problem. At each node you need two values: down and up (the height when you call type 2 operation and type 1 operation, respectively).

  • Set up the tree by making up = 0 and down = INF for every node.
  • When you update the tree, combine every node along the path with its children. Let dp and up be the values of the parent and dc and uc the values of the child. Then you combine them by doing the following four operations: 1) dc = min(dc, dp), 2) dc = max(dc, up), 3) uc = max(uc, up), 4) uc = min(uc, dp). After this, set dp = INF and up = 0. By resetting the nodes along the path, you make sure that whatever operation is present on the parent comes after the operations on its children, and the reasoning for those four operations to combine them is as follows: 1) If you lower to height h on the child and to height h' on the parent after that, only min(h, h') will take effect. 2) If you decrease to height h on the child and then increase to height h' on the parent, with h' > h, then the first operation will lose effect. 3) If you increase to height h on the child and then increase to height h' on the parent, only max(h, h') will take effect. 4) If you increase to height h on the child and then decrease to height h' on the parent, with h' < h, then the first operation will lose effect.
  • When you reach the node you need to update, if you need to increase to height h, you do down = max(down, h) and up = max(up, h). If, on the other hand, you're decreasing to height h, you do down = min(down, h) and up = min(up, h).
  • After all the queries, you walk the tree from root to leaves and you combine every node with their children, as explained earlier (you don't do it for the leaves, obviously).
  • Finally, you output min(down, up) for all the leaves of the tree.

Perhaps the code will be clearer than the explanation. Here --> C++ code

→ Reply