3_Problems_Everyday's blog

Help in Croc Champ 2013 — Round 1 Problem-E
By 3_Problems_Everyday, history, 8 years ago, In English

Could anyone please tell me how to solve Problem E . I have seen some codes which use a segment tree but i am not able to understand. Also there is no editorial for this round .Any help would be appreciated. Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi, I've just solve this problem and looking for the editorial I found your question, maybe you already solves this problem but anyways.

I use a Segment Tree with Lazy Propagation, I don't know if it is the best solution, that's why I was looking for the editorial. If this technique is not familiar to you I suggest you to search it on google. Basically it allows to made updates in O(log(N)) time.

First, what you have to notice is that after each modification, you have to reset all the values, no matter what modifications occurred before. So if you know which was the last modification that affects the position you are analyzing you could answer the query. I let this part to you.

I used the ST to know latest modification. My ST answer the query max element in a range (in this particular problem the range is always length 1). Using lazy propagation you update range [y,y+k-1] whit value cont (the ordinal of the modification). When you ask for the max value you will get the desire ordinal of the modification.

I let you my code. 20223882 Sorry for my english.

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

I used another technique that is similar to this problem: 555B - Case of Fugitive. It's one that is used quite often in data structures problems. Try solving that one then solving this. I think it might give you some good insights. If you're desperate for the solution of this problem: 19610583

→ Reply