SPACEARR - Editorial

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;
}
2 Likes

My solution -

First, find out the number of occurrences for each element [1-n].
Second, Check for each element, the count of all numbers that are >= to it( say num_greater_elements or nge in short). If count(num_greater_elements) is <= (n - ele + 1) [if ele = 3, n = 5, then num_greater_elements for ele = 3 should be <= 5 - 3 + 1] then it can be/become any permutation of numbers 1 to n, only if this is true for all the elements.

If num_greater_elements is >= 5 -3 +1, that means this array can never become a permutation, hence Second wins.

Now, after all this, lets say every element of the given array satisfies the above inequality.

Now calculate the sum of all the elements (say sum).
What’s the maximum sum for an array of 1 to n elements?
max_sum = (n * (n+1))/2

if sum >= max_sum then Second wins
else {
diff = max_sum - sum
if diff is even then Second wins
else First wins
}

I believe this approach is correct, but i could only pass first subtask. :’(

Can anyone provide a corner case where this algorithm fails?

I took a different approach. First read the sequence into an array and sort it. A permutation contains the numbers 1 to N, so if any member of the sorted array A[i] > i (1-based) then no solution is possible. Evaluate the total deficit i - A[i] and proceed as above. The sorting makes this approach O(log(N)), still fast enough. My submission is at CodeChef: Practical coding for everyone

1 Like

I also once tried with this way - but, this would fail in few cases e.g. for n = 5, array [ ] = {2, 2, 3, 3, 3, 3} or n = 5, array [ ] = {1, 3, 3, 3, 4} etc. Check for these. A valid permutation won’t exist for this array, but as per the condition mentioned by you, it will get satisfied.

1 Like

Try to explain your algo upon posting a query about your approach .

i have a doubt,how can we sort the array . the array should be left undisturbed practically

1 Like

But solving the problem becomes easy after sorting.

Why does this code give a WA in one of the subtasks? Please have a look and help.

while(t-- >0)
{
    int n=in.nextInt();
    int[] arr= new int[n];
    long to_be_added=0;
    for(int i=0;i<n;i++)
    {
        arr[i]=in.nextInt();
    }

    Arrays.sort(arr);
    for(int i=0;i<arr.length;i++)
    {   if(arr[i]>i+1)  {break;}
        to_be_added+=(i+1-(arr[i]));

    }
    if(to_be_added==0)              out.println("Second");
    else if(to_be_added%2==0)       out.println("Second");
    else                            out.println("First");
}

Sir, can you please take a look at this code snippet.
I think, I did the same thing.
package codes;

import FastIO.InputReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class SpaceArrays {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
int t=in.nextInt();
//testcases

while(t-- >0)
{
    int n=in.nextInt();
    int[] arr= new int[n];
    long to_be_added=0;
    for(int i=0;i<n;i++)
    {
        arr[i]=in.nextInt();
    }

    Arrays.sort(arr);
    for(int i=0;i<arr.length;i++)
    {   if(arr[i]>i+1)  {break;}
        to_be_added+=(i+1-(arr[i]));

    }
    if(to_be_added==0)              out.println("Second");
    else if(to_be_added%2==0)       out.println("Second");
    else                            out.println("First");
}
    }
}

Akash, suppose we have a sorted sequence that starts 0 3 x x x. In your code

On the first pass, to_be_added is set to 1.
On the second pass, it breaks from the loop, leaving to_be_added as 1.
You should set to_be_added to 0 before breaking from the loop.

if(arri]>i+1)  {break;}

should read

if(arr[i]>i+1)  {
    to_be_added = 0;
    break;
}

Also you don’t need to check (to_be_added == 0) because this case is covered by (to_be_added % 2 == 0)

4 Likes

n = 6 array[] = {2,2,3,3,3,3} ans is First? and for n = 5 array[] = {1,3,3,3,4} ans is First?

NO, ans is Second in both the cases. It won’t be possible for First to even start the game.

1 Like

Thanks, I got your point