# Winter Vacation

**Adarsh and Saurabh are playing a Game in Winter Vacation. The game consists of \(N\) piles where each pile has some \(P_i\) marbles. At each step one player can search for pile with minimum number of marbles and removes it and all elements present to its right from list.**** Both player will play \(G\) games, your task is to determine the winner of the game i.e., the one who take up the last move If Adarsh plays first! Read Problem Statement.**

**Above problem can be solved using following approaches:**

**Naïve Method \(\mathcal O(n^2)\):**

- Search for the minimum element in the array and reduce the size of array till that minimum element.
- As problem contains
**distinct numbers**so there is no need to take care about occurrence of a single element multiple times.

Naïve approach can be illustrated using following approach -> *Lets take example of array A[5 4 1 3 2] is this array 1 ^{st} player search for the minimum element and reduce size of array by 3(as element is at index 2 (0-indexing) ).*

*Hence after 1*

^{st}move array A = [5 4]. Now second player takes up the chance and removes element 4 from array A = [5] at end last element is removed. The player who removed the last elements wins the Game.**Optimal Method ****\(\mathcal O(n)\)****:**

This problem requires a little observation that when first element is inserted it is our minimum element and of course 1^{st} player will win when the game is played. Now consider following two situations :

**When element inserted after 1**^{st}element is greater than it.

Ex- A = [5] U {6} = [5 6]

In this case winner will be first player, which means winner will never change if any element which is greater than previous is inserted in array.

Similarly we add 7 to list

A = [5 6 7] winner = 1^{st} player

**Now consider another case when element is smaller than 1**^{st}

Ex – A = [5] U {2} = [5 2]

In this case winner will be second player. Now we need to observe that after adding 2^{nd} element if 3^{rd} element is added which is smaller than our previous smallest value i.e, 2 only then the winner will be changed.

We only need to increment the counter wherever 2^{nd} case is satisfied.

Optimal solution code in C++ is:

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int n,q; cin>>q; int k=0; while(q--) { k=0; int x=1e9; cin>>n; for(int i=0;i<n;i++) { int num; cin>>num; if(num<x) { k++; x=num; } } if(k%2) cout<<"Adarsh\n"; else cout<<"Saurabh\n"; } return 0; }

This article is contributed by Ravi Kant. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.