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.
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[1000][1000] 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
Ok thanks for the reply,