1 / 2
Jan 2017

I'm trying to solve this29 problem.
My logic is as follows :

Say input array is : 7,4,5,6

Then the value of F[A] will be

7*7 + 4*4 - 2*7*4 +
7*7 + 5*5 - 2*7*5 +
7*7 + 6*6 - 2*7*6 +

4*4 + 5*5 - 2*5*4 +
4*4 + 6*6 - 2*4*6 +

5*5 + 6*6 - 2*5*6

Thus, F[A] will be

3*(7*7) + 3*(4*4) + 3*(5*5) + 3*(6*6) - 2* ( 7*(4 + 5 + 6) + 4*(5 + 6) + 5*(6) )

To calculate this, first prepare the sum array where sum[i] is sum of all the elements of a from i to length of array

for(int i=n-1;i>=0;i--) {
	if(i == n-1) {
		sum[i] = a[i];
	} else {
		sum[i] = sum[i+1] + a[i];
	}
}

Then to calculate F[A],

double ans = 0;
for(int i=0;i<n;i++) {
	ans += a[i] * a[i] * (n - 1);
	if(i != n - 1) {
		ans -= (2 * a[i] * sum[i+1]);
	}
	ans %= MOD; 
}

That will be the F[A] for the original input array.

For query type 1,x,v
For example we have 1,2,8
The array will be 7,8,5,6

The previous ans was:

3*(7*7) + 3*(4*4) + 3*(5*5) + 3*(6*6) - 2 * ( 7*(4 + 5 + 6) + 4*(5 + 6) + 5*(6) )

The new ans will be :

3*(7*7) + 3*(8*8) + 3*(5*5) + 3*(6*6) - 2 * ( 7*(8 + 5 + 6) + 8*(5 + 6) + 5*(6) )

Re writing it,

3*(7*7) + 3*(8*8) + 3*(5*5) + 3*(6*6) - 2 * ( 8 * ( 7 + 5 + 6 ) + 7 * ( 5 + 6 ) + 5 * (6) )

To incorporate such change in O(1),
I have one variable totalSum which has the value of sum[0] or sum of all the elements in the array

The code to make changes is:

//Undoing the effects of a[x] from F[A]
ans -= a[x] * a[x] * (n - 1);
ans += 2 * a[x] * ( totalSum- a[x] );

//Making changes in total sum and actual a[x]
totalSum += (-a[x] + v);
a[x] = v;

//Incorporating the changes as explained above
ans += a[x] * a[x] * (n - 1);
ans -= 2 * a[x] * ( totalSum - a[x] );	
ans %= MOD;

Similarly for query type 2,x,v

//Undoing the effects of a[x] from F[A]
ans -= a[x] * a[x] * (n - 1);
ans += 2 * a[x] * ( totalSum- a[x] );

//Making changes in total sum and actual a[x]
totalSum += v
a[x] += v;

//Incorporating the changes as explained above
ans += a[x] * a[x] * (n - 1);
ans -= 2 * a[x] * ( totalSum - a[x] );	
ans %= MOD;

I'm getting correct answers in my custom inputs. I have tried cross checking the answers with the randomly generated input and calculating them using brute force ( O(n*2) ) and the logic explained above. And I am getting correct answer for each custom input.

Although, I get wrong answer when I submit the problem. Any idea why ?

Here is the full code I'm submitting

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main {

	private static final double MOD = Double.parseDouble("2760727302517");

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		final int t = Integer.parseInt(br.readLine());
		for(int Q=1;Q<=t;Q++) {
			bw.write("Case "+Q+":\n");
			String ip[] = br.readLine().split(" ");
			final int n = Integer.parseInt(ip[0]);
			final int q = Integer.parseInt(ip[1]);
			final double a[] = new double[n];
			final double sum[] = new double[n];
			ip = br.readLine().split(" ");
			for(int i=0;i<n;i++) {
				a[i] = Double.parseDouble(ip[i]);
			}

			for(int i=n-1;i>=0;i--) {
				if(i == n-1) {
					sum[i] = a[i];
				} else {
					sum[i] = sum[i+1] + a[i];
				}
			}

			double ans = 0;
			double totalSum = sum[0];
			for(int i=0;i<n;i++) {
				ans += a[i] * a[i] * (n - 1);
				if(i != n - 1) {
					ans -= (2 * a[i] * sum[i+1]);
				}
				ans %= MOD; 
			}
			
			for(int T=0;T<q;T++) {
				final String query[] = br.readLine().split(" ");
				if(query.length == 1) {
					bw.write(String.format("%.0f\n",ans%MOD));
				} else {
					final int tmp = Integer.parseInt(query[0]);
					final int x = Integer.parseInt(query[1]) - 1;
					final double v = Double.parseDouble(query[2]);
					ans -= a[x] * a[x] * (n - 1);
					ans += 2 * a[x] * ( totalSum- a[x] );
					if(tmp == 1) {	
						totalSum += (-a[x] + v);
						a[x] = v;
					} else {
						totalSum += v;
						a[x] += v;
					}
					ans += a[x] * a[x] * (n - 1);
					ans -= 2 * a[x] * ( totalSum - a[x] );	
					ans %= MOD;
				}
			}
		}
		bw.close();
	}
}
  • created

    Jan '17
  • last reply

    Nov '23
  • 1

    reply

  • 921

    views

  • 2

    users

  • 1

    link

6 years later

make sure u have selected java as submission language…otherwise I don’t know the error