PROBLEM LINK:
Setter- Oleksandr Kulkov
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY
PRE-REQUISITES:
Observations, Strings, 2-D arrays, Game Theory.
PROBLEM:
Given 2 strings which tell if a player bringing coin to that cell wins or loses, we need to tell Q queries asking “Who wins the game if game starts at (x,y) and alice goes first?”
QUICK-EXPLANATION:
Key to AC- Observing winning and losing positions diagonally!!
We have data to tell who wins if stone comes at (0,i) or (i,0). Use that to derive data of first 2 rows. Use the observation that, winning positions dont change diagonally after row 2. (There are corner cases where they can change from row 1 to row 2 going diagonally, but they are guaranteed to remain constant thereafter). Now, store the states (whether player starting at that cell wins or loses) for first 2 rows and first 2 columns. After this, all thats left is to do this to make cases. If (x,y) does not lie in first 2 rows or first 2 columns, find the corresponding cell in row/column 2 diagonal to (x,y) (if cell is not in row 1 or row 2 or column 1 or column 2) to find the answer, as states remain constant diagonally. If cell is in first 2 rows or columns whose state we calculated above, we simply refer to it to answer the query.
EXPLANATION:
This editorial will have 2 sections. We will be referring to first the brute force, and then deal with what we observed and how we used it to get full solution.
First Subtask-
There was a lot of confusion in this question related to what does 0 represent and what does 1 represent, mostly because the question followed a different convention. Hence, to avoid any such confusion, let me denote W as winning position, i.e. player starting from this cell wins, and L by losing position, i.e. player starting from this cell loses.
Lets first get how the games are played by the players. The only thing you need to remember is, for impartial games, usually the starting position itself determines the winner if players play optimally. If “playing optimally” is something that confused you in this question, read the paragraphs below in tab-
Click to view
"First player is starting from (x,y). A cell is marked W if a player starting from that cell (or who has his turn when stone is on that cell) wins. A cell is marked L if he loses if he has to make a move from that cell.
Now, assume we already found out which of previous cells (or cells which we might visit in our moves) are W or L. If all the cells to which I can move to (from current cell) are W, then that means that my opponent will win (because a cell is W if player who gets to make a turn when stone is on that cell wins). This means, I will lose no matter what, as irrespective of how I move, there is a winning strategy possible for my opponent. What if all are not W, i.e. I can move to a cell labelled L? It means my opponent cannot win no matter what if stone is at that cell when he gets his turn. Now, obviously, I will move the stone to that L labelled cell to win as I move optimally."
What does above mean (especially if you read the paragraphs in hidden tabs)? The starting position will determine the winner, and if we know states of previous cells then we can find states (W or L) of current cell. All thats left is, finding a base case to start with so we can start finding if the position is W or L.
How do we do that…HMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM. The setter gave us 2 strings, can we use them for this? Turns out we can 
I will denote the string also by WLWLWWWL... to avoid any confusion regarding 0 and 1's. W means player bringing stone at that position wins, and L means he loses.
We can move vertically up, or horizontally left. Hence, the states (W or L) of only these 2 cells matter. For cell (1,1) , we know the states of (0,1) and (1,0) in input. Once we get (1,1), then along the row we can derive state of (1,2) , and hence (1,3) and hence (1,4)…and so on. Doing this for every row gives us states of all the cells. Now for every query, we see the state of given cell and accordingly append to the string.
You know the base case, and also the recurrence (when and how to assign a state W or L). Can you come up with a pseudo code to assign current state W or L?
Please let me make it clear. W/L in matrix means player who starts his turn at that cell wins/loses, while W/L in string means player who brings stone at that cell wins/loses.
Answer is in tab below-
Click to view
//Applicable only after Row 1. Not to be used to find states of Row 1 or Row 2.
- If(A_{i-1,j}==L) then A_{ij}=W
- Else if (A_{i,j-1}==L) then A_{ij}=W
- Else \implies both A_{i-1,j}==W and A_{i,j-1}==W \implies A_{ij}=L
How to find for Row 1 and Column 1 then?-
Row 1-
-
If(A_{0,j}==W) then A_{ij}=W//I can win by moving to cell (0,i)
-
Else if (A_{1,j-1}==L) then A_{ij}=W//I can force my opponent to lose by moving to cell (1,j-1)**
-
Else A_{1j}=L
Use this to derive the same for Column 1.
Full Solution-
Surprisingly, this section wont be long at all!
The only difference between brute force and full solution is that, full solution observes (or proves) that diagonal elements after row 2 remain constant. Hence, while brute force tries to find the entire matrix, full solution derives the state of cell (x,y) using cells in first 2-3 rows and columns. (We only need cell which is lying “Diagonally backward” from (x,y) in these rows.)
Images and all those are fine, but how can one actually get the intuition?
The most basic and commonly used method, of course, is observation. But proofs are needed to be done, so that we can verify and also better ourselves at such questions. I will first state the lemma’s or rules, and then move on to prove them one by one. Proofs are in tabs, so that you can first attempt to derive them.
- If A_{ij}=L \implies A_{i+1,j+1}=L as well. Meaning, if cell (i,j) is losing state, then cell (i+1,j+1) is losing state as well.
- Can we sketch a similar proof for A_{ij}=W? Why/Why not? What significance does it have?
- Prove that there cannot be more than 3 consecutive W's in matrix after row 1. After this, explore that when a W changes to L. (You’ll see it happens in case of 3 or more consecutive Ws.
Proof of Lemma 1-
Click to view
Say A_{ij}=L. Now, what does this imply for A_{i+1,j} and A_{i,j+1}? We can see that, from both these cells, the starting player can move to A_{ij} and force his opponent into a losing move!! This means that if A_{ij}=L \implies A_{i+1,j} =A_{i,j+1}=W
Now, if A_{ij}=L \implies A_{i+1,j} =A_{i,j+1}=W, then this means that, if I am at cell A_{i+1,j+1}, then no matter where I move, opponent will have a winning move. This implies that A_{i+1,j+1}=L as we cannot force the opponent to lose and the game cannot tie. (i.e. the opponent will be able to force us to lose).
Answer for 2.-
Click to view
No!! The base point of above proof was that, just 1 L (among cells where we can move) is enough to give us the chance to make opponent lose. But 1 W among them doesnt mean that we lose. All of them must be W to enforce that!
The significance is that, while we can say that if A_{ij}=L \implies A_{i+1,j+1}=L, we cannot imply the same for W. Hence, the observation becomes "A state of W may or may not change diagonally, but the state of L will definitely NOT change.
Proof for 3.
Click to view
Assume that we have three consecutive 1's at cells (i,j-1) (i,j) and (i,j+1). From the W's at (i,j+1), go back diagonally. The state at (i-1,j) must also be W! Why? Because had it been L, then state at (i,j+1) would had been L as well as L forces its diagonally next elements to be L as well.
Now, this is the corner case. Why? Because say, there do exist 3 consecutive W in the matrix. What effect does it have on the states of next row? Say, we talk of cell (i+1,j+1). We know that (i,j) is a W, but so is (i,j+1) and (i+1,j), i.e. both the cells where we can move are giving opponent a winning strategy. This means that (i+1,j+1) is actually L!!.
This proof is significant in 2 ways. First it tells that, if I have W diagonally, they can convert to L and remain constant thereafter. The second is that it proves that I will not see 3 consecutive 1's in any row except row 1, because row 0 is not determined by our rules and is given as an input from user.
Now, with this idea clear, how do we implement it? One of the neat implementations used by @um_nik ought to be discussed here :D.
- Create a matrix. Find Row 1 and Row 2, along with Column 1 and Column 2 as we discussed above.
- If Query is in row 1 or row 2, we already have the answer
- Else, diagonally move backward until you come at row or column 2. The answer is stored in your table.
Code for reference is in tab below-
Click to view
void solve() {
scanf("%s", s);
n = strlen(s);
for (int i = 1; i <= n; i++)
a[0][i] = (int)(s[i - 1] - '0');//Base case, assigning input to 0'th row.
scanf("%s", s);
m = strlen(s);
for (int i = 1; i <= m; i++)
a[i][0] = (int)(s[i - 1] - '0');
for (int x = 1; x <= m; x++) {
for (int y = 1; y <= n && y < (int)a[x].size(); y++)
a[x][y] = 1 ^ (a[x - 1][y] & a[x][y - 1]);//Calulating the states. Refer to formula
//we discussed
}
int q;
scanf("%d", &q);
while(q--) {
int x, y;
scanf("%d%d", &x, &y);
int d = min(x, y) - 3;//Number of steps to reach at least 3rd row or column
if (d > 0) {//d<= means we are at <=3rd row/column already (eg- Row 2 etc.)
x -= d;//We already have ans of above part. Else, we move diagonally backwards
y -= d;//Until we reach third row.
}
printf("%d", a[x][y]);//print the character instead of involving strings at all.
}
printf("\n");
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
a.resize(N);
for (int i = 0; i < N; i++) {
if (i < 4)
a[i].resize(N);//For first 4 rows, find states of all columns. After that, keep
//track of only first 3-4 columns
else
a[i].resize(4);
}
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
SOLUTION
Author’s solution can be found here.
Tester’s solution can be found here.
Click to view
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
vector<vii> vec(123456);
char ans[123456];
int main(){
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
string c;
string r;
cin>>r>>c;
int i,j;
int n=c.length();
int m=r.length();
rep(i,n+10){
vec[i].clear();
}
int q,pos;
cin>>q;
int a,b;//note down queries.
rep(i,q){
cin>>a>>b;
vec[a].pb(mp(b,i));
}
string s="";
fd(i,r.length()-1,0)
s+=r[i];
r=s;
int len=r.length();
r+='0';
f(i,1,n+1){
// simulating the problem statement for first 10 rows. Becuase there is no good pattern in first three rows
if(i<10){
r[len]=c[i-1];
fd(j,len-1,0){
if(r[j+1]=='1' && r[j]=='1')
r[j]='0';
else
r[j]='1';
}
}
else{
// correspondingly updating pattern for each row from previous row based on the element.
if(r[len-1]=='0'){
r[len]='1';
}
else{
if(c[i-1]=='1'){
r[len]='0';
}
else{
r[len]='1';
if(len-2>=0 && r[len-2]=='1')
r[len-1]='0';
}
}
len++;
r+='0';
}
// answering queries in that row.
rep(j,vec[i].size()){
pos=vec[i][j].ss;
b=vec[i][j].ff;
ans[pos]=r[len-b];
}
}
rep(i,q){
cout<<ans[i];
}
cout<<endl;
}
return 0;
}
Editorialist’s solution can be found here.
Time Complexity=O(N)
Space Complexity=O(N)
CHEF VIJJU’S CORNER
1. Is your idea same as editorial? Still got TLE? Make sure you done use s=s+'1' for making the output string, as this method creates a completely new string and then adds ‘1’ to end, making it O(N^2)! Use s+=1; for better performance. Just like creating a new vector to add an element at last v/s adding an element at back of vector.
2. At the end of the day, I’d want you to remember the part of W and L which we discussed. You can apply that to any such game. If starting position determines winner, and you know the state of positions which you can visit from current cell, you can derive for this cell as well. A player wins only if he can force his opponent to lose by making sure opponent plays only at “losing” or L cells. Hopefully this will clear the numerous doubts among div2 guys on what “playing optimally” is 
3. Often I am asked, what does a coder truly do to ace all the contest’s problems?
Click to view
4. Setter’s Notes (his solution isnt based on observations)-
Click to view
Assume x=y=n and considered diagonal [(0,n), (1,n-1),...,(n,0)]. If you start in (n, n), you will always go through this diagonal and reach it in exactly n steps.
Now consider mapping (x,y) \implies (x+y,x-y). You can see that each step now is actually decreasing first coordinate by 1 and increasing or decreasing second coordinate by 1.
Thus we start in (2n, 0) and will end up in (n, k) when we step on. Now we can see that either first or second player has victorious strategy which ends up in -2 \le k \le 2.
Assume first player also makes last move. Then if (n,-1) is winning, he will start by stepping in (2n-1,-1) and will return to it on each his step. Same for (n,1). If they both are losing, second player has winning strategy.
You may see that if first players wins or not starting in (2n, 0) is actually same as for (n+1,0), or in initial coordinates (\lfloor n/2\rfloor +1,\lfloor n/2 \rfloor +1).
Now if second player makes a step on diagonal, first player will win iff (n,-2) and (n,0) are winning OR (n,0) and (n,2) are winning. In first case he starts with (2n-1,-1) and with (2n-1,1) in second.
You may see that now winning of first player is identical to (n+2,0), or in initial coordinates, well, also (n/2+1,n/2+1). This will reduce you size almost twice, unless n=2, for which you should calculate answers manually.
To generalize, assume x<y and consider diagonal [(y-x,x), (y-x+1,x-1),...,(y,0)].
5. Related Problems:
- Hackerrank Section for basic problems on game theory.
- Codeforces Section for trickier problems.
