TLAPM - Editorial

editorial
, , ,
8

Can someone plz help me with this code . I’m getting WA on this code but when I change the size of the array a to a[2005][2005] then this code works

ll a[1005][1005];

void precalc(){

ll cnt = 1; 
for(int j=0;j<1005;j++){
    int i = 0; 
    for(int k = j;k>=0;k--){
        a[i][k] = cnt; 
        cnt++; 
        i++; 

    }
}

}

void solve()
{
ll x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;

ll sum = 0; 

for(int i=x1;i<=x2;i++){
    sum+=a[i-1][y1-1]; 
}

for(int j=y1+1;j<=y2;j++){
    sum+=a[x2-1][j-1]; 
}
cout<<sum;

}

int main()
{

fast;
ll t;
// t = 1;
cin>>t;
precalc();
while(t–)
{
solve();
cout<<endl;
}

}

9

I did it by first precomputing the matrix and then I used minimum path sum to find the sum

10

Yeah, I guess it should be marked which direction is which. From the problem statement it is not clear. In the problem the x direction goes from top to bottom and the y-direction from left to right which is not what one might expect especially if one is used to the standard Euclidean coordinate system.

Apart from that it was a nice problem :slight_smile:

11

what is wrong in my solution?
I have first of all calculated each cell value by following process:
row head as first cell of row 1.
as nth term in first row can be calculated as
Tn=1+T1+T2+T3+ …+ Tn-1
=>Tn=1+1+2+3+…+(N-1)
=>Tn=1+ x*(x-1)/2 //x=n

and similarly then nth term in that colomn using row_head
as
T1=row_head
T2=T1+x+1=row_head+x+1
T3=T2+x+1+1=row_head+(x+1)+1
…
…
…
Ty=row_head+(y-1)(x+1)+(y-2)(y-1)/2 //this is our cell value;

and then in main i use cellvalue to get path reach x2,y2.
help…

my code------------------------------------------------

#include

using namespace std;
int cellval(int x,int y)
{
int row_head; //first cell of each row
ro_head=1+x*(x-1)/2;
return row_head+(y-1)(x+1)+((y-2)(y-1))/2;
}
int main()
{
int t,al;
cin>>t;
while(t–)
{
int x1,y1,x2,y2;
bool flag=1;
long sum;
cin>>x1>>y1>>x2>>y2;
sum=cellval(x1,y1);
while(x1!=x2||y1!=y2)
{
if(x1==x2)
{
y1++;
sum=sum+cellval(x1,y1);
}
else if(y1==y2)
{
x1++;
sum=sum+cellval(x1,y1);
}

        else
        {
            int z1=cellval(x1+1,y1);        //right vale
            int z2=cellval(x1,y1+1);        //down value

            if(z1>z2)
            {
                x1++;
                sum=sum+cellval(x1,y1);
            }

            else
            {
                y1++;
                sum=sum+cellval(x1,y1);
            }

        }
    }

cout<<sum<<endl;

}
return 0;
}

[https://www.codechef.com/viewsolution/46834244](https://www.codechef.com/viewsolution/46834244)
12

Yeah a[1000][1000] won’t work because if you think logically like if you make the matrix of a[3][3]

Blockquote
1 2 4
3 5
6

indexing for them is like (1 - based )

Blockquote
11 12 13
21 22 23
31 32 33

if i ask you accordingly now what’s value a a[3][3] ? i.e. is nothing you can see in the first matrix
so for a[1000][1000] you have to make it a[2000][2000] cz then a[1000][1000] = 0

Hope you understand now! :slight_smile:

13

If we consider the size of the matrix to be (3 * 3) it will of the form:
1 2 4
3 5 0
6 0 0
and trying to build a (3 * 3) matrix completely would result in something of the form:
1 2 4
3 5 7
6 8 9
Which has 9 at index (3,3) while it should have been 13,which will obviously result into WA.

14

got AC but can anybody tell me why my answer is not giving TLE?

   void solve() {   
   int x1,y1,x2,y2;
   cin>>x1>>y1>>x2>>y2;

   int xcurr = 1;
   int ycurr = 1;
   int val_1 = 1;
   int ans;
   int curr_val=1;
   int xadd = 2;
   
    while(xcurr!=x1){
        val_1+=xadd;
        xadd++;
        xcurr++;
    }   
    int yadd = x1;
    while(ycurr!=y1){
        val_1+=yadd;
        yadd++;
        ycurr++;
    }
    
    
    xcurr = x1;
    ycurr = y1;
    ans = val_1;
    curr_val = val_1;
    xadd = x1+y1;
    
    while(xcurr!=x2){
        curr_val+=xadd;
        ans+=curr_val;
        xadd++;
        xcurr++;
    }   
    xadd--;
    
    yadd = x2+y1-1;
    while(ycurr!=y2){
    //    cout<<curr_val<<" "<<ans<<endl;
        curr_val+=yadd;
        ans+=curr_val;
        yadd++;
        ycurr++;
    }
     cout<<ans;
     return; 
      }
15

Guys, I did my code but was getting WA again and again and cause i took the array size as [1005][1005], which should not give any error, idk why it was giving WA but when i increased my array size to [3005][3005],it was working fine how is this possible?
I don’t understand this, is the question statement wrong?
ll arr[1005][1005];
void calc()
{
ll i=0;
ll count=1;
for(int j=0;j<1005;j++)
{
ll k=j;
i=0;
while(i<1005 && k>=0)
{
arr[i][k]=count;
count++;
k–;
i++;
}
}
}
With this array, my code gives WA and if I just increase the size of array, it gives AC
Can someone tell me what is wrong here?

16

What am I doing wrong here, I checked a few possible outputs using the correct solutions and I m getting the same result, but code is not being accepted.

def value(m,n):
ans = ((m**2 - m +2) / 2) + (m*(n-1)) + (n*(n-1))/2
return int(ans)

t = int(input())
while t != 0:

x1,y1,x2,y2 = [int(x) for x in input().split()]
sum = 0
for i in range(0,y2-y1+1):
    sum += value(x1,y1+i)
for i in range(1,x2-x1+1):
    sum += value(x1+i,y2)
print(sum)
t = t-1
17

thanks a lot now I understand :slight_smile:

18

Thanks , i got it

1 Like
19

https://www.codechef.com/viewsolution/46836715
Can Anyone help me to find why my code is giving the wrong answer?

I didn’t precompute entire matrix but precompute target row.

static void findAns(int row, int column, int trow, int tcolumn)
	{
	    int rightMove[] = new int[tcolumn];
	    
	    int sum = 0 ; 
	    int moveDown = 0;
	    while(row != trow)
	    {
	        moveDown += row * (row+1)/2;
	        row++;
	    }
	    
	    rightMove[0] = trow * (trow +1)/2;
	    
	    int moveRight = rightMove[0];
	    
	    for(int i = 1; i < tcolumn ; i++)
	    {
	        rightMove[i] = rightMove[i-1] + trow-1 + i;
	        moveRight += rightMove[i];
	    }
	    
	    System.out.println(moveRight+moveDown);
	}
20

can anyone help me find out what’s wrong in my code

#include <bits/stdc++.h>
#define pi 3.14159265358979323846
#define P 1000000007
using namespace std;
typedef long long ll;



long long arr[1000][1000];
void fxn()
{

  long long temp=1;
   for (int i=0;i<1000;i++)
   {
      arr[0][i]=temp;
      long long k=i;
      long long  p=0;
      temp++;
      while(k>0)
      {
         
         k--;
         p++;
         arr[p][k]=temp;
         temp++;
        
      }
   }
}

void solve()
{
   ll x1,y1,x2,y2;
   cin>>x1>>y1>>x2>>y2;
   ll ans{0};
   
   x1--;
   x2--;
   y2--;
   y1--;

   if(x1==x2 && y1==y2)
   {
      cout<<arr[x1][y1]<<"\n";
      return;
   }
    for (int i=x1;i<=x2;i++)
     {
      
        ans+=(arr[i][y1]);
     }
     for(int i=y1+1;i<=y2;i++)
     {
       
        ans+=(arr[x2][i]);
     }
     cout<<ans<<"\n";
     return;
 
       
}





int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);
    fxn();
   /*for (int i=0;i<8;i++)
   {
      for (int j=0;j<10;j++) cout<<arr[i][j]<<" ";
      cout<<"\n";
   }*/
   ll t;
   cin>>t;
  
   
   while (t--)
   {
       solve();
   }


   return 0;
}
21

I want to ask if we create the matrix with the values in the same order and then we calculate sum by moving down and then right. Is this approach right or wrong?

22

pre-computing function run total operation 10^3*10^3 = 10^6
and we have time limit of 0.5 mean we can run only 10^4 operation approx.
so why not we are getting tle by precomputing the matrix?

23

Have a look on setters code ant the way he had made the matrix , I think it could be made like that

24

vvll mat;

void precompute()

{

ll v = 1;

fo(i, 0, 2000)

{

    ll x = 0;

    ll y = i;

    while (x <= 2000 && y >= 0)

    {

        mat[x][y] = v++;

        x++;

        y--;

    }

}

}

void solve()

{

ll x1, x2, y1, y2, ans = 0;

cin >> x1 >> y1 >> x2 >> y2;

x1--, y1--, x2--, y2--;

fo(x, x1, x2)

{

    ans += mat[x][y1];

}

fo(y, y1 + 1, y2)

{

    ans += mat[x2][y];

}

cout << ans << ln;

}
what is wrong in this code?

25

https://www.codechef.com/viewsolution/46841152
why i am getting tle

26

Online judge does approx 10^8 operations in 1 second . So for 0.5 seconds it takes 5*10^7 ops which is more than our matrix precomputing function(10^6). That’s why we are not getting a TLE.

27

Can someone help me with my code

I precomputed matrix. When matrix size is a[1000][1000] answer is wrong but on a[1001][1000] it’s correct .How ?

Code–

#include<bits/stdc++.h>
#define ll unsigned long long int
#define mod 1000000007

using namespace std;

int main() {

int t;
cin>>t;

ll a[1000][1000];

a[0][0]=1;
ll d1=1,d2=1;
for(int i=0;i<1000;i++)
{
if(i>0){a[i][0] +=a[i-1][0]+d1;}

for(int j=1;j<1000;j++)
{
 a[i][j]  +=a[i][j-1]+d2;
 d2++;
}
d1++;
d2=d1;

}

while(t–)
{
int x1,y1,x2,y2;

cin>>x1>>y1>>x2>>y2;

ll val=0;
x1–; y1–;x2–;y2–;

for(int i=x1;i<=x2;i++)val +=a[i][y1];

for(int j=y1+1;j<=y2;j++)val +=a[x2][j];

cout<<val<<endl;

}

return 0;
}