# TLAPM - Editorial

How do u observed that ?

Can anyone help me out with this approach?
https://www.codechef.com/viewsolution/46870104

I precomputed only the y axis sum (Total Sum so far) ,i.e if we want any element of matrix at (0,i) than it can be calculated as matrix[i]-matrix[i-1] and sum from (0,i) to (0,j) then it is matrix[j]-matrix[i-1]. So what it did is i precomputed the vertical path and i will compute the horizontal path on given query and add them for final ans. But i am getting WA. Pls Help!!!

getting tle for this…pls if someone can see into it…(generated array and did sum)
#include <bits/stdc++.h>
using namespace std;

int main()
{
long t;
cin>>t;
while(t–)
{
long x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
unsigned long long a;
memset(a,0,sizeof(a));
a=1;
for(int i=2;i<=1003;i++)
{
a[i]=a[i-1]+(i-1);
}
for(int j=2;j<=1003;j++)
{
a[j]=a[j-1]+j;
}
// for(int j=2;j<=1003;j++)
// {
// unsigned long long k=j;
// unsigned long long last = k;
// for(int i=2;i<=1003;i++)
// {
// a[j][i]+=(a[j-1][i]+last);
// last++;
// }
// k++;
// }

``````for(int i=2;i<=1003;i++)
{
long  k=i;
long  last = k;
for(int j=2;j<=1003;j++)
{
a[i][j]+=(a[i-1][j]+last);
last++;
}
k++;
}
if(x1==x2&&y1==y2)
{
cout<<a[x1][y1]<<endl;
continue;
}

// for(int i=1;i<=4;i++)
// {
//     for(int j=1;j<=4;j++)
//     {
//         cout<<a[j][i]<<" ";
//     }
//     cout<<endl;
// }
unsigned long long int summ=0;
if(y1==y2)
{
while(1)
{
summ+=a[x1][y1];
x1++;
if(x1==x2)
{
summ+=a[x1][y1];
break;
}
}
}
else
{
while(1)
{
summ+=a[x1][y1];
y1++;
if(y1==y2)
{
summ+=a[x1][y1];
break;
}
}
if(x1==x2)
{
cout<<summ<<endl;
continue;
}
while(1)
{
x1++;
summ+=a[x1][y1];
if(x1==x2)
{
break;
}
}
}
cout<<summ<<endl;
}
return 0;
``````

}

its given in ques …just below the table " Let (x,y)(x,y) denote the cell in the xx-th row and yy-th column"

Ups… you’re right, I guess I have to read more carefully then… Eh…

Here is my C++ code. I am posting it just for the sake of posting. ``````#include <bits/stdc++.h>
using namespace std;

void faster_io() {
ios::sync_with_stdio(0);
cin.tie(0);
}

int main() {
faster_io();

int max_size = 1000;
vector<vector<int>> mat (max_size + 1, vector<int> (max_size + 1, 0));
for (int i = 0; i <= max_size; i++) mat[i] = 0;
for (int j = 0; j <= max_size; j++) mat[j] = 0;
mat = 1;

for (int j = 2; j <= max_size; j++) mat[j] = mat[j - 1] + (j - 1);
for (int i = 2; i <= max_size; i++) {
for (int j = 1; j <= max_size; j++) mat[i][j] = mat[i - 1][j] + i + (j - 1);
}

int tc; cin >> tc;
while (tc--) {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
int max_sum = 0;
max_sum += mat[x1][y1];

while (x1 < x2 && y1 < y2) {
if (mat[x1 + 1][y1] > mat[x1][y1 + 1]) {
max_sum += mat[x1 + 1][y1];
x1++;
}
else if (mat[x1 + 1][y1] < mat[x1][y1 + 1]) {
max_sum += mat[x1][y1 + 1];
y1++;
}
}

while (x1 < x2) {
max_sum += mat[x1 + 1][y1];
x1++;
}
while (y1 < y2) {
max_sum += mat[x1][y1 + 1];
y1++;
}

cout << max_sum << "\n";
}

return 0;
}
``````

Can anybody tell what’s wrong with my solution? I tested it manually several times for various inputs but still it’s not getting accepted. It says Wrong Answer again and again. Please help…

``````#include <bits/stdc++.h>
using namespace std;
int a;
void solve(){
unsigned long long int ans = 0;
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int i=y1-1; i<y2-1; i++){
ans = ans + a[i][x1-1];
}
for (int i=x1-1; i<=x2-1; i++){
ans = ans + a[y2-1][i];
}
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
a = 1;
for (int i=0; i<1000; i++){
if (i > 0){
a[i] = a[i-1] + (i+1);
}
for (int j=1; j<1000; j++){
a[i][j] = a[i][j-1] + j + i;
}
}
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}``````

O(1) approach… CodeChef: Practical coding for everyone

• y is supposed to denote the columns. You’ve used it to reference rows. (and vice versa for x)
• you’re supposed to move down first, i.e from the a [min(x1,x2)] [min(y1,y2)] to a [max(x1,x2)] [min(y1,y2)] and then move right , i.e from a [max(x1,x2)] [min(y1,y2)+1] to a [max(x1,x2)] [max(y1,y2)].

I thought that we don’t need to create a matrix.  t = int(input())
for _ in range(0, t):
x1, y1, x2, y2 = map(int, input().split())
sum_d_r = []
col1 = x1
row1 = y1
col2 = x1
row2 = y2
while row1 <= y2:
num = (row1*row1)/2 + row1/2 + (col1-1)row1
if num not in sum_d_r:
sum_d_r.append(num)
row1 += 1
while col2 <= x2:
num = (col2
col2)/2 - col2/2 + (row2-1)col2 + (row2row2)/2 - row2/2 + 1
if num not in sum_d_r:
sum_d_r.append(num)
col2 += 1
a = sum(sum_d_r)
print(int(a))
I have used basic maths to create a formula to know the value in a given box. It is also passing the test cases. please tell where is the mistake.

Without matrix

#include
using namespace std;

int main()
{
int t;
scanf("%d",&t);
while(t–)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
int i,j,element=0;
for(i=1;i<=x1;i++)
{
element=element+i;
}
i–;
for(j=2;j<=y1;j++)
{
element=element+(i+j-2);
}
int sum=element;
for(i=x1+1;i<=x2;i++,x1++)
{
element=element+(x1+y1);
sum=sum+element;

``````    }
for(j=y1+1;j<=y2;j++,y1++)
{
element=element+(x2+y1-1);

sum=sum+element;

}
printf("%d\n",sum);

}
``````

}

Thanks a lot It worked. I really need to pay more attention to the problem statement now. My bad. 1 Like

We need the matrix of size itself If we somehow manage to fill it with the appropriate values. To fill the matrix with appropriate values the easy thing to do was to generate a matrix of size (2n * 2n). The editor however opted to generate some sort of formula for it.
If you try and run his code it fills the matrix of size (n*n) with the appropriate values.

Attaching SS for reference:

My question is how did the setter find the equation i*(i+1)/2. I even tried the quadratic equation to solve the problem, but he came up with such a simple equation. How?

These things usually comes up with lot of practice.Like when you start solving similar problems you start developing some trivial observations.Sometimes,I myself have wondered but with practice I think you can develop this skills