Stone Game USACO 2021 February Contest

by

Stone Game USACO Solution

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.

See Also : USACO 2021 Challenges

  • 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.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN.

The second line contains NN space-separated integers a1,…,aNa1,…,aN.

OUTPUT FORMAT (print output to the terminal / stdout):

Print the number of ways Bessie can remove stones on her first turn in order to guarantee a win.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a “long long” in C/C++).

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.

SCORING:

  • Test cases 3-5 satisfy N=2N=2.
  • Test cases 6-10 satisfy N,ai≤100N,ai≤100.
  • Test cases 11-20 satisfy no additional constraints.

Problem credits: 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);
    }
}

USACO 2021 February Contest

Weekly Contest 247

Biweekly Contest 55

Codechef Long Challenge Solutions

July Long Challenge 2021 Solutions

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Leave a Comment