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!
Thank you.
I just checked that x denoted the row, not column. Why, why, and I wasted so much time man.
Still buddy, thanks a lot.
I used three different approaches for this quesion in python:
All three solutions are accepted:
(i)
for _ in range(int(input())):
x1,y1,x2,y2 = map(int,input().split())
x1-=1
y1-=1
x2-=1
y2-=1
summ = 1
cnt = 2
for i in range(x1):
summ += cnt
cnt += 1
cnt -= 1
for i in range(y1):
summ += cnt
cnt += 1
cnt += 1
ans = summ
for i in range(x1+1,x2+1):
summ += cnt
ans += summ
cnt += 1
cnt -=1
for i in range(y1+1,y2+1):
summ += cnt
ans += summ
cnt += 1
print(ans)
(ii)
arr = [[i+1 for i in range(1000)] for j in range(1000)]
for i in range(1,1000):
arr[0][i] = arr[0][i-1] + (i)
for i in range(1,1000):
for j in range(1000):
arr[i][j] = arr[i-1][j] + (i+j+1)
for _ in range(int(input())):
x1,y1,x2,y2 = map(int,input().split())
x1-=1
y1-=1
x2-=1
y2-=1
summ = 0
for i in range(x1,x2+1):
summ += arr[i][y1]
for i in range(y1+1,y2+1):
summ += arr[x2][i]
print(summ)
(iii)
dic = {n:((n*(n+1))//2) for n in range(10001)}
def find(x,y):
global dic
ans = 0
ans += dic[x]
ans += (dic[x+y-2] - dic[x-1])
return ans
for _ in range(int(input())):
x1,y1,x2,y2 = map(int,input().split())
ans= 0
for i in range(x1,x2+1):
ans += find(i,y1)
for i in range(y1+1,y2+1):
ans += find(x2,i)
print(ans)
Okkk got it
Why am I getting WA? I have pre-computed the array
`#include
using namespace std;
int main() {
int arr[2000][2000], i, j;
arr[0][0] = 1;
for(i=1; i<2000; i++){
arr[i][0] = arr[i-1][0] + i;
}
for(j=1; j<2000; j++){
arr[0][j] = arr[1][j-1] + 1;
for(i=1; i<2000; i++){
arr[i][j] = arr[i-1][j] + i + j;
}
}
int t, x1, y1, x2, y2, sum;
cin >> t;
while(t--){
sum = 0;
cin >> x1 >> y1 >> x2 >> y2;
for(j=y1-1; j<y2; j++){
sum += arr[x1-1][j];
}
for(i=x1; i<x2; i++){
sum += arr[i][y2-1];
}
cout << sum << '\n';
}
return 0;
}
`
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[1005][1005];
memset(a,0,sizeof(a));
a[1][1]=1;
for(int i=2;i<=1003;i++)
{
a[i][1]=a[i-1][1]+(i-1);
}
for(int j=2;j<=1003;j++)
{
a[1][j]=a[1][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];
// cout<<"added "<<a[x1][y1]<<endl;
x1++;
if(x1==x2)
{
summ+=a[x1][y1];
// cout<<"added "<<a[x1][y1]<<endl;
break;
}
}
}
else
{
while(1)
{
summ+=a[x1][y1];
// cout<<"added "<<a[x1][y1]<<endl;
y1++;
if(y1==y2)
{
summ+=a[x1][y1];
// cout<<"added "<<a[x1][y1]<<endl;
break;
}
}
if(x1==x2)
{
cout<<summ<<endl;
continue;
}
while(1)
{
x1++;
summ+=a[x1][y1];
// cout<<"added "<<a[x1][y1]<<endl;
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] = 0;
for (int j = 0; j <= max_size; j++) mat[0][j] = 0;
mat[1][1] = 1;
for (int j = 2; j <= max_size; j++) mat[1][j] = mat[1][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[1000][1000];
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[0][0] = 1;
for (int i=0; i<1000; i++){
if (i > 0){
a[i][0] = a[i-1][0] + (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;
}- 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 = (col2col2)/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.