Space Arrays | codechef solution

Finally, progress reached the Madoka family and she decided to play with her little sister in the sensational game Space Arrays.

The rules of the game are as follows:

• Initially, a sequence ${�}_{1},{�}_{2},\dots ,{�}_{�}$ is given.
• The players alternate turns.
• In each turn, the current player must choose an index $�$ and increment ${�}_{�}$, i.e. change ${�}_{�}$ to ${�}_{�}+1$.
• Afterwards, if there is no permutation ${�}_{1},{�}_{2},\dots ,{�}_{�}$ of the integers $1$ through $�$ such that ${�}_{�}\le {�}_{�}$ holds for each valid $�$, the current player loses.
• Otherwise, the game continues with the next turn.

Madoka is asking you to help her ― tell her if the first player (the player that plays in the first turn) or second player wins this game if both play optimally.

Input

• The first line of the input contains a single integer $�$ denoting the number of test cases. The description of $�$ test cases follows.
• The first line of each test case contains a single integer $�$.
• The second line contains $�$ space-separated integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$.

Output

For each test case, print a single line containing the string "First" if the first player wins or "Second" if the second player wins (without quotes).

Constraints

• $1\le �\le 2\cdot 1{0}^{4}$
• $1\le �\le 2\cdot 1{0}^{5}$
• The sum of $�$ over all test cases doesn't exceed $2\cdot 1{0}^{5}$
• $1\le {�}_{�}\le �$ for each valid $�$

Subtask #1 (100 points): Original constraints

Sample 1:

Input
Output
4
4
1 2 3 3
4
1 1 3 3
5
1 2 2 1 5
3
2 2 3
First
Second
Second
Second

Explanation:

Example case 1:

• If the first player increases the fourth element, the resulting sequence is $\left(1,2,3,4\right)$. The second player loses after increasing any of the elements.
• If the first player increases the second element, the resulting sequence is $\left(1,3,3,3\right)$, and he loses because there is no valid permutation. For example if $�=\left(2,1,4,3\right)$, the second element of $�$ is greater than the second element of $�$.

Code(C++):-
#include <iostream>
#include<algorithm>
using namespace std;

int main() {
int t;
cin>>t;
for (int j=0; j<t; j++){
int n;
cin>>n;
int arr[n];
long long count=0;
for (int i=0; i<n; i++){
cin>>arr[i];
}
int flag=0;
std::sort(arr,arr+n);
for (int i=0; i<n; i++){
if (arr[i]<i+1){
count += i+1-arr[i];
}
if (arr[i]>i+1){
flag=-1;
break;
}
}
if (flag==0){
if (count%2==1){
cout<<"First"<<endl;
}
else{
cout<<"Second"<<endl;
}
}
else{
cout<<"Second"<<endl;
}
}
return 0;
}

Code(JAVA):-
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++)
a[i]=sc.nextInt();
Arrays.sort(a);
int sum=0;
boolean is=true;
for(int i=0;i<n;i++){
if(a[i]<=(i+1)){
sum=sum+i+1-a[i];
}
else{
is=false;
break;
}
}
if(!is)
System.out.println("Second");
else{
if(sum%2==0)
System.out.println("Second");
else
System.out.println("First");
}
}
}
}