USACO 2021 February Contest, Gold Problem 1. Stone Game

USACO 2021 February Contest, Gold Problem 1. Stone Game

Bessie and Elsie are playing a game with NN (1≤N≤1051≤N≤105) piles of stones, where the ii-th pile has aiai stones for each 1≤i≤N1≤i≤N (1≤ai≤1061≤ai≤106). The two cows alternate turns, with Bessie going first.

 

• First, Bessie chooses some positive integer s1s1 and removes s1s1 stones from some pile with at least s1s1 stones.
• Then Elsie chooses some positive integer s2s2 such that s1s1 divides s2s2 and removes s2s2 stones from some pile with at least s2s2 stones.
• Then Bessie chooses some positive integer s3s3 such that s2s2 divides s3s3 and removes s3s3 stones from some pile with at least s3s3 stones and so on.
• In general, sisi, the number of stones removed on turn ii, must divide si+1si+1.

The first cow who is unable to remove stones on her turn loses.

Compute the number of ways Bessie can remove stones on her first turn in order to guarantee a win (meaning that there exists a strategy such that Bessie wins regardless of what choices Elsie makes). Two ways of removing stones are considered to be different if they remove a different number of stones or they remove stones from different piles.

 

 

 

SAMPLE INPUT:

1
7

SAMPLE OUTPUT:

4

Bessie wins if she removes 44, 55, 66, or 77 stones from the only pile. Then the game terminates immediately.

 

SAMPLE INPUT:

6
3 2 3 2 3 1

SAMPLE OUTPUT:

8

Bessie wins if she removes 22 or 33 stones from any pile. Then the two players will alternate turns removing the same number of stones, with Bessie making the last move.

 

 

Problem credits: Benjamin Qi

 USACO 2021 February Contest, Gold Problem 1. Stone Game 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

We can think of a valid move in the game as follows:

 

1. Dividing all of the pile sizes by some positive integer.
2. Subtracting one from some pile with a positive size.

We claim that a state in the game is losing for the first player iff for each x≥1x≥1, the number of piles of size xx is even. In this case, the second player can win by simply mirroring the moves of the first player.

In all other states, let xx the maximum pile size such that the number of piles of size exactly xx is odd. Then the first player wins if she removes that pile.

Now suppose that Bessie removes xx stones from some pile on her first turn. Then we need to count the number of integers among the sequence Sx=[⌊a1x⌋,⌊a2x⌋,⌊a3x⌋,…,⌊anx⌋]Sx=[⌊a1x⌋,⌊a2x⌋,⌊a3x⌋,…,⌊anx⌋] such that when decreased by one, every positive integer in the sequence occurs an even number of times (ignoring zero).

So Bessie wins if she picks t>0t>0 such that

 

• tt occurs an odd number of times in SxSx
• If t>1t>1, t−1t−1 occurs an odd number of times in SxSx
• No other positive integer occurs an odd number of times in SxSx.

For each xx and tt, the number of occurrences of tt in SxSx is equal to the number of integers in the input sequence that are in the range [xt,x(t+1)−1][xt,x(t+1)−1]. For a fixed xx, we can compute this quantity for all relevant tt in O(maxaix)O(maxaix) time using prefix sums. After this, it's just a matter of checking which numbers appear an odd number of times in SxSx and updating the answer accordingly.

Time Complexity: O(N+(maxai)log(maxai))O(N+(maxai)log⁡(maxai)).

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int N; cin >> N;
	vector<int> A(N); 
	int mx = 0;
	for (int& t: A) {
		cin >> t;
		mx = max(mx,t);
	}
 
	vector<int> cum(mx+1); for (int t: A) ++cum[t];
	for (int i = 1; i <= mx; ++i) cum[i] += cum[i-1];
	auto getCum = [&](int ind) { // number of elements of A <= ind
		if (ind > mx) return cum.back();
		return cum[ind];
	};
 
	long long ans = 0;
	for (int x = 1; x <= mx; ++x) {
		vector<int> counts{0};
		for (int t = 1; x*t <= mx; ++t)
			counts.push_back(getCum(x*(t+1)-1)-getCum(x*t-1));
		vector<int> odd; 
		for (int t = 1; t < counts.size(); ++t) 
			if (counts[t]&1) odd.push_back(t);
		if (odd == vector<int>{1} || (odd.size() == 2 && odd[0]+1 == odd[1]))
			ans += counts[odd.back()];
	}
	cout << ans << "\n";
}

Danny Mittal's Code (somewhat different):

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class StoneGame {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        Integer[] piles = new Integer[n + 1];
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        for (int j = 0; j < n; j++) {
            piles[j] = Integer.parseInt(tokenizer.nextToken());
        }
        piles[n] = 0;
        Arrays.sort(piles);
        int[] diffSums = new int[1000001];
        int[] indexSums = new int[1000001];
        for (int j = n; j >= 1; j -= 2) {
            diffSums[piles[j]]++;
            diffSums[piles[j - 1]]--;
            indexSums[piles[j]] += j;
            indexSums[piles[j - 1]] -= j;
        }
        long answer = 0;
        for (int k = 1000000; k > 0; k--) {
            diffSums[k - 1] += diffSums[k];
            indexSums[k - 1] += indexSums[k];
            int diff = 0;
            int index = 0;
            for (int m = k; m <= 1000000; m += k) {
                diff += diffSums[m];
                index += indexSums[m];
            }
            if (diff == 1) {
                int upper = n;
                int lower = index;
                while (upper > lower) {
                    int mid = (upper + lower + 1) / 2;
                    if (piles[mid] / k == piles[index] / k) {
                        lower = mid;
                    } else {
                        upper = mid - 1;
                    }
                }
                answer += upper - index + 1;
            }
        }
        System.out.println(answer);
    }
}

[/hide]