Sorry - I wasn't aware. On Sun, Aug 5, 2012 at 8:38 PM, Lokesh Khandelwal <[email protected]> wrote: > Cheating ... Shameful ..this is a running question on codechef.com > http://www.codechef.com/AUG12/problems/DRANGE ..Please do not answer him > > > On Monday, August 6, 2012, Luke Pebody wrote: >> >> Instead of looking at the effect of these operations on the N numbers, >> look at the effect of these operations on: >> Number 1 >> Number 2 - Number 1 >> ... >> Number N - Number (N - 1) >> >> On Sun, Aug 5, 2012 at 8:17 PM, ADEGEYE MAYOWA <[email protected]> >> wrote: >> > My algorithm O(t*m*n) >> > >> > >> > On Aug 5, 2012 6:44 PM, "Vicky Sirwani" <[email protected]> >> > wrote: >> >> >> >> Alice has N pieces of paper. These papers are numbered from 1 to N. She >> >> writes down the numbers 1 to N in order (one number on each paper), >> >> i.e. >> >> paper i has number i written on it. Bob messes the numbers on these >> >> papers. >> >> He either adds a constant to a number or subtracts a constant from the >> >> number. He performs M such operations. Each operation is of the form: w >> >> x y >> >> z where each of them is an integer. If w = 1, then Alice has to add z >> >> to >> >> every number on papers x to y (both inclusive). If w = 2, then Alice >> >> has to >> >> subtract z from every number on papers x to y (both inclusive). After >> >> doing >> >> this, Bob challenges Alice to tell him the range of this data, where >> >> range >> >> denotes the count of numbers from the smallest number to the largest >> >> (See >> >> here for more details). Your task is to help Alice in finding the >> >> range. >> >> >> >> Input: >> >> >> >> First line of input contains a single integer T, the number of test >> >> cases. >> >> Each test case starts with a line containing two space separated >> >> integers >> >> N and M. >> >> Then follow M lines. Each of these lines is of the form w x y z. Each >> >> separated by a single space. >> >> >> >> Output: >> >> >> >> For each test case output a single line containing the range of the new >> >> data set after Bob's modifications. >> >> >> >> Constraints: >> >> >> >> 1 ≤ T ≤ 20 >> >> 1 ≤ M ≤ 10000 >> >> 1 ≤ N ≤ 1000000 >> >> 1 ≤ x ≤ y ≤ N >> >> 0 ≤ z ≤ 100000 >> >> >> >> Example: >> >> >> >> Input >> >> 1 >> >> 10 2 >> >> 2 3 6 4 >> >> 1 5 9 1 >> >> >> >> Output: >> >> 11 >> >> >> >> Explanation: Initially the papers are as follows: 1 2 3 4 5 6 7 8 9 10. >> >> First operation decreases the numbers on paper number 3,4,5 and 6 by 4. >> >> Now, >> >> the papers look like: 1 2 -1 0 1 2 7 8 9 10. The second operation >> >> increases >> >> the numbers on papers 5 to 9 by 1. The numbers will now be 1 2 -1 0 2 3 >> >> 8 9 >> >> 10 10. Thus, the range is 10 - (-1) = 11. >> >> >> >> >> >> >> >> Can anyone help me with this??? >> >> I can think of an O(t*m*n) solution, but it gives TLE. >> >> Any efficient algorithm for this??? >> >> >> >> -- >> >> You received this message because you are subscribed to the Google >> >> Groups >> >> "Google Code Jam" group. >> >> To post to this group, send email to [email protected]. >> >> To unsubscribe from this group, send email to >> >> [email protected]. >> >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> >> >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups >> > "Google Code Jam" group. >> > To post to this group, send email to [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]. >> > For more options, visit https://groups.google.com/groups/opt_out. >> > >> > >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit https://groups. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > >
-- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
