a_kabdygali's blog

Problems in lightoj.com
By a_kabdygali, 10 years ago, In English

Hello everyone ! Please help me to solve these problems from lightoj.com : 1083 1135 1424 Thank you for your attention.

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

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

The histogram problem can be solved easily with a stack. We push the first value to the stack. Then we push the second one etc etc. If the value that we want to push to the stack is less than the one that is on top of the stack, we dont push it and we pop values until the value on top of the stack is less than the one that we want to push. With this information you should be able to figure out the details yourself.

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

The second problem can be solved with a segment tree with lazy propagation. At every node you keep the number of numbers in the interval that are 0 mod 3,1 mod 3 and 2 mod 3. Try to figure out the updates yourself.

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

The third problem with the king and prince can be solved like the first histogram problem. We will go row by row. Every row is the starting axis of the histogram and the values in the histogram are how many consecutive cells are above me, that doesnt contain any rocks. Then the problem is reduced to N or M histograms.

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

Could you suggest some problems that you solved in lightoj and found challenging?

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

    I'm sorry, but I've solved only 10 problems. And all of them not hard.

    → Reply
»
6 years ago, # |
  Vote: I like it -6 Vote: I do not like it

What was your approx. rating when you asked this help? Just curious to know.

→ Reply