Page Contents
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:
- Dividing all of the pile sizes by some positive integer.
- 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
- Clockwise Fence USACO 2021 February Contest
- Just Green Enough USACO 2021 February Contest
- Year of the Cow USACO 2021 February Contest
- Comfortable Cows USACO 2021 February Contest
- Count the Cows USACO 2021 February Contest
- Modern Art 3 USACO 2021 February Contest
- Stone Game USACO 2021 February Contest
- Counting Graphs USACO 2021 February Contest
- Minimizing Edges USACO 2021 February Contest
- No Time to Dry USACO 2021 February Contest
- Maze Tac Toe USACO 2021 US
- Balanced Subsets USACO 2021 US
- Routing Schemes USACO 2021 US
- United Cows of Farmer John USACO 2021 US
Weekly Contest 247
- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony
Biweekly Contest 55
- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System
Codechef Long Challenge Solutions
July Long Challenge 2021 Solutions
- Maximum Production
- Relativity
- XxOoRr
- Optimal Denomination
- K Path Query
- Chef vs Bharat
- Chef and Pairs
- Even Odd Partition
- Dakimakura Distribition
- Madoka and Ladder Decomposition
June Long Challenge 2021 Solutions
- Maximum Frequent Subarray Sum solution codechef
- Dual Distance solution codechef
- Optimal Xor Set solution codechef
- Minimum Subtree Cover solution codechef
- Minimum Dual Area solution codechef
- Bitwise Tuples solution codechef
- Shortest Route solution codechef
- Bella ciao solution codechef
- Summer Heat solution codechef
March Long Challenge 2021 Solutions
- An Interesting Sequence ISS SOLUTION
- Tree House THOUSES SOLUTION
- Valid Paths VPATH SOLUTION
- Modular Equation MODEQ SOLUTION
- Tic Tac Toe TCTCTOE SOLUTION
- Xor Equality XOREQUAL SOLUTION
- Golf LKDNGOLF SOLUTION
- Solubility SOLBLTY SOLUTION
April Long Challenge 2021 Solutions
- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution
February Long Challenge 2021
- 1. Frog Sort Solution Codechef
- 2. Chef and Meetings Solution Codechef
- 3. Maximise Function Solution Codechef
- 4. Highest Divisor Solution Codechef
- 5. Cut the Cake Challenge Solution Codechef
- 6. Dream and the Multiverse Solution Codechef
- 7. Cell Shell Solution Codechef
- 8. Multiple Games Solution Codechef
- 9. Another Tree with Number Theory Solution Codechef
- 10. XOR Sums Solution Codechef
- 11. Prime Game Solution CodeChef
- 12. Team Name Solution Codechef
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef
November Challenge 2020 SOLUTION CodeChef
- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID
October Lunchtime 2020 CodeChef SOLUTIONS
- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP