Help with "E-Bomber" from ABC 176

general
,
1

Problem: E - Bomber
My Approach: I maintain a frequency array for the x and y coordinates separately. Then I choose the x-coordinate with the maximum frequency and add it to the sum. Then I decrement the frequency of the y-coordinates with that particular x-coordinate (the one with the maximum frequency) with the help of a map which maps the y-coordinates to the x-coordinate.
CODE:

    #include <bits/stdc++.h>
    using namespace std;
     
    #define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    using ll = long long;
     
    int main() {
    	FASTIO
     
    	int h, w, m;
    	cin >> h >> w >> m;
    	
    	vector<int> freqx(h+1,0), freqy(w+1,0);
    	map<int,vector<int>> mxy;
    	
    	for(int i=0; i<m; i++) {
    		int x, y;
    		cin >> x >> y;
    		
    		freqx[x]++, freqy[y]++;
    		mxy[x].push_back(y);
    	}
    	
    	int sum = 0, maxX = 0;
    	for(int i=1; i<=h; i++) {
    		if(freqx[i] > sum) {
    			sum = freqx[i];
    			maxX = i;
    		}
    	}
    	for(int y : mxy[maxX]) {
    		freqy[y]--;  
    	}
    	
    	sum += *max_element(freqy.begin(), freqy.end());
    	
    	cout << sum << "\n";
    	
    	return 0;
    }

Problem with the code: The above code gets an AC in all of the test cases except for the 5 test cases on which it gives a WA. Can anyone please help me figure out the problem with the code?

2

Atcoder keeps its testcases public. In case you didn’t know. But since the testcases of this contest are not uploaded yet so it’s of no use rn.

Now as this problem is concerned, it had weak testcases that’s why you’re getting most of them accepted.
Your code fails on tests like
3 3 5
1 1
1 2
2 1
2 3
3 2

The correct ans will be 4 (explode 2, 2) but your code will give 3.
The counter test is taken from here and you can find more about it in comments.

1 Like