[Unofficial] Editorial — Google APAC 2017 Round B

Revision en3, by VastoLorde95, 2016-09-01 12:32:42

Problem A. Sherlock and Parentheses

Category: Ad-Hoc, Math, Greedy

Let's define n = min(L,R). Then the claim is that the sequence ()()...() consisting of n pairs of "()" will give us the maximum answer n*(n+1) / 2

Proof:

Let's look at some sequence T = (S) where S is also a balanced parenthesis sequence of length m. Let's denote by X(S), the number of sub-strings of S that are also balanced and by X'(S) the number of balanced parenthesis sub-strings that include the first and last characters of S (In fact this will be just 1). Then X(T) = X(S) + X'(S).

It should be easy to prove that X'(S) <= X(S) (simply because X'(S) is a constrained version of X(S))

If we rearrange our sequence T to make another sequence T' = "S()", then X(T') >= X(S) + X'(S). The greater than equal to sign comes because we might have balanced sub-strings consisting of a suffix of S and the final pair of brackets.

Thus, we have that X(T') >= X(S) + X'(S) = X(T). Thus by rearranging the sequence in this manner, we will never perform worse. If we keep applying this operation on each string, we will finally end up with a sequence of the form "()()...()" possibly followed by non-zero number of "(" or ")"

Problem B. Sherlock and Watson Gym Secrets

Category: Math, DP

Let's look at all valid pairs (i,j) in which i is fixed. Then, if i^a mod k = r then j^b mod k = (k-r) mod k.

There are only k possible values of the remainder after division. Since k is small enough, if we can quickly determine how many numbers i exist such that i^a mod k = r and j^b mod k = (k-r) mod k then we can simply multiply these quantities and get our answer. Thus the reduced problem statement is —

Find the number of numbers i <= N such that i ^ a mod k = r for all r = 0 to k-1.

Let's denote by dp1[r] = number of i <= N such that i ^ a mod k = r. We will try to compute dp1 from r = 0 to k-1 in time O(K log a)

Let's make another observation —

i ^ a mod k = (i + k) ^ a mod k = (i + 2k) ^ a mod k = (i + x*k) ^ a mod k.

Proof:

(i + x*k) ^ a mod k = (i mod k + (x * k) mod k) ^ a mod k

= (i + 0) ^ a mod k = i ^ a mod k

Now i + x * k <= n. This implies that x <= (n-i) / k.

Thus if we know that for some i <= K, i ^ a mod k is r then there are x + 1 such numbers which also have the same remainder.

This gives us a quick way to compute dp1

for i = 1 to k:
    r = pow(i, a) mod k
    x = (n-i) / k
    dp1[r] += x + 1

Similarly, we can compute dp2[r] which denotes the number j <= N such that j ^ b mod k = r

Now our final answer is the sum of dp1[i] * dp2[(k-i) mod k] for i = 0 to k.

ans = 0
for i = 0 to k-1:
    ans += dp1[i] * dp2[(k-i)%k]

But we need to exclude the cases when i = j.

To handle this we can simply iterate one last time from i = 1 to k and find all the cases when (i ^ a + i ^ b) mod k = 0. and subtract (1 + (n-i)/k) from the answer for all such i

for i = 1 to k
    if pow(i,a) + pow(i,b) mod k == 0:
        ans -= ((n-i)/k + 1)

Problem C. Watson and Intervals

Category: Greedy, Line Sweep

Refer to this comment

Problem D. Sherlock and Permutation Sorting

Tags apac, 2017, google, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en13 English VastoLorde95 2016-10-05 10:51:09 4
en12 English VastoLorde95 2016-10-05 10:49:39 1154 Tiny change: 'um answer n*(n+1) / 2\n\n**' -
en11 English VastoLorde95 2016-09-02 15:10:18 102 Tiny change: 'um answer n*(n+1) / 2\n\n**Proo' -
en10 English VastoLorde95 2016-09-01 20:40:27 0 (published)
en9 English VastoLorde95 2016-09-01 18:15:55 0 Tiny change: 'um answer n*(n+1) / 2\n\n**Proo' - (saved to drafts)
en8 English VastoLorde95 2016-09-01 15:42:14 0 Tiny change: 'equence $($$)$$($$)$$\' -
en7 English VastoLorde95 2016-09-01 13:42:39 44 (published)
en6 English VastoLorde95 2016-09-01 13:41:26 68 (published)
en5 English VastoLorde95 2016-09-01 13:39:03 2284 Tiny change: '_f(n) += (sum over all p' f(p') + 1' - (published)
en4 English VastoLorde95 2016-09-01 13:17:42 4402 Tiny change: '========\n' -
en3 English VastoLorde95 2016-09-01 12:32:42 1267 Tiny change: 'bservation. If i ^ a mod ' -
en2 English VastoLorde95 2016-09-01 12:22:19 1466 Tiny change: 'later.\n\n\n[Probl' -
en1 English VastoLorde95 2016-09-01 11:22:33 1439 Initial revision (saved to drafts)