SIGNWAVE - Editorial

PROBLEM LINK:

Practice
Contest

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 :slight_smile:

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) :slight_smile:

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)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

3 Likes

Can anyone please help me to find out what is wrong with my solution? I am getting 1 WA in 1st and last subtask. Here is the link to my solution http://www.codechef.com/viewsolution/6483340

Thank you

Someone please explain me what is wrong with my solution.I have tried a large number of test cases getting the correct result each time.

Also explain how only the third subtask satisfied and not others.
This is the link to my solution: http://www.codechef.com/viewsolution/6481214

Do suggest how while solving a problem I can ensure that all the subtask gets satisfied

Thanks

Can someone please explain, that if s=0 and c=2 and k=1,then logically the solution should be 4 points on x-axis,becoz first cos curve will cut the x-axis on 2 points and the second would cut on 4 points ,so for k=1,the answer should be 2^c=4,but the correct answer seem to be 6.Can some one please explain why the answer for s=0,c=2 and k=1 whould be 6 and not 4.

In case of cos,

“Since we only want 0≤x≤2π, this means that 0≤k<2^j+1,”

Can you please explain how did you arrive at this 0<=k<2^j+1 ?
In case of sin, i get it. But not in cos.

Try substituting k = -1, k = 0, k = 2^{j+1}-1 and k = 2^{j+1} to x = \frac{2k+1}{2^{j+1}} \pi, and see which x s are not in the range 0 \le x \le 2\pi.