CodeChef October Challenge 2013 Editorial [CAO Stage-3] ____________By: Nafis Sadique

Problem: CAO Stage-3

The problem has 2 sub-problems. The first problem is to finding the position of the monsters.
The second was to find out the winner of the game. Let's solve this problem step by step.

First problem - where are the monsters?

The problem says that we have to find the total number of consecutive free cells in all 4 direction from a cell. Then if the minimum of them has at least a prime less than or equal to it then we can call that this cell has a monster.

We know that the smallest prime is 2. So if any cell has at least 2 consecutive cells containing '^' in all 4 direction then we can say that this cell contains a monster. easy job!!!

Hard problem - who the hell is the winner?

Now we know the position of the monster. But what about the game we are supposed to play?
This game has 2 players. In one move a player can select any monster that is alive and kill all the monsters in the same row and column. The first person who can't give any move loses.
Sounds a lot like grundy game. But how to calculate the outcome?????????????

Well after being stuck for 1 day i finally observed this line in the statement 

"Lava stops flowing past the cells which already have lava in them."

That gave me a hint that we can convert the game to dp state and calculate the outcome.
The hint would be - whenever i select a monster i divide the grid into 4 disjoint grid.

Thus we can get a dp state and then use sprague-grundy theorem to calculate mex etc. etc.

See the code for details and if grundy is unclear then wikipedia would be a good reference.
Also you have to know dp.

Code:

1. #include <bits/stdc++.h>
2. using namespace std;
3.  
4. int dp[21][21][21][21], grid[21][21];
5.  
6. int go(int x1, int x2, int y1, int y2){
7. if(x1 > x2 || y1 > y2)return 0;
8. int &ret = dp[x1][y1][x2][y2];
9. if(ret != -1)return ret;
10. ret = 0;
11. set < int > ss;
12. for(int i = x1; i <= x2; i++){
13. for(int j = y1; j <= y2; j++){
14. if(grid[i][j] != 1)continue;
15. int a = go(x1, i - 1, y1, j -1);
16. a ^= go(x1, i - 1, j + 1, y2);
17. a ^= go(i + 1, x2, y1, j - 1);
18. a ^= go(i + 1, x2, j + 1, y2);
19. ss.insert(a);
20. }
21. }
22. for(set < int > :: iterator it = ss.begin(); it != ss.end(); it++){
23. if(ret != *it)break;
24. ret++;
25. }
26. return ret;
27. }
28. char pp[21][21];
29. main(){
30. ios_base::sync_with_stdio(0); cin.tie(0);
31. long long a,b,c,d,e,f,g,h = 0,x,y,z;
32. cin >> a;
33. while(a--){
34. cin >> b >> c;
35. for(int i=0;i<b;i++) cin >> pp[i];
36. memset(grid,0,sizeof grid);
37. memset(dp, -1, sizeof dp);
38. for(int i=0;i<b;i++){
39. for(int j=0;j<c;j++){
40. d = 0;
41. if(pp[i][j] == '#')d = 1;
42. if(i < 2 || pp[i - 1][j] == '#' || pp[i - 2][j] == '#')d = 1;
43. if(j < 2 || pp[i][j - 1] == '#' || pp[i][j - 2] == '#')d = 1;
44. if(i > b - 3 || pp[i + 1][j] == '#' || pp[i + 2][j] == '#')d = 1;
45. if(j > c - 3 || pp[i][j + 1] == '#' || pp[i][j + 2] == '#')d = 1;
46. if(d == 0)grid[i][j] = 1;
47. }
48. }
49. d = go(0, b - 1, 0, c - 1);
50. if(d == 0)cout << "Kirito" << endl;
51. else cout << "Asuna" << endl;
52. }
53. }