CHECHOC - Editorial

PROBLEM LINK:

Contest

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

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

Missed the base case (all the time ):slight_smile: .

16 Likes

1*1 case costed me 100 points.

37 Likes

guys i have tried explaining but went really fast, so first read the question and then watch(if you still dont get it) (0.00 sec solution)
English Explanation
Hindi Explaination

10 Likes

best explanation

1 Like

I am getting correct outputs during dry run but shows WA when I submit it. Can you please tell me what’s wrong.
https://www.codechef.com/viewsolution/36019737

This submission gets ac : CodeChef: Practical coding for everyone
But This doesnt get ac: CodeChef: Practical coding for everyone

The question clearly says sum cant be greater than y, Then how is the second one not ac

The minimum of x and y should have gotten ac, if(x>y) then answer is y or else x, But Second link gives WA
pls correct me if i am wrong

2 Likes

yeah same with me. In luchtime also just because of a base case my solution wasn’t accepted. :frowning:

2 Likes

Can anyone tell me what’s wrong with my solution?
https://www.codechef.com/viewsolution/36018600

Can anyone give me a counter example for this submission?

Can anyone help with my code?
https://www.codechef.com/viewsolution/35986525

Is there a way we can see the test case used during the contest? This problem gave me a hard time, haha.

2 Likes

When n==m==1 then answer is always x, you should use all you can because it has no adjacent pairs

14 Likes

Please tell me what’s wrong in my code?
https://www.codechef.com/viewsolution/36012029

Why does a brute-force like this fail? i think all cases are covered.
Link

The problem except the base case(n=1)?
https://www.codechef.com/viewsolution/35986231

nice editorials

1 Like

@tengiz05, you just made me realize why my code wasn’t working. :frowning: I was outputting the minimum of (y, x) for n == m == 1.

3 Likes

Sorry it can’t be make public I guess.

Very noice editorial

1 Like