Having verified that the contest this puzzle was in is no longer running: If the upper bound on the number of students is 10,000 and the upper bound on the number of chocolates is 105 then the total number of deliveries of chocolates to students is at most 1,050,000. As such a brute force method would work: set an array of the number of chocolates each student has (initially 0), and then do the deliveries manually. See http://ideone.com/6YqhYm for an implementation of this in Python.
Now, if the bounds on N, u and k were all increased dramatically, it would still be solvable, but you would need a more complicated data structure. See this tutorial: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees On Mon, Jan 26, 2015 at 3:52 PM, Yask Srivastava <yask...@gmail.com> wrote: > On the occasion of Republic day, Chef wants to give away chocolates to the > students. N students are eagerly waiting for the Chef and they have formed > a queue. > Chef has u variety of chocolates. Looking at the strength of the students > he is sure that he cannot provide chocolates of all the variety to all the > students. He decided that he will start from ith student and end at jth > student (0 ≤ i,j < N) and will give them K number of chocolates to each > student. In the same manner chef distributed all the varieties of > chocolates. > Now Lemon Kumar, who is a very friendly student (as his other name is Yaar > Kumar), has M number of friends. He knows the positions of each of his > friend in the queue. Now he wants to query for each friend, how many > chocolates his friend standing on pth position got. > Input > > First line consists of T, the number of test cases. > Each test case consists of two number, N u, the number of students in the > queue and the number of varieties of chocolates Chef has. > Then follow u lines, giving description of distribution of each variety of > chocolate, in the format "i j k". > Next line contains M, the number of friends of Lemon Kumar. > Next M lines contain a position p of Lemon's friend standing in the line. > Output > > For each test case, print the result of the query for M friends, each on a > separate line.. > Constraints > > 1 ≤ T ≤ 30 > 1 ≤ N ≤ 10000 > 1 ≤ u ≤ 105 > 0 ≤ i,j<N > 0 ≤ k<10000 > 1 ≤ M<10000 > 0 ≤ p<N > > Example > > Input: > 1 > 6 4 > 3 5 2 > 2 4 3 > 1 5 1 > 0 2 4 > 4 > 4 > 3 > 2 > 0 > > Output: > 6 > 6 > 8 > 4 > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To post to this group, send email to google-code@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/b0dcc504-079d-44db-a004-14ddc39b78a2%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-Of3TTZ0KiXq%3DzJ2moThUfKTa%2BpunvHsmM8Zec3ok3rWQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
