# GAMEW - Editorial

Author: Raghav Agarwal
Tester: Miten Shah
Editorialist: Ansh Gupta

SIMPLE

Observation

# PROBLEM:

There is a string S of length N consisting of only 0's and 1's. Players take turns moving - on his turn, a player chooses some block of S and erases it. The remaining parts of S are then concatenated together (without changing the order), and the other player then makes a move on this modified string.The player who is unable to make a move at the end loses the game and has to leave Wasseypur.

# QUICK EXPLANATION:

Given a string of length n consisting of only 0's and 1's. Two players are playing a game. Game goes in turn, in each turn a player can erase a block from the current string and the remaining part of the string will concatenate to make the current string for another player.The player who will not be able to make a move at the end will lose the game. Assuming the game will start from the first player, find out the winner.

# EXPLANATION:

Firstly, find out the different number of blocks in the given string, let say it is K. If a player erases the left most or right most block number of blocks will be reduced by 1 but if he erases any other block, the number of blocks will be reduced by 2.
Now, from the first playerâ€™s perspective,

K  	    =  	1	2	3	4	5	6	7	8	9	10	11
Condition:	W	L	W	W	L	W	W	L	W	W	L


W - winning condition, L- Losing condition It can be seen,
if (K % 3 == 2 ) it is a losing condition for the first player otherwise winning.

# TIME COMPLEXITY:

Overall time complexity would be be: O(n) per test case, where n is the size of string.

# SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define fast_io std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

using namespace std;

int main() {
int t;
cin >> t;

while (t--) {
int n;
cin >> n;
string s;
cin >> s;

int cnt = 1;
for (int i = 1; i < n; i++)
cnt += s[i] != s[i - 1];

if (cnt % 3 == 2)
else
cout << "SAHID\n";
}
}


Tester's Solution
// created by mtnshh

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)

#define err() cout<<"--------------------------"<<endl;
#define errA(A) for(auto i:A)   cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl

#define all(A)  A.begin(),A.end()
#define allr(A)    A.rbegin(),A.rend()
#define ft first
#define sd second

#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>

#define endl "\n"

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cerr << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

const int max_q = 1e4;
const int max_n = 1e5;
const int max_sum_n = 1e6;

const ll N = 100005;
const ll INF = 1e12;

void solve(ll n){
rep(i,0,n)  assert(s[i] != '0' or s[i] != '1');
ll cnt = 0;
char last = '\$';
rep(i,0,n){
if(s[i] != last){
last = s[i];
cnt += 1;
}
}
if(cnt % 3 == 2)    cout << "RAMADHIR" << endl;
else                cout << "SAHID" << endl;
}

int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll sum_n = 0;
while(q--){
solve(n);
sum_n += n;
}
assert(sum_n <= max_sum_n);
assert(getchar()==-1);
}

Editorialist's Solution
#include"bits/stdc++.h"
using namespace std;
int N = 0;
void solve()
{
int n;
cin >> n;
N += n;
assert(1 <= n and n <= 1e5);
assert(1 <= N and N <= 1e6);
string s;
cin >> s;
for (int i = 0; i < n; i++) {
assert(s[i] == '0' || s[i] == '1');
}
int cnt = 1;
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1]) {
cnt++;
}
}
if (cnt % 3 == 2) {
}
else {
cout << "SAHID" << endl;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
assert(1 <= t and t <= 1e4);
while (t--)
{
solve();
}
return 0;
}


I solved it with Dynamic Programming.
Solution: 53440140 | CodeChef

6 Likes

Iâ€™m not understanding where mod 3 came from here. Can someone explain?

if we have number of blocks so can we fill dp array as dp[i]=dp[i-1]&dp[i-2]
as if at dp[i-1] or dp[i-2] we have 0 that means the second person will loose hence we will win
so why i am getting wrong ans??

why my dp solution is wrong any idea?
https://www.codechef.com/viewsolution/53465689

The current player wins if and only he can make a move to force the other player to lose, so the correct recurrence relation, for \textit{numBlocks}>2:

playerWinsForNumBlocks[numBlocks] = !playerWinsForNumBlocks[numBlocks-1]     // Player chooses end block.
|| !playerWinsForNumBlocks[numBlocks-2]; // Player chooses non-end block.


or equivalently:

playerWinsForNumBlocks[numBlocks] = !(playerWinsForNumBlocks[numBlocks-1] && playerWinsForNumBlocks[numBlocks-2]);

2 Likes

@sonicdude47 At every step, the next player has the choice to reduce the number of blocks either by one by taking an end block or (provided there are more than two blocks) by two by taking a mid block

The â€śmod 3â€ť comes about because by making the opposite choice to your opponent you can always drop the number of blocks they face by 3. Since 2 blocks is a losing position, the player facing 2 mod 3 blocks can be kept in that position until they reach exactly two blocks and lose.

2 Likes

Use xor(^) instead of and(&) in dp[i]= dp[i-1] & dp[i-2] and try to think of the logic behind it.

Here is My DP code Memoised Version
https://www.codechef.com/viewsolution/53471202

yeah bro got it
thanks