CODEWITHSUNDEEP
algorithmdata-structures
a Bg
a Bg

Reputation: 11

Unable to solve a codechef problem

Is (O(n),O(log n)) approach sufficient to solve the problem - http://www.codechef.com/problems/MULTQ3/ ?

(Update time - O(n), query time - O(log n))

My solution - solved using the above approach (using segment trees) was adjudged a 'TLE' submission by the Codechef judge.

Well, I even tried an (O(log n),O(n)) approach to the problem (update time - O(log n), query time - O(n)), but even that was rejected by the Codechef judge as exceeding the time limit. I have no idea where to go from here as of now. Here is the link to my second submission - http://www.codechef.com/viewsolution/558614

Anyone who has already solved the problem is requested to help me with this. Can I make it (O(lgn)-O(lgn))? how?

Thanks in advance.

Upvotes: 0

Views: 1030

Answers (1)

btilly
btilly

Reputation: 46542

It can indeed be made O(log(n)), O(log(n)).

The trick is to have a tree represented by a data structure with the following pieces of information at each node:

  • start index
  • end index
  • left node
  • right node
  • How many 0 mod(3)
  • How many 1 mod(3)
  • How many 2 mod(3)
  • Unapplied update amount

When you are told to apply an update, you only need to apply it (and that unapplied amount) to nodes which have a boundary inside of that range. Otherwise just increment the unapplied update amount. You'll lazily apply it if you ever need to.

When you query a range you can lazily apply the unapplied update amount and fetch from the right bucket unless the range in question has a boundary inside of the range of indexes in that part of the tree. Then, and only then, do you need to bring the unapplied update amount down into interior nodes.

Both operations only drill in to the part of the tree on the boundary and are therefore O(log(n)).

Upvotes: 2

Related Questions