GAMEW - Editorial

PROBLEM LINK:

Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest

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

DIFFICULTY:

SIMPLE

PREREQUISITES:

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)
                        cout << "RAMADHIR\n";
                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 readString(int l,int r,char endd){
    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){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,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){
    string s = readStringLn(n, 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 q = readIntLn(1, max_q);
    ll sum_n = 0;
    while(q--){
        ll n = readIntLn(1, max_n);
        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) {
        cout << "RAMADHIR" << endl;
    }
    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??
help please

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

1 Like