#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin >> t;
while (t--){
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
sort(arr, arr + n);
bool flag = true, ans = false;
for (int i = n - 2; i >= 0; i--){
if (arr[i] < arr[i + 1]) {
if (flag) cout << "Marichka" << endl;
else cout << "Zenyk" << endl;
ans = true;
break;
}
flag = !flag;
}
if (!ans){
if (flag) cout << "Marichka" << endl;
else cout << "Zenyk" << endl;
}
}
return 0;
}

Can anyone help me to figure out a testcase in which the above code gives the wrong answer?

Sorry, but can you explain why we need to start from 2? Can’t we start from the last index every time coz there is no mention of starting index for Marichka??

If they are playing optimally, then the first person should take the max element in the array, the second person loses. If the max element occurs odd number of times, Marichka wins, else Zenyk wins.

This is incorrect, what #3 mentioned is the correct technique. The only way Zenyk can win is when EVERY element appears an even number of times, only then can he counter every one of Marichka’s moves by choosing another element with the same value. Else Marichka chooses the largest element that appears an odd number of times as a winning strategy.