CHECHOC WA

My logic for CHECHOC:
Notice that we can divide each matrix into sub-matrices of size 2 x 1.
And each sub-matrix can have a maximum sum = min(2*x, y).
In case of odd m and n, a 1 x 1 matrix is left whose maximum sum can be min(x, y) .
This approach gives a WA. Can someone please provide a countercase?
@aneee004 @therealnishuz

#include <bits/stdc++.h>
#define vi vector<int>
#define pi pair<int, int>
#define vs vector<string>
#define ll long long int
#define pb push_back
#define mod 1000000007
#define INF 1e9
#define f first
#define s second

using namespace std;

int 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;
		ll ans = 0;
		if(m%2 == 0 || n%2 == 0) cout << ((m*n)/2)*min(2*x, y);
		else{
            cout << ((n*m)/2)*min(2*x, y) + min(x, y);
		}
    }
	return 0;
}

Yeah, totally forgot to handle the edge case.

Cost me a 100…

1 Like

same

@flash_0408

Really sorry. My approach is literally the same but I still got WA. And I passed this test case :sob:

1 Like

Why is it 9? Shouldn’t it be 10? in 1x1 matrix case, there is no adjacent sides so there’s no sum, the single cell can take maximum value

1 Like

Consider test case : 1 1 11 7
For this case, there are no adjacent cells in the 1x1 matrix. So, the cell can hold the value of x even if it exceeds ‘y’. This is the only corner case due to which many must have got WA.

1 Like

That was brutal

how is it correct when sum cant exceed y

actually do two things, check for 1x1 and y<x conditions.

This edge case has ruined more lives than COVID-19.

4 Likes

you are give a constraint for individual cells and a constraint for pairs of cells. When you only have one cell, there are no pairs, so the second condition doesn’t apply to anything.

2 Likes

I don’t really think this 1x1 was an edge case tbh. It was more of an ambiguous problem statement. Like I had already thought of this case but kept it because even though there are no adjacent cells, still it does count as a cell in the sum of two adjacent cells. The problem setters could have even done the opposite for this 1x1 matrix and would call it an edge case lol.

1 Like

I would’ve been in div 1 if I didn’t mess it up (although I can’t survive there XD)

1 Like