PROBLEM LINK:
Setter: Aman Dwivedi
Tester: Yash Chandnani
Editorialist: Rajarshi Basu
DIFFICULTY:
Easy
PREREQUISITES:
Math, Implementation
PROBLEM:
You need to fill the matrix with candies in such a way that:
- For each cell, the number of candies in this cell is an integer between 0 and X inclusive.
- For each pair of adjacent cells, the number of candies in one cell plus the number of candies in the other cell does not exceed Y. Two cells are considered adjacent if they share a side.
Find the maximum number of candies you can place in the given matrix.
Constraints
- 1 \le T \le 100
- 1 \le N, M \le 100
- 1 \le X, Y \le 10^4
EXPLANATION:
Some initial thoughts
Since we are only talking about restrictions on the adjacent cells, it makes sense that there is a lot of symmetry and we probably won’t need advanced techniques to assign weights.
Taking Some Examples
2D things are obviously harder to deal with than linear arrays, so why not start with something 1-dimensional? How about the case of a 1 \times 3 matrix? Let’s try to intuitively figure out what we can do. One possible, and somewhat immediate approach would be, to place \frac{Y}{2} on all the cells. Here I am assuming that x \leq y \leq 2x. However, is this the best we can do?
Making the solution better
It should be clear from the previous example that if you decrease the middle position by 1, then you can increase the left and right position by 1, so overall increasing the sum by 1. Try generalising this to larger matrics.
Main Idea
We tried with a matrix of size 1 \times 3. Now, let’s try to see for larger 1D arrays. It should be clear that for larger sized arrays, we fill the odd positions (1,3,5…) with higher values and the even ones(2,4,6…) with lower values. If ever we can decrease the even values and increase the odd values, we do that. Since there are atleast as many odd cells as even ones, we are guaranteed to not decrease our sum.
We take this same idea to the next level by seeing how this relates to 2D matrices. Just replicating this for all rows is not enough since we also need to take care of columns. Essentially our idea was that in every two adjacent cells, we kindof “color’ them with different colors - here colors essentially means different values. We can 2-color 1D arrays. Can we do the same with 2D matrices? YES ! The checkerboard pattern ! We place higher values on black cells of a checkerboard, and lower values on white cells. Note that I am assuming that atleast 1 corner is black. Think why this is needed. (Hint: We want to maximise the places where we place higher values, ie black cells).
2+2=4-1+3 Quick Maths
How to find the exact formula? Here is some quick Maths:
- First, set X = min(X,Y) and Y = min(2x,Y).
- Answer: \frac{n*m+1}{2}*x+\frac{n*m}{2}*(y-x).
- The first term corresponds to black squares, the second to white squares.
TricKKK : There’s an edge case
Well, don’t forget to handle the case of 1 \times 1
SOLUTIONS
Tester’s Code
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void pre(){
}
void solve(){
int n,m,x,y;cin>>n>>m>>x>>y;
assert(n>=1&&n<=100);
assert(m>=1&&m<=100);
assert(x>=1&&y<=10000);
assert(y>=1&&x<=10000);
if(n*m>1) x=min(x,y);
y=min(y,2*x);
cout<<(n*m+1)/2*x+(n*m)/2*(y-x)<<'\n';
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int n;cin>>n;
assert(n>=1&&n<=100);
rep(i,n) solve();
return 0;
}