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.<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.
