PROBLEM LINK:
Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest
Author: Yuriy Fedorov
Tester: Felipe Mota
Editorialist: Yuriy Fedorov
DIFFICULTY:
Easy
PREREQUISITES:
Game theory
PROBLEM:
Given an array a_1 \ldots a_n and two players play a game on it. Each player must increase one element of the array by 1, and if there is no permutation p_1 \ldots p_n such that p_1 \leq a_1 \ldots p_n \leq a_n, then he loses, otherwise the move is passed to another player.
EXPLANATION:
Let’s understand what is the general condition for the fact that such a permutation exists at all.
Let c_i be the number of elements in the array \leq i.
Then to put 1 somewhere, you need c_1 \geq 1. To put 2 , we need to guarantee that c_2 \geq 2, since we spent one such element on 1. Similarly, c_i should be \geq i. Since we spent i-1 of such elements on smaller values. So the sufficient condition for the existence of a permutation is c_i \geq i.
Let’s see what happens after one move. We have one of the elements increases by one. Note that in this case, c_1 + c_2 + \ldots + c_n increases by exactly 1.
Since in the case of a bad move, the player immediately loses, the game will end only if c_i = i. Otherwise, the player could make a move, or after his turn, he would immediately lose.
So the solution is to look at the value of 1 + 2 + \ldots + n - (c_1 + c_2 + \ldots + c_n). If she is even, the second player wins, otherwise the first player win. You also need to see if there was no move initially (c_i < i), then the second one immediately wins, since there is no suitable move.
As a result, the solution for O (n)
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <vector>
using namespace std;
void solve() {
int n;
cin >> n;
long long sum = 0;
vector<int> c(n);
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
c[a - 1] += 1;
}
for (int i = 1; i < n; ++i)
c[i] += c[i - 1];
for (int i = 0; i < n; ++i) {
if (c[i] < i + 1) {
cout << "Second\n";
return;
}
sum += c[i];
}
cout << ((sum - (long long) n * (n + 1) / 2) % 2 == 0 ? "Second\n" : "First\n");
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l<=x && x<=r)){
cout << l << ' ' << r << ' ' << x << '\n';
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = readIntLn(1, 2 * TEN(4));
int sum_n = 0;
while(t--){
int n = readIntLn(1, 2 * TEN(5));
sum_n += n;
vector<int> a(n);
for(int i = 0; i < n; i++){
if(i + 1 < n) a[i] = readIntSp(1, n);
else a[i] = readIntLn(1, n);
}
sort(a.begin(), a.end());
bool impossible = false;
for(int i = 0; i < n; i++)
if(a[i] > i + 1)
impossible = true;
long long sum = accumulate(a.begin(), a.end(), 0ll);
sum -= 1ll * n * (n + 1) / 2;
if((sum % 2) == 0)
impossible = true;
if(impossible) cout << "Second\n";
else cout << "First\n";
}
assert(1 <= sum_n && sum_n <= 2 * TEN(5));
return 0;
}