# Optimising Funny Marbles

Problem statement is at http://www.codechef.com/DEC13/problems/MARBLEGF

Lira is given array A, which contains elements between 1000 and 2000. Three types of queries can be performed on this array: add a given value to a single element on it, subtract a given value from a single element on it and find the sum of the values between indexes i and j, i.e. A[i]+...+A[j]. Check input and example section for details.

### Input

The first line of the input contains two integers: N and Q, denoting respectively, the number of students that there are present to receive the marbles as a gift and the number of actions Lira's mom will perform.

These actions can be of three different types:

• S i j - if the mom wants to find the sum of the number of marbles from students i to j.
• G i num_marbles - if the mom decides to give num_marbles to student i
• T i num_marbles - if the mom decides to take away num_marbles from student i

### Output

The output should contain as many lines as the number of queries S and it should contain the answer for each query on a separate line

### Constraints

• 2 ≤ N ≤ 1000000
• 3 ≤ Q ≤ 50000
• The array is 0-indexed.
• 1000 ≤ A[i] ≤ 2000
• A student can never have a negative value of marbles. (i.e. there's no data which can cause a student to have a negative value of marbles)
• 0 ≤ i, j ≤ N-1, and i ≤ j for the sum query
• At any given time, it is assured that the maximum number of marbles each student can have (num_marbles) never exceeds the size of the int data type.

### Example

Input:

5 3
1000 1002 1003 1004 1005
S 0 2
G 0 3
S 0 2


Output:

3005
3008


My code gives time limit exceeded.

My code:

import java.util.*;

class funny_marbles
{
public static void main(String[] ar)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++)
a[i] = sc.nextInt();
for(int i = 0; i < q; i++)
{
String s = sc.next();
int t1 = sc.nextInt();
int t2 = sc.nextInt();
if(s.equals("S"))
{
long sum = 0;
for(int j = t1; j <= t2; j++)
sum+=a[j];
System.out.println(sum);
}
else if(s.equals("G"))
a[t1]+=t2;
else if(s.equals("T"))
a[t1]-=t2;
}
}
}


Updated to use cumulative sum, but still exceeding time limit:

import java.util.*;

class funny_marbles
{
public static void main(String[] ar)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++)
{
if(i == 0)
a[i] = sc.nextInt();
else
a[i] = a[i-1] + sc.nextInt();
}
for(int i = 0; i < q; i++)
{
String s = sc.next();
int t1 = sc.nextInt();
int t2 = sc.nextInt();
if(s.equals("S"))
{
int x;
if(t1 == 0)
x = 0;
else
x = a[t1-1];
System.out.println(a[t2]-x);
}
else if(s.equals("G"))
{
update(a,t2);
}
else if(s.equals("T"))
{
update(a,-t2);
}
}
}

public static void update(int[] a, int t)
{
for(int i = 0; i < a.length; i++)
a[i] += t;
}
}

• How are you timing it? What input values are you using? Also please add a short description of the problem itself within the question. Also please describe your approach a little so that it is easier to understand your code. – Simon Forsberg Dec 20 '13 at 19:05
• @SimonAndréForsberg I am not timing it, I submitted it at CodeChef and it gave TLE.It works for sample input.I haven't done special, just simulated what was written in the question.But I think brute force will not work here. – user2369284 Dec 20 '13 at 19:09
• @user2369284 Very nicely formatted question. – Fiddling Bits Dec 20 '13 at 19:35

Given the constraints, the maximum sum, N * max(A), would be 2000000000, which fits within a Java int. You don't need a long.

Your code is a straightforward implementation of the challenge; there's nothing to micro-optimize. Your only hope is to use a different approach.

Assuming that the test is heavy on "S" queries, you would be better off keeping an array of cumulative sums. Then you could answer an "S" query in constant time.

What to do with "G" and "T" operations, though? The elegant approach would be to update the entire cumulative sums array for each "G" or "T". However, since N is likely to be larger than Q, you might get better performance keeping the "G" and "T" operations as a list of exceptions instead.

• What do you mean by cumulative sums? – user2369284 Dec 20 '13 at 19:42
• For the example, store { 1000, 2002, 3005, 4009, 5014 }. – 200_success Dec 20 '13 at 19:46
• In short, I have to make a cumulative array, apply "G" and "T" on all elements and for "S" return array[j] - array[i]. Is that correct ? – user2369284 Dec 20 '13 at 19:52
• Updated my code. Still giving TLE – user2369284 Dec 20 '13 at 20:09
• Please don't edit away the original code; doing so invalidates any reviews. I've restored the original code. – 200_success Dec 20 '13 at 20:50