Game Theory in Competitive Programming Part 13
Atcoder: Prime Sum Game
Welcome to part 13 of this series, in case you have missed part 12, here is the link: Part 12
Problem Statement
Takahashi and Aoki are playing a game.
- First, Takahashi chooses an integer between A and B (inclusive) and tells it to Aoki.
- Next, Aoki chooses an integer between C and D (inclusive).
- If the sum of these two integers is a prime, then Aoki wins; otherwise, Takahashi wins.
When the two players play optimally, which player will win?
Problem Link
Input
Input is given from Standard Input in the following format:
A B C D
Output
If Takahashi wins when the two players play optimally, print “Takahashi”; if Aoki wins, print “Aoki”.
Example
Input: 2 4 3 4
Output: Aoki
Explanation: Takahashi can choose any number from [2,4] and Aoki can choose any number from [3,4]. If Takahashi chooses 2, then Aoki can choose 3, as 2+3=5, which is a prime number. Similarly for 3 and 4, Aoki can choose 4 and 3 respectively, as they both add up to 7, which is a prime number. So, Aoki wins no matter what Takahashi chooses.
Input: 3 8 2 4
Output: Takahashi
Explanation: If Takahashi chooses 6, then Aoki can form 8,9 and 10 only, and we can observe that all of them are composite numbers. So, Takahashi wins in this case!
Hint
Can we find even a single number in [a,b], suppose x, such that the range [x+c, x+d] has all composite numbers only?
Solution
Whenever Takahashi chooses a number, suppose x, then Aoki can form any number in the range [x+c, x+d].
So first, we observe the range of all possible sums that may arise, which is simply [a+c, b+d].
Our task is to find d-c+1 consecutive numbers in this range which are composite. If we are able to complete this task, then Takahashi wins, otherwise Aoki wins.
Brute Force Approach:
Define variables start = a+c, end = b+d, gap = d-c+1 and countComposite = 0. Then iterate from start to end with a for-loop and check if each number is a prime or not.
If the number is not prime, then increment countComposite by 1.
If the number is prime, check whether the current value of countComposite is greater than or equal to gap. If it is greater, then print “Takahashi” and break from the for-loop.
Otherwise, reset countComposite to 0 and continue with the for-loop. If the for-loop ends, print “Aoki”.
To check if a number is prime, we can define a function checkPrime(int n) which takes the number to be checked as an argument. Inside the function, we can run a loop from i=2 to i=squareRoot(n) and check whether any i is a factor of n.
Time Complexity: O((b+d-a-c)^(3/2))
Space Complexity: O(1)
Optimal Approach:
Generate a sieve of prime numbers till b+d using the Sieve of Eratosthenes method. Create an array (say nums) which stores numbers of prime numbers that are less than or equal to i (0≤i≤201). Now we only need to check if nums[i+d] — nums[i+c-1] is equal to 0 or not for all i [a,b]. (We take nums[i+c-1] because we increment an element in nums[] when we find a prime number and that value remains same for rest of the composite numbers AHEAD until another prime is found)
If we find any i that satisfies the above condition, then we can print Takahashi, else we have to print Aoki.
Time Complexity: O((b+d)*log(log(b+d))) ≈ O(b+d) {as b and d are quite small}
Space Complexity: O(b+d) {to store the sieve}
