# TLAPM - Editorial

Setter: Deepak Prajapati
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

Cakewalk

# PREREQUISITES

None, prefix sums might be helpful.

# PROBLEM

Given an infinite matrix, whose values are filled in the following manner.

Among all paths from cell (x_1, y_1) to (x_2, y_2) by only moving right or down, find the value of the path with maximum value, where the value of a path is the sum of values of cells on the path including starting and ending cell.

# QUICK EXPLANATION

• The optimal path is to move downwards from (x_1, y_1) to (x_2, y_1) and then from (x_2, y_1) to (x_2, y_2).
• The values of vertical and horizontal paths can be computed by precomputing the prefix sums of each row and column.

# EXPLANATION

Assume we have already generated the matrix, V_{i, j} denoting the value of cell (i, j).

### Figuring out Optimal Path

Let’s figure out how this matrix is generated. The values are filled diagonal-wise, and each diagonal is filled from top to bottom. We are going to use the second fact.

`````` 1  2  4  7 11
3  5  8 12
6  9 13
10 14
15
``````

Let’s consider a path from cell (1, 1) to cell (3, 3) and consider all paths.

• (1,1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3) with value 28
• (1,1) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3) with value 29
• (1,1) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3) with value 30
• (1,1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) with value 30
• (1,1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3) with value 31
• (1,1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) with value 32

As you may already have guessed, the optimal path moves all downward moves first, and then all right moves.

Let’s denote the sequence of moves by characters ‘R’ denoting the right move and ‘D’ denoting the downward move.

Claim: In optimal move sequence, there are no two consecutive moves where the first move is a right move and the second move is a down move. That means, `RD` doesn’t appear in the move sequence.
Proof: Let’s assume we are at cell (x, y) and the next two moves are `RD` in this order. The path would look like (x, y) -> (x, y+1) -> (x+1, y+1). We can see that we can replace this sequence with `DR`, resulting in path (x, y) -> (x+1, y) -> (x+1, y+1). Let’s compare their values.

Cell (x, y) and (x+1, y+1) appear in both sequences, so their weight doesn’t matter. We only need to compare V_{x, y+1} and V_{x+1, y}. As a matter of fact, they lie on the same diagonal. Specifically, while constructing matrix, cell (x, y+1) is filled first, immediately followed by cell (x+1, y). Hence, the V_{x+1, y} = 1+V_{x, y+1}

Hence, in the move sequence, if there appears any occurrence of moves `RD`, we can swap moves to obtain `DR`. We keep doing this until there’s no occurrence of `RD` in the move sequence. The move sequence becomes DDD \ldots DDRR \ldots RR, all down moves followed by all right moves.

### Computing the value of the path

Constraints are small enough to iterate moving from cell (x_1, y_1) to (x_2, y_1) and then to (x_2, y_2) and adding up their values. Setter’s solution does this.

Alternatively, you may use prefix sums for each row and column to answer test cases in O(1) time. You may read more on prefix sums here, or refer to my implementation below.

Implementation Error to avoid: Generate the matrix of size 2000 instead of 1000, since value at cell (1000, 1000) is impacted by cells outside 1000*1000 matrix.

# TIME COMPLEXITY

The time complexity is O(MAX^2+T) or O(MAX^2+T*MAX) where MAX = 2000 depending upon implementation.

# SOLUTIONS

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;
int matrix;

void infiniteMatrix()
{
for(int i = 1;  i <= 1000;  i++)
{
matrix[i] = i * (i+1)/2;
for(int j = 2;  j <= 1000;  j++)
{
matrix[i][j] = matrix[i][j-1] + (j - 1) + (i - 1);
}
}
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

infiniteMatrix();

int t;
cin >> t;
while(t--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;

int sum = 0;
for(int i = x1;  i <= x2;  i++)
{
sum += matrix[i][y1];
}
for(int i = y1+1;  i <= y2;  i++)
{
sum += matrix[x2][i];
}

cout << sum << "\n";
}
}
``````
Tester's Solution
``````#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
//assert(false);
}
}
}

string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif

const int maxV = 1002;
vector<vector<int>> v(maxV, vector<int>(maxV));
forn(i, maxV)
{
v[i] = i ? v[i - 1] + i : 1;
fore(j, 1, maxV-1)
{
v[i][j] = v[i][j - 1] + i + j + 1;
}
}

vector<vector<int>> dp(1000, vector<int>(1000));

forn(tc, T)
{
--y1, --x1, --y2, --x2;
dp[y1][x1] = v[y1][x1];

fore(i, y1, y2)
{
fore(j, x1, x2)
{
if (i != y1)
{
dp[i][j] = dp[i - 1][j] + v[i][j];
if (j != x1)
dp[i][j] = max(dp[i][j - 1] + v[i][j], dp[i][j]);
}
else if(j != x1)
dp[i][j] = dp[i][j-1] + v[i][j];
}
}
printf("%d\n", dp[y2][x2]);
}
assert(getchar() == -1);
return 0;
}
``````
Editorialist's Solution
``````import java.util.*;
import java.io.*;
class TLAPM{
//SOLUTION BEGIN
int max = 2000;
int[][] mat, row = new int[1+max][1+max], col = new int[1+max][1+max];
void pre() throws Exception{
mat = new int[1+max][1+max];
for(int d = 2, val = 1; d <= 2*max; d++){
for(int r = 1; r < d; r++, val++){
int c = d-r;
if(Math.min(r, c) >= 1 && Math.max(r, c) <= max){
mat[r][c] = val;
row[r][c] = row[r][c-1]+mat[r][c];
col[r][c] = col[r-1][c]+mat[r][c];
}
}
}
}
void solve(int TC) throws Exception{
int x1 = ni(), y1 = ni(), x2 = ni(), y2 = ni();
int ans = col[x2][y1]-col[x1-1][y1]+row[x2][y2]-row[x2][y1];
pn(ans);
}

//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new TLAPM().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
``````

Feel free to share your approach. Suggestions are welcomed as always. 2 Likes

How do we know that moving right will increase y by 1 and not x?

1 Like

becasue when we are are at cell (x,y) we can go in (x,y+1) (right-as x being the level/height is same and we are simply going forward) or (x+1,y)(down-we are changing the level/height and do not move anywhere else in this move)

1 Like

Wish I had used common sense and not ended up interpreting x and y as x-axis and y-axis in the contest.

4 Likes

Can’t understand the reason of this line , can you please explain it a bit more , I am saying this because as much as I can see , the value of mat[r][c] is calculated by mat[r][c-1] , so why not take maxn as 1000

No need to generate a matrix…

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
long long int digit;
digit = x1*(x1+1)/2 + (x1+y1-2)(x1 + y1 - 1)/2 -
(x1-1)
(x1)/2;
long long int sum = digit;
for(int i = 0;i<(x2-x1);i++){

``````    digit = digit + y1+ x1 + i;
sum+=digit;
}

for(int i=0;i<(y2-y1);i++){
digit  = digit + x2+y1-1+i;
sum = sum + digit;
}

cout<<sum<<endl;

}
``````

}

11 Likes

Let M be the given matrix.
Upon observation , we get M[x][y] = {x*(x+1)}/2 + (y-1)x + {(y-2)(y-1)}/2; 9 Likes

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 then this code works

ll a;

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;
}

}

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

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 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

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
}
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)``

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

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 ? i.e. is nothing you can see in the first matrix
so for a you have to make it a cz then a = 0

Hope you understand now! 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.

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;

while(xcurr!=x1){
xcurr++;
}
while(ycurr!=y1){
ycurr++;
}

xcurr = x1;
ycurr = y1;
ans = val_1;
curr_val = val_1;

while(xcurr!=x2){
ans+=curr_val;
xcurr++;
}

while(ycurr!=y2){
//    cout<<curr_val<<" "<<ans<<endl;
ans+=curr_val;
ycurr++;
}
cout<<ans;
return;
}``````

Guys, I did my code but was getting WA again and again and cause i took the array size as , which should not give any error, idk why it was giving WA but when i increased my array size to ,it was working fine how is this possible?
I don’t understand this, is the question statement wrong?
ll arr;
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-1``````

thanks 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 = trow * (trow +1)/2;

int moveRight = rightMove;

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;
void fxn()
{

long long temp=1;
for (int i=0;i<1000;i++)
{
arr[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;
}``````