EQUALITY - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Konstantsin Sokol
Tester: Gedi Zheng
Editorialist: Miguel Oliveira

DIFFICULTY:

Easy.

PREREQUISITES:

Math, Linear Algebra.

PROBLEM

We have a system of N equations on N variables. Equation i is of the form: x_1 + x_2 + ... + x_{i-1} + x_{i+1} + .. x_n = A_i. You can prove that solution of this system of equations will be unique. You have to solve this system of equations.

QUICK EXPLANATION

  • Write each equation in form of sum - x_i = A_i where sum denotes sum of all the variables i.e. sum = x_1 + x_2 + \dots + x_n. So, x_i = (sum - A_i)
  • Now only thing that we have to do is to compute value of sum in terms of known values A_1, A_2, \dots A_n.
    Let us add all the equations, we get N * sum - ( x_1 + x_2 + \dots + x_n) = A_1 + A_2 + \dots + A_n.
    As, sum = x_1 + x_2 + \dots + x_n, we get sum = \frac{A_1 + A_2 + \dots + A_n}{N - 1}
  • So finally, x_i = \frac{A_1 + A_2 + \dots + A_n}{N - 1} - A_i.

EXPLANATION

The solution to a system of 2 variables is trivial:

\begin{cases} x_2 = A_1 \\ x_1 = A_2 \end{cases}

If we have 3 variables, the system is:

\begin{cases} x_2 + x_3 = A_1 \\ x_1 + x_3 = A_2 \\ x_1 + x_2 = A_3 \end{cases}

Each variable appears N-1 times. Let’s sum these equations. We get

\begin{array}{lcl} 2 * x_1 + 2 * x_2 + 2 * x_3 & = & A_1 + A_2 + A_3 \\ 2 * (x_1 + x_2 + x_3) & = & A_1 + A_2 + A_3 \\ x_1 + x_2 + x_3 & = & \frac{A_1 + A_2 + A_3}{2} \end{array}

Now, to know the value of each variable, we can reuse the original equations. Then, to know the value of x1, we can use the fact that x_2 + x_3 = A_1. Let S = A_1 + A_2 + A_3, then x_1 + A_1 = \frac{S}{2} \Leftrightarrow x_1 = \frac{S}{2} - A_1.

In general, let S = A_1 + A_2 + ... + A_n. For each variable, x_i = \frac{S}{N-1} - A_i.

Time Complexity

We can compute the sum in linear time and calculate the answer in linear time as well for a O(N) solution.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution

1 Like
2

can n1 tell me why my code is showing wrong answer?

#include<stdio.h>
#include<math.h>

int main()
{
int t,n;
int a[50000];
int x[50000];
int k,i;
int asum;
scanf("%d",&t);
if(t<=25000)
{
while(1)
{
scanf("%d",&n);
if(n>=2&&n<=50000)
{
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]<=(int)(5*(pow(10,12))))
asum+=a[i];
}
for(i=0;i<n;i++)
x[i]=((asum/(n-1))-a[i]);
for(i=0;i<n;i++){
if(x[i]<=(int)(pow(10,8)))
printf("%d\n",x[i]);}
}
asum=0;
k=0;
t–;
if(t<=0)
break;
}
}
return 0;
}

3

#include<stdio.h>
#include<math.h>

int main()
{
int t,n;
int a[50000];
int x[50000];
int k,i; int asum;
scanf("%d",&t);
if(t<=25000)
{
while(1)
{
scanf("%d",&n);
if(n>=2&&n<=50000)
{
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]<=(int)(5*(pow(10,12))))
{
asum+=a[i];
}
}
for(i=0;i<n;i++)
{
x[i]=((asum/(n-1))-a[i]);
}
for(i=0;i<n;i++)
{
if(x[i]<=(int)(pow(10,8)))
{
printf("%d\n",x[i]);
}
}
}
asum=0; k=0; t–;
if(t<=0)
{
break;
}
}
}
return 0;
}