CodeChef October Challenge 2013 Editorial [Kamehameha]

Problem: Kamehameha
You are given cell position (row and column) of demons in 2D grid. In a single attack you can kill all demons in a row or in a column. You have to print minimum number of attack needed to kill all the demons.

Observation: number of demons <=1000 and given cell position (row number or column number) can be 10^9. so you have to decompress the row numbers and column numbers using STL map.

Solution Idea #1: Brute Force. 

count how many demons in row and column. find which row or column have maximum demons, then remove all the demons belongs to it. 

the idea won't work for this configuration. 

 

brute force idea will give 4, where minimum is 3. now go to the next idea. 

Solution Idea #2: Bipartite Matching

think the problem a little differently. each demon is denoted by two value, row and column. now you can assume the demons as edge and row and column as nodes. look at the picture below to clarify. 

here is two edge denoted by nodes (1, 7) and (2, 5)

now your task is to find minimum number of nodes to cover all edges. 

BINGO!!! straightforward BPM. 

Code: 

1. #include<bits/stdc++.h>
2. using namespace std;
3.  
4. #define SET(a) memset(a,-1,sizeof(a))
5. #define CLR(a) memset(a,0,sizeof(a))
6. #define PI acos(-1.0)
7. #define MOD 1000000007
8. #define MX 2002
9.  
10. vector<int>adj[MX];
11. int lft[MX], rgt[MX];
12. bool visited[MX];
13.  
14. bool bpm(int u)
15. {
16. for(int i=0;i<adj[u].size();i++)
17. {
18. int v=adj[u][i];
19. if(visited[v]) continue;
20. visited[v]=true;
21.  
22. if(rgt[v]==-1 || bpm(rgt[v]))
23. {
24. lft[u]=v;
25. rgt[v]=u;
26. return true;
27. }
28. }
29. return false;
30. }
31.  
32. int maximum_match(int n)
33. {
34. int cnt=0;
35. for(int i=1;i<=n;i++)
36. {
37. CLR(visited);
38. if(bpm(i)) cnt++;
39. }
40. return cnt;
41. }
42.  
43. int main()
44. {
45. int tc,kk=1, n, x, y;
46. cin>>tc;
47. while(tc--)
48. {
49. cin>>n;
50. map<int, int>mp;
51. int cnt=0;
52. for(int i=0;i<n;i++)
53. {
54. cin>>x>>y;
55. y+=1e9+1;
56. if(!mp[x]) mp[x]=++cnt;
57. if(!mp[y]) mp[y]=++cnt;
58. adj[mp[x]].push_back(mp[y]);
59. adj[mp[y]].push_back(mp[x]);
60. }
61. SET(lft);
62. SET(rgt);
63.  
64. cout<<maximum_match(cnt)/2<<endl;
65.  
66. for(int i=1;i<=cnt;i++) adj[i].clear();
67. }
68. return 0;
69. }