Space Arrays (SPACEARR) Solution — Codechef March Long Challenge

Problem Statement

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 a1,a2,…,aN is given.
• The players alternate turns.
• In each turn, the current player must choose an index i and increment ai, i.e. change ai to ai+1.
• Afterwards, if there is no permutation p1,p2,…,pN of the integers 1 through N such that ai≤pi holds for each valid i, 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 T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains N space-separated integers a1,a2,…,aN.

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≤T≤2⋅10⁴
• 1≤N≤2⋅10⁵
• The sum of N over all test cases doesn’t exceed 2⋅10⁵
• 1≤ai≤N for each valid i

Subtasks

Subtask #1 (100 points): Original constraints

Example Input

4
4
1 2 3 3
4
1 1 3 3
5
1 2 2 1 5
3
2 2 3

Example Output

First
Second
Second
Second

Explanation

Example case 1:

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

Code (Solution)

The code has been implemented in 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
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
Outer:
while(t-- > 0){
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
int sum =0;
int i=0;
for(i=0;i<n;i++){
if(arr[i] <= i+1){
sum += Math.abs(arr[i]-(i+1));
}
else{
System.out.println("Second");
continue Outer;
}
}
if(sum%2==0)
System.out.println("Second");
else
System.out.println("First");
}
}
}

Hope you would have liked the article. Please give 50 claps to this article and follow me for more future programming related blogs.

References

https://www.codechef.com/MARCH21C/problems/SPACEARR