Query regarding Take Not less problem in feb 2023 cookoff contest

general
,
1 
#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?

2

dude , i want to ask the samee ques as i have similar code and it is failing on some test case…

3

Check the test case:

1
5
1 1 2 3 3

Answer should be Marichka by starting with element 2.

1 Like
4

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??

5

in the above example if Marichka start from 2 then only she will win

6

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.

1 Like
7

Why should we start with 2 can’t we start with 3 i.e. the max element

8

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.

9

Got it.