I have programmed the Binary Indexed Tree approach in C# here: http://ideone.com/Ammsll
On Wed, Jan 28, 2015 at 3:42 AM, Luke Pebody <[email protected]> wrote: > 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 <[email protected]> > 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 [email protected]. >> To post to this group, send email to [email protected]. >> 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 [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-PAb%3D-%2B_og-gP2ViCravWVPpkVh9uCRaWdf1o5Q_%2Bf5hA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
