The last problem may cook off 2021

general
1

i have made the 2d array by going from top to bottom of diagonal , checked it with multiple test cases my answer is coming out to be correct can someone please help me by telling where i am going wrong

#include <bits/stdc++.h>
#define int long long
using namespace std;

int helper(int **arr, int m, int n, int x, int y)
{
int ans=0;

int i;
for(i=x;i<m;i++)
{
    ans=ans+arr[i][y];
}


int k=ans;
for(int j=y+1;j<n;j++)
{
    ans=ans+arr[m-1][j];
}

return ans;

}

signed main()
{
// boost
int t;
cin>>t;
int r=1005;
int c=1005;
int**arr=new int*[r];
for(int i=0;i<r;i++)
{
arr[i]=new int[c];
}

// filling till last col of 1st row

  arr[0][0]=1;
  int k=2;
for(int i=1;i<c;i++)
{
    int k1=0;
    int k2=i;
    while(k1>=0 and k2>=0 and k1<r and k2<c)
    {
        arr[k1][k2]=k++;
        k1++;
        k2--;
    }
    
}

// filling from 1st row last index

for(int i=1;i<r;i++)
{
    int k1=i;
    int k2=c-1;
     while(k1>=0 and k2>=0 and k1<r and k2<c)
    {
        arr[k1][k2]=k++;
        k1++;
        k2--;
    }
}


while(t--)
{
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    cout<<helper(arr,x2,y2,x1-1,y1-1)<<endl;
    
}

}

2

try changing the approach by checking for the infinite matrix instead of traversing diagonally.

3

you are not actually filling the array correctly. as the cell (1000,1000) is also affected by cell (0,2000) as you are filling diagonally. Try increasing your array size and filling it.

Or, you can fill it like I’ve done here CodeChef: Practical coding for everyone
There was a relation between the elements directly, so need to fill diagonally.

4

thanks a lot man really appreciate ur efforts
i overlooked the fact that 0,2000 is going to affect 1000,1000
made it finally :- CodeChef: Practical coding for everyone
thanks bro for helping out

1 Like