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?
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-1thanks a lot now I understand 
Thanks , i got it
1 Like
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);
}
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;
}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?
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?
Have a look on setters code ant the way he had made the matrix , I think it could be made like that
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?
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.
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;
}
Feedback for this problem-
You should have given the matrix or in the problem statement, it should be stated that how the matrix will be created. Yes, it’s quite clearly visible that elements are diagonally increasing, but how do we come to the conclusion that the rest of the values will have the same sequence?
This is not an aptitude problem, this is a programming problem, right?
If I am wrong in stating my feedback, please do correct me!
Thanks a lot…
In contest I was able to figure out logic but was creating arr size 1000
I know this question was easy, and if I had generated the matrix, it would have been much easier. I also used the same strategy, go down first, and then right. But maybe I didn’t calculated the value of grid correctly.
int val(int x, int y) {
int d = y * (y + 1) / 2;
int r = (x + 2 * (y - 1)) * (x - 1) / 2;
return r + d;
}
I don’t know why this isn’t working. This function was giving correct value for small x and y. Here y is depth and x is left-right distance. I generated this formula, and checked it many times. I am sure I calculated it correctly. Still, I get wrong answer on submission.
Please just look into this once, CodeChef: Practical coding for everyone
Even though I thought I should have used some different strategy, I just couldn’t bring myself to question what I did wrong in my calculation. Really, first problem can make or break your contest.
Your code fails in the following test cases (there are many such).
2 3 2 6
1 7 10 7
6 10 8 10
7 3 10 10
1 1 4 5
3 7 4 9
5 9 7 9
6 2 7 6
4 9 5 10
3 5 10 9
Edit: According to your algo, the way you’re reading input is wrong.
The following changes worked.
cin >> y1 >> x1 >> y2 >> x2;
My solution runtime 0.0 second and space complexity O(x+y)
#include
using namespace std;
int main() {
int t;
cin>>t;
while(t–)
{
int a,b,x,y;
cin>>a>>b>>x>>y;
int arr[x+y];
for(int i=a+b-1;i<=x+y-1;i++)
arr[i]=((i+1)*(i))/2;
int sum=0;
for(int i=a;i<=x;i++)
sum+=(arr[i+b-1]-b+1);
for(int j=b+1;j<=y;j++)
sum+=(arr[x+j-1]-j+1);
cout<<sum<<endl;
}
return 0;
}
To understand what is wrong with your code, you should try printing your matrix created from i = 990 to i = 1000. You need to pre - compute the values upto 2000, and not just 1000.
There is also another small error, if x1 == x2 and y1 == y2, the answer will be 2*arr[x1][y1], because we have to include both the starting point as well as the end point of the path.
Link to submission after making changes to your code : CodeChef: Practical coding for everyone
Hope I helped!