MinGame (Easy Version)

Author : knishanthreddy

Required Knowledge : Greedy, Game theory

Time Complexity : $\mathcal{O}(N)$

Editorialist : knishanthreddy

Approach:

Since Alice can rearrange the array before the game begins, she will always prefer a win over a draw, and a draw over a loss.

Case 1: The array contains at least two distinct numbers

If there are at least two unique elements in the array, Alice can construct a permutation that always guarantees her a win.

The Strategy :

She extracts the maximum and minimum elements from the array and sorts the remaining elements in descending order. She then places the maximum element at the very beginning of the array, immediately followed by the minimum element, and appends the rest of the descending sequence.

When the game starts, Alice simply picks only the first element $($the maximum value$)$ on her turn, regardless of the limit $k$. Because the next available element is the overall minimum, Bob will be forced to include it in his selection, meaning his score increase will be minimal. After this opening move, throughout the game Alice will have a greater score regardless of the subsequent plays resulting in Alice's Win.

Case 2: All elements in the array are equal

If all elements in the array are identical, Alice’s ability to rearrange the array has no effect. In this case, Bob can never guarantee a win. Therefore, the game will always result in either a win for Alice or a draw.

The outcome depends entirely on the length of the array $(n)$ and the maximum selection size $(k)$. This relationship forms a predictable pattern:

• If $n\%(k+1)$ equals zero then its a Draw.
• Otherwise, Alice win's.

Setter's Code:

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{       
    int n,k;
    cin >> n >> k;
    map<int,int> m;
    for(int i=0;i<n;i++) {
        int x; cin >> x;
        m[x]++;
    }
    if(m.size()==1) {
        if(n%(k+1)==0) cout << "Draw" << endl;
        else cout << "Alice" << endl;
    }
    else cout << "Alice" << endl;
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

Tester's Code:

import sys
input = sys.stdin.readline

def solve():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    
    all_equal = all(x == arr[0] for x in arr)
    
    if all_equal and (n % (k + 1) == 0):
        print("Draw")
    else:
        print("Alice")

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()