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.
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
public class Numbers {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
List<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < num; i++) {
int arr[] = new int[2];
arr[0] = in.nextInt();
arr[1] = in.nextInt();
List<String> li = new ArrayList<String>();
for (int j = 0; j < arr[1]; j++) {
li.add(in.next());
li.add(in.next());
li.add(in.next());
li.add(in.next());
}
int min = 1;
int max = arr[0];
int array[] = new int[arr[0]];
for (int u = 0; u < array.length; u++)
array[u] = u+1;
for (int v = 0; v < arr[1]; v++) {
int f = Integer.parseInt(li.remove(0));
int s = Integer.parseInt(li.remove(0));
int t = Integer.parseInt(li.remove(0));
int fr = Integer.parseInt(li.remove(0));
switch (f) {
case 1:
for (int h = s; h <=t; h++) {
array[h-1] = array[h-1] + fr;
if (min > array[h-1])
min = array[h-1];
if (array[h-1] > max)
max = array[h-1];
}
break;
case 2:
for (int h = s; h <=t; h++) {
array[h-1] = array[h-1] -fr;
if (min > array[h-1])
min = array[h-1];
if (array[h-1] > max)
max = array[h-1];
}
break;
}
}
ans.add(max - min);
}
for (int e : ans)
System.out.println(e);
}
}
