DESTRUCT - Editorial

PROBLEM LINK:

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

Author: Utkarsh Gupta
Tester: Aryan
Editorialist: Aryan

DIFFICULTY:

EASY-MEDIUM.

PREREQUISITES:

Observation, Game Theory

PROBLEM:

In 2 player game. There are N piles, i^{th} pile contains A_i stones. In each turn, one of the players chose a pile with non zero stones and the other player removes non zero stones from it and then in the next turn role of both players is reversed. The player who removes the last stone wins.

QUICK EXPLANATION:

The first player to remove coins win if and only if -

  1. All piles contain 1 coin and the total no of piles are odd.
  2. Total no of piles with 1 coin is even and there is at least one pile with contains more than 1 coin.

EXPLANATION:

The most difficult part of the problem is to observation to come up with the winning states. Once it’s done it’s relatively easy to prove it.

Let us denote winning states as the starting distribution of piles if the first player to start wins. Let’s call the first player to remove piles as A and other players as B.

1. All piles contain 1 coin

None of the players really have the choice here since all piles are identical. In each turn, the player would remove the only coin remaining in the pile. So the winner just depends on the no of the piles. If there are odd piles then A would be the last person to remove coins and would win. If piles are even then B would be the last person to remove coins and would win. Hence its winning state if and only if no of piles are odd.

2. There is at least one pile that contains more than 1 coin

We can further divide it into two cases -
2. a.) There is only one pile that contains more than 1 coin.
2. b.) There is more than one pile that contains more than 1 coin.

2. a.) There is only one pile that contains more than 1 coin.
  • If B picks a pile that has just 1 coin. Then A doesn’t have any choice but to remove all coins from that pile. Since for winning state, there would be even no of piles with 1 coin. In the very next turn, A can again choose a pile with 1 coin. B wouldn’t have any choice either.

    After these 2 turns, we would reach the same state except that we have removed 2 piles with 1 coin. The parity of no of piles with 1 coin remains the same. Also, the no of piles with contains more than 1 coin remains the same. If starting position was a winning state then it would again be a winning state,

  • If B picks a pile that has more than 1 coin. Then A should remove all coins from this pile. If this was the only remaining pile then A wins. Otherwise, all the remaining piles have 1 coin.
    In the very next turn, A should choose any pile and B would remove the only remaining coin from the same pile.
    After these 2 turns, we would reach the same state except that we have removed 1 pile which had more than 1 coin and 1 pile which contained 1 coin. Since in the winning state there were even no of piles with 1 coin after these two turns there would be an odd no of piles with one coin and all piles would contain 1 coin. Hence if starting position was a winning state then it would again be a winning state,

2. b.) There is more than one pile that contains more than 1 coin.
  • If B picks a pile that has just 1 coin. Then A doesn’t have any choice but to remove all coins from that pile. Since for winning state, there would be even no of piles with 1 coin. In the very next turn, A can again choose a pile with 1 coin. B wouldn’t have any choice either.

    After these 2 turns, we would reach the same state except that we have removed 2 piles with 1 coin. The parity of no of piles with 1 coin remains the same. Also, the no of piles with contains more than 1 coin remains the same. If starting position was a winning state then it would again be a winning state,

  • If B picks a pile that has more than 1 coin. Then A should remove all coins except 1 coin from this pile. In the very next turn, A should force B to remove the only remaining coin from the same pile.
    After these 2 turns, we would reach the same state except that we have removed 1 pile which had more than 1 coin. Since there were still at least two piles containing more than 1 coin. There would be at least one pile remaining which would have more than 1 coin. If starting position was a winning state then it would again be a winning state,

Hey Aryan, this works but how do I come up with this observation?

To be honest this is the reason why this problem was initially rated as medium initially.

  • Some people tried some greedy and then they came up with it. Then they verified similar to the editorial and found this works.

  • Some people brute-forced to print all winning states then see what is observed pattern among them. Then they verified similar to the editorial and found this works.

  • @shubham_12 observed that we can replace all piles with more than 2 coins to 2 coins pile and the result would still remain the same. Then he did some dp to precompute on no of piles with 1 coin and no of piles with 2 coins. 55176615

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTIONS:

Tester's and Editorialist's Solution (Python)
def main():
    T=int(input())
    for _ in range(T):
        n=int(input())
        a=[int(x) for x in input().split()]
        ones = a.count(1)
        if ones == n:
            if ones % 2 == 1:
                print("Utkarsh")
            else:
                print("Ashish")
        else:
            if ones % 2 == 0:
                print("Utkarsh")
            else:
                print("Ashish")

main()
Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
/*
------------------------Input Checker----------------------------------
*/
 
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();
        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;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        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,' ');
}
void solve()
{
    int n=readInt(1,1000,'\n');
    int arr[n+1]={0};
    int cnt1=0;
    for(int i=1;i<=n;i++)
    {
        ll c;
        if(i!=n)
            c=readInt(1,1000000000,' ');
        else
            c=readInt(1,1000000000,'\n');
        if(c>=2)
            arr[i]=2;
        else
            arr[i]=c;
        if(arr[i]==1)
            cnt1++;
    }
    if(cnt1==n)
    {
        if(n%2==1)
            cout<<"Utkarsh\n";
        else
            cout<<"Ashish\n";
    }
    else
    {
        if(cnt1%2==0)
            cout<<"Utkarsh\n";
        else
            cout<<"Ashish\n";
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=readInt(1,200,'\n');
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    assert(getchar() == -1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's and Editorialist's Solution 2
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

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();
        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;
            }
            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();
        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,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         const lli u=readIntSp(1,n)-1;
//         const lli v=readIntLn(1,n)-1;
//         e[u].pb(v);
//         e[v].pb(u);
//         d.merge(u,v);
//     }
//     assert(d.size(0)==n);
//     return e;
// }

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,200);
while(T--)
{

    n=readIntLn(1,1e3);
    a=readVectorInt(n,1,1e9);
    lli one=0;
    for(auto x:a)
        one+=x==1;
    if(one!=n)
        one^=1;
    cout<<(one&1?"UtkaRsh":"AshIsh")<<endl;
}   aryanc403();
    readEOF();
    return 0;
}
1 Like

This is the same as the problem “stones” of CEOI2021. :sweat_smile: