SPATH3 - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

We are given four positive integers N, M, X, Y . We need to find the minimum cost to reach the point (N, M) from (1, 1) if we can perform the following operations:

  • Go down, up, left or right for cost X.

  • Go diagonally down-left, down-right, up-right, up-left for cost Y.

QUICK EXPLANATION:

Basically we have three cases. Without loss of generality, assume N \geq M. The answer is the minimum of all of these cases:

  • Reaching (N, M) by only using the first operation.

  • Reaching the point (M,M) by only using the second operation and cover the remaining length by the first operation.

  • Reaching the point (M, M) by only using the second operation. Now we can move consecutively in the following manner whenever possible i.e, move diagonally up-right and then down-right. Whenever this is not possible, use the first operation instead.

EXPLANATION:

Without loss of generality let us assume that N \geq M. ( If it is not the case, we can swap N and M ). This helps us simplify the problem without running into too many cases to handle. We need to go through these cases sequentially, if we are going through some case, then it means all the previous cases have failed to meet their conditions.

Case 1: \hspace{1 mm} N = 1 or M = 1

  • Whenever this is the case, we can’t move diagonally and hence can only use the first operation.

  • Therefore, in this scenario the answer will be (N+M-2) \cdot X .

Case 2: \hspace{1 mm} Y \lt X

  • This condition gives us an intuition that we must use the second operation as frequently as possible.

  • This condition means that, if we want to move from point (P, Q) to any of the points (P+2, Q) , (P,Q+2), (P-2, Q), (P,Q-2), instead of using the first operation two times, we can use the second operation two times.

  • Based on this two ideas, one of the ways to construct an optimal path is to reach (N, M) in the following way: (1,1), (2,2), \dots (M,M), (M+1, M-1), (M+2, M), (M+3, M-1), (M+4, M) \dots

  • But there is a catch here. We can end at two possible states if we follow the above procedure: at (N, M) or (N, M-1). This depends on the concept of parity. Initially we start at (1,1) where both x-coordinate and y-coordinate have the same parity. Whenever we use the second operation x-coordinate increments or decrements by 1 and the same thing happens for y-coordinate as well. Thus, if N and M have the same parity, we end up at (N, M). Else we end up at (N, M-1) and we need to apply one extra first operation to reach (N,M).

  • Therefore the answer in this scenario will be (M-1+ (N-M) ) \cdot Y = (N-1) \cdot Y if the parities of N and M are same, or else the answer will be (M-1+ (N-M-1) ) \cdot Y + X = (N-2)\cdot Y +X .

Case 3: \hspace{1 mm} Y \lt 2 \cdot X

  • In this case, moving one step diagonally to some location using the second operation has less cost than moving two steps using the first operation to that same location.

  • Based on this idea, one of the ways to construct an optimal path is to reach (N, M) in the following way: (1,1), (2,2), \dots (M,M), (M+1, M), (M+2, M), (M+3, M), (M+4, M) \dots

  • Therefore the answer in this scenario will be (M-1) \cdot Y + (N-M) \cdot X.

Case 4: \hspace{1 mm} Y \geq 2 \cdot X

  • In this case, we need to use operations of the first type and reach (N, M) since any operation of the second type is costlier than the operation of the first type.
  • Therefore the answer in this scenario will be (N+M-2) \cdot X.

TIME COMPLEXITY:

O(1) for each testcase.

SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
#define int long long int
#define endl "\n"
using namespace std;

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

    int tests;
    cin >> tests;
    while (tests--)
    {
        int n, m, x, y;
        cin >> n >> m >> x >> y;
        if (n < m)
            swap(n, m);

        if (n == 1 || m == 1)
        {
            cout << (n + m - 2) * x << endl;
        }
        else if (y < x)
        {
            if (n % 2 == m % 2)
                cout << (n - 1) * y << endl;
            else
                cout << (n - 2) * y + x << endl;
        }
        else if (y < 2 * x)
        {
            cout << (m - 1) * y + (n - m) * x << endl;
        }
        else
        {
            cout << (n + m - 2) * x << endl;
        }
    }
    return 0;
}
Setter's solution
#include <bits/stdc++.h>
#define int long long
//#include <sys/resource.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
using namespace std;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--) {
        int n, m, x, y;
        cin >> n >> m >> x >> y;
        if (n > m) swap(n, m);
        int diff = m - n;
        int ans = (n + m - 2) * x; //if x*2 < y
        ans = min(ans, (y * (n-1)) + (diff * x)); //if x<y
        ans = min(ans, (y *(n-1)) + ((diff / 2) * 2) * y + (diff % 2) * x);
        cout << ans << '\n';
    }
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    ll n, m, x, y;
    cin>>n>>m>>x>>y;
    ll ans = (n + m - 2) * x;
    ll q = min(n - 1, m - 1);
    ll w = (n + m - 2) - 2 * q;
    ll a = q * y + w * x;
    ll b = q * y + 2 * (w / 2) * y + (w % 2) * x;
    ans = min(ans, min(a, b));
    cout<<ans<<"\n";
  }
  return 0;
}

Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

1 Like

ans = (n+m-2)x // y>=2x
ans = (n+m-2)x + i(y-2x)// y>2x and i = min(n,m)-1
Ye solun kaam kyu nhi kar rha hai :upside_down_face:

2 Likes

Anyone please tell, why my solution is wrong??
https://www.codechef.com/viewsolution/51454269

Also, can someone please explain why using int instead of long long for x, y, n, m gives TLE?
Should give WA or something that I understand, why TLE?

2 Likes

I was trying to use Dijkstra’s and it was giving segmentation error. Is there a reason or was I doing some silly mistake. Has anyone done this using Dijkstra?

1 Like

I understood all the cases but i m confused with case 2 where y<x. Can any one explain with some good example or please help me find some examples.

Let’s consider a corner case when Y=0. In this case any diagonal movements are absolutely free. And if we paint the grid in a checkerboard pattern, then it’s easy to see that it’s possible to move from any white cell to any other white cell (or from any black cell to any other black cell) by only doing diagonal movements. If the (1,1) cell and the (N,M) cell have the same color, then the answer is 0. If not, then the answer is X.

If Y is not zero, but still much smaller than X, then a similar logic still applies. And that’s what the case 2 from the editorial is all about.

Try using fast I-O methods as the judge will declare it a TLE if the inputs are too big.

1 Like

Can you provide a link to that submission?

https://www.codechef.com/viewsolution/51471394
This one is giving TLE, some others gave WA

use fast input output method

ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

inputs are huge , use above code
or you can use printf() and scanf() of C

I guess because of the constraints the 2D array could not be declared.

I solved the question with 2D dp array but the constraints on n and m were 10^6 due to which the dp array could not be made. Therefore it was working for small inputs but for large inputs it failed due to space complexity of (n*m).

why dfs wont work here?

1 Like

Why should it work?

2 Likes