I'm trying to solve the following problem:
There are N
notes in an array (2<=N<=105) labeled 0..N-1, all of them initially set to 1
. Then there follows Q
operations to perform in the array (1<=Q<=105).
The task for each operation is:
- Find the most frequent value between the inclusive range
[A,B]
. - Add that value to all elements in the same range. The new values must be in range [0..8], then we take it modulo
9
.
At the end, output all array values.
This is the first problem of "Maratona de Programação da SBC – ACM ICPC – 2017" here in Brazil, and I'm trying to solve it in the URI Online Judge site. Time Limit: 1 second.
First I tried SQRT Decomposition because it looked good, but it's not. This week I came up with a few nice ideas to solve it using Segment Tree. I was so sure my code was perfect... but it wans't. Time limit exceeded again.
I don't have Advanced Data Structures classes, I learn those things by myself. So I'm probably lacking some fancy tree structure that would solve this problem really faster. Please, give me some resource to learn such a structure.
Here is an Ideone link to my code. Let me describe the few nice ideas using Segment tree that I mentioned above:
- Storing the difference (delta) instead of values. With that I was able to update the ranges without going to the leaf nodes. And to find value of some node, ex: leaf node
[0,0]
for N=8, I can traverse from root to that node and sum up delta values[0,7].delta + [0,3].delta + [0,1].delta + [0,0].delta
. - Store in each node the count of every value [0..8] in its descendants and itself. Because each node represents a subrange, then the frequencies can be precalculated.
- Instead of recalculating the subrange array of frequencies, I can rotate it. Ex: If the most frequent note is
3
, the previous quantity of values 2 is now the quantity of values 5, and so on... so rotating makes sense instead of calculating the quantities of descendant nodes again. - This is the most brilliant, I think. Instead of rotating, use the value (calculated using delta since root path) to find which index of the frequency subrange array should be treated as the first index 0.
I spent more than twenty hours over this week since the first version of the segment tree approach. It was not easy to think all the ideas I listed above. I know I'm not the best at it. But I think you can feel how frustrated I am, after getting Time Limit Exceeded in all of my attempts.
I also think I evolved since the Square Root Decomposition approach. The problem is that I am out of ideas to improve it further. If I didn't see that 156 people have already solved it. I would think it is impossible.
Please, share a bit of your knowledge with me. Thanks in advance.