MinGame (Hard Version)

Idea & Prepared By : knishanthreddy

Solution : shailesh_2004

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. Because every valid move adds the exact same value to a player's score, their scores will be perfectly tied after every round (after both players have taken one turn).

Because the scores are always tied at the end of a round, the game's tie-breaking rule strictly determines the turn order. The player who played second previously now plays first, creating a continuous 4-turn cycle:

Alice, Bob, Bob, Alice, Alice, Bob $\dots$

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.
• If $n\%(2\cdot k+2) > (k+1)$, then Bob wins.
• Otherwise, Alice wins

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 {
            int t=n%(2*k+2);
            if(t>k+1) cout << "Bob" << 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()))
    
    first_val = arr[0]
    all_equal = True
    
    for x in arr:
        if x != first_val:
            all_equal = False
    
    if not all_equal:
        print("Alice")
    else:
        m = n % (2 * (k + 1))
        
        if m == 0 or m == k + 1:
            print("Draw")
        elif 1 <= m <= k:
            print("Alice")
        else:
            print("Bob")

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

if __name__ == "__main__":
    main()