PROBLEM LINK:
Author: Chandan Boruah
Tester: Hiroto Sekido
Editorialist: Kevin Atienza
DIFFICULTY:
SIMPLE
PREREQUISITES:
Basic trigonometry, counting, arithmetic
PROBLEM:
You are given three numbers, S, C and K. Given S sine functions and C cosine functions restricted in the domain 0 \le x \le 2\pi:
- a_i \sin(2^i x) for i = 0, 1, \ldots, S-1
- b_j \cos(2^j x) for j = 0, 1, \ldots, C-1
Where the a_i and b_j are positive constants, how many points in the x-axis are there where at least K functions pass through it?
Note that it can be easily shown that a_i and b_j do not affect the answer, no matter how they are chosen. They are just there so that the curves can be drawn with any amplitude the author chooses 
QUICK EXPLANATION:
- The only points x we need to consider are those of the form x = \frac{v}{2^M}\pi, where M = \max(S,C).
- Given a v, the number of curves that cross the x-axis at x = \frac{v}{2^M}\pi is only dependent on the number of times 2 appears in the prime factorization of v. Specifically, if this value is e, then the number of curves is \max(0,S-(M-e)) + [0 \le M-e-1 < C] (using Iverson bracket notation).
- One can compute the answer by looping through all possible values of e (0 to M), calculating the number of curves as above, and counting how many v's correspond to that e.
EXPLANATION:
First, we need to understand when exactly these curves intersect the x-axis. Note that these observations can also be derived using simple observations, but one can also derive this otherwise (i.e. using only formulas). We’ll use the latter way so correctness can be seen easily, and we invite the reader to check it using visualization.
When is \sin(2^i x) = 0? \cos(2^j x) = 0?
First, let’s recall one way to define \sin t and \cos t:
- Draw a ray from the origin, with angle t radians clockwise from the positive x-axis.
- Draw the unit circle.
- Then the intersection of these two is the point (\cos t, \sin t).
(One can see it visualized here)
Thus, \sin t = 0 happens exactly when the ray is horizontal, i.e. when t is an integral multiple of \pi. Similarly, \cos t = 0 happens exactly when the ray is vertical, i.e. when t - \pi/2 is an integral multiple of \pi.
Thus, \sin(2^i x) = 0 is equivalent to the following statements:
- 2^i x is an integral multiple of \pi.
- 2^i x = k\pi for some integer k.
- x = \frac{k}{2^i} \pi for some integer k.
Since we only want 0 \le x \le 2\pi, this means that 0 \le k \le 2^{i+1}.
Similarly, \cos(2^j x) = 0 is equivalent to the following statements:
- 2^j x - \pi/2 is an integral multiple of \pi.
- 2^j x - \pi/2 = k\pi for some integer k.
- 2^j x = k\pi + \pi/2 for some integer k.
- x = \frac{2k+1}{2^{j+1}}\pi for some integer k.
Since we only want 0 \le x \le 2\pi, this means that 0 \le k < 2^{j+1}.
This means that there are only a finite number of x's to consider, and they are all of the form \frac{k}{2^i}\pi for some integer k.
Subtask 1 solution
What we did above can actually give us a way to find the answer for the first subtask. Let M = \max(S,C). Then the only x's we have to consider are those of the form x = \frac{v}{2^M}\pi for some integer 0 \le v \le 2^{M+1}. But to do this, we need to find a way to count the number of curves that pass through the x-axis at any given x = \frac{v}{2^M}\pi.
Checking whether \sin(2^i x) = 0 for x = \frac{v}{2^M}\pi
First, fix an i, 0 \le i < S, and say we want to know whether \sin(2^i x) = 0. This is equivalent to saying that x = \frac{k}{2^i} \pi for some integer k, or
- \frac{v}{2^M}\pi = \frac{k}{2^i} \pi for some integer k,
- \frac{v}{2^M} = \frac{k}{2^i} for some integer k,
- v = k2^{M-i} for some integer k,
- 2^{M-i} divides v.
This means that \sin(2^i x) = 0 for x = \frac{v}{2^M}\pi if and only if 2^{M-i} divides v.
Checking whether \cos(2^j x) = 0 for x = \frac{v}{2^M}\pi
Next, fix an j, 0 \le j < S, and say we want to know whether \cos(2^j x) = 0. This is equivalent to saying that x = \frac{2k+1}{2^{j+1}}\pi for some integer k, or
- \frac{v}{2^M}\pi = \frac{2k+1}{2^{j+1}} \pi for some integer k,
- \frac{v}{2^M} = \frac{2k+1}{2^{j+1}} for some integer k,
- v = (2k+1)2^{M-j-1} for some integer k,
- v = K\cdot 2^{M-j-1} for some odd integer K,
- 2^{M-j-1} divides v but 2^{M-j} does not. (In other words, 2^{M-j-1} divides v exactly)
This means that \cos(2^j x) = 0 for x = \frac{v}{2^M}\pi if and only if 2^{M-j-1} divides v exactly.
Thus, given v, the number of curves that cross the x-axis at x = \frac{v}{2^M}\pi can be computed in O(S + C) = O(\max(S,C)) time. Since there are 2^{M+1}+1 points to check, this therefore runs in O(\max(S,C)2^{\max(S,C)}) time. The following pseudocode illustrates it:
def answer_case(S,C,K):
M = max(S,C)
ans = 0
for v from 0 to 2**(M+1) // ** is the exponentiation operator
count = 0
for i from 0 to S-1
if v % (2**(M-i)) == 0
count += 1
for j from 0 to C-1
if v % (2**(M-j-1)) == 0 and v % (2**(M-j)) != 0
count += 1
if count >= K
ans += 1
return ans
We can roughly halve the running time of the above by noticing that \sin(x) = -\sin(x + \pi) and \cos(x) = -\cos(x + \pi), so the intersections at the (0,\pi] interval are exactly the same as those in the (\pi,2\pi] interval. This leaves x = 0 (the origin), which we can consider as a simple special case (there are exactly S curves that pass through the origin!). The following code illustrates it:
def answer_case(S,C,K):
M = max(S,C)
ans = 0
if S >= K
ans += 1
for v from 1 to 2**M
count = 0
for i from 0 to S-1
if v % (2**(M-i)) == 0
count += 1
for j from 0 to C-1
if v % (2**(M-j-1)) == 0 and v % (2**(M-j)) != 0
count += 1
if count >= K
ans += 2
return ans
Fast counting
Unfortunately, the above solution is too slow for the other subtasks. We will need to optimize it. The important observation is this: to compute count, we only need to compute how many times 2 appears in the prime factorization of v. In other words, if v = 2^e d for some e \ge 0 and d odd, then the number of curves that cross the x-axis at x = \frac{v}{2^M}\pi is only dependent on e. This is illustrated in the following code:
def answer_case(S,C,K):
M = max(S,C)
ans = 0
if S >= K
ans += 1
for v from 1 to 2**M
e = 0
d = v
while d % 2 == 0
e += 1
d /= 2
count = 0
for i from 0 to S-1
if e >= M-i
count += 1
for j from 0 to C-1
if e == M-j-1
count += 1
if count >= K
ans += 2
return ans
This code makes it clear how count is actually being calculated: count is simply the number of i's such that 0 \le i < S and e \ge M-i, plus the number of j's such that 0 \le j < C and e = M-j-1. This can be easily computed as \max(0,S-(M-e)) + [0 \le M-e-1 < C] (using Iverson bracket notation). Thus, we can get rid of the two inner for loops:
def answer_case(S,C,K):
M = max(S,C)
ans = 0
if S >= K
ans += 1
for v from 1 to 2**M
e = 0
d = v
while d % 2 == 0
e += 1
d /= 2
count = max(0, S-(M-e))
if 0 <= M-e-1 < C
count += 1
if count >= K
ans += 2
return ans
Note that already we’re down to the complexity O(2^{\max(S,C)}), but it is still far too slow. To really make it fast, we now use the fact that count only depends on e, and not on d. Thus, we can simply loop for all possible values of e (which is just 0 to M), and then count the number of d's that can pair with it, that is, where 1 \le 2^e d \le 2^M and d is odd. But there are exactly \lceil \frac{2^{M-e}}{2} \rceil of those! Therefore, we can speed up the code above to the following:
def answer_case(S,C,K):
M = max(S,C)
ans = 0
if S >= K
ans += 1
for e from 0 to M
count = max(0, s-(M-e))
if 0 <= M-e-1 < c
count += 1
if count >= K
ans += 2*((2**(M-e)+1)/2) // where '/' denotes integer division. Note that
// floor((a+1)/2) = ceil(a/2) for integer a.
return ans
This now runs in O(\max(S,C)) time, assuming one precomputes the powers of two up to M, or simply use bitwise operations (2^M is simply 1 << M)
Finally, one should use 64-bit variables, because \max(S,C) can reach up to 50, so 2^{M-e} will usually exceed the 32-bit limit.
A constant-time solution
As a bonus, we mention that it is possible to improve the answer above even more, down to O(1) time! It is nothing more than fiddling with inequalities and adding up the ranges e that count, so we will leave it as an exercise to the reader. Here is an example of an O(1) solution:
def answer_case(S,C,K):
ans = 0
if S >= K
ans += 3
t = 0
if S >= K
t = (1<<S-K+1)-1
if S <= C
if K == 1
t += 1<<C
t -= 1<<S
else if C <= S-K
t -= 1<<S-K
return ans + (t<<1)
Time Complexity:
O(\max(S,C)) or O(1)