PROBLEM LINK:
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. 
