Here's the solution to the problem one hint at a time. High quality problems are rare, and it would be a waste to read the solution without trying to solve the problem for a few hours.
Read one hint at a time. As soon as you get to a hin...
Read more… (373 words)
Read more (373 words)
Motivation: Given an array of N numbers, you need to support two operations. Operation 1: find-min(i, j) = return the minimum value in array[i ... j]. Operation 2: update(i, v) = update the value at array[i] to v. Solve the problem for N <= 10^6, number of operations <= 10^6.
To solve the above problem, both the operations need to run in O(log N) time, but using an naive array gives O(N) run-time for operation 1 (and O(1) run-time for operation 2). So how do you solve the problem? Read on. :)
Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.
Try to not read this next hint, it gives it all away...
Read more… (82 words)
Read more (82 words)
Topics which will be discussed in IOITC
I got selection to IOITC this year. I would like to know more about the camp and topics which will be discussed there. Will they teach the whole syllabus of IOI in the camp within a span 10 days? What all should I learn before attending the camp in order to understand everything discussed there in a more better way?