lucifer1004's blog

My Editorial for Google Kick Start 2020 Round D
By lucifer1004, history, 4 years ago, In English

Problems

Problem A — Record Breaker

Implementation. Keep a record of the current maximum. Compare the current value to it, and also to the next number.

Time complexity is $$$O(N)$$$.

Code

Problem B — Alien Piano

Simple DP. Enumerate all choices of the last step and the current step.

Time complexity is $$$O(P^2K)$$$, where $$$P=4$$$ in this problem.

Code

Problem C — Beauty of Tree

Inclusion-exclusion, DFS.

We need to find, for every node, the number of descendants has a distance that can be divided by $$$A$$$, and similar for $$$B$$$. This can be done during DFS if we keep a record of the current path.

After having $$$ca[i]$$$ and $$$cb[i]$$$, we can simply calculate how many times the current node will be counted, via inclusion-exclusion:

$$$t[i]=(ca[i]+cb[i])\cdot N-ca[i]\cdot cb[i]$$$

Then we add up all the results and divide it by $$$N^2$$$.

The total time complexity is $$$O(N)$$$.

Code

Problem D — Locked Doors

I used a rather complicated algorithm leveraging monotonic stack, sparse table and binary search.

For each door, calculate the first door to its left having higher difficulty, and the first door to its right having higher difficulty. For simplicity, a door with infinite difficulty is added at either end. This part is done by monotonic stack in $$$O(N)$$$.

Then construct a sparse table for range maximum query in $$$O(N\log N)$$$.

In each query, on the $$$K_i$$$-th day, there will be $$$K_i-1$$$ opened doors. Some are to the left of the $$$S_i$$$-th room, while some are to the right. If there are $$$l$$$ opened doors to the left on the $$$K_i$$$-th day, there needs to be at least $$$f(l)$$$ opened doors to the right, so that the highest difficulty among the $$$f(l)$$$ doors to the right is higher than the highest difficulty among the $$$l$$$ doors to the left. An observation is that $$$l+f(l)$$$ is monotonic. So the suitable $$$l$$$ can be found via binary search.

The last step is to determine whether we should use the leftmost room or the rightmost room. This can be done by comparing the highest difficulty of the doors to the left and those to the right. If the highest difficulty is to the left, then on the $$$K_i$$$-th day we must be in the leftmost room, otherwise rightmost.

The total time complexity is $$$O((N+Q)\log N)$$$.

Code

Heltion's Cartesian tree solution.

Code
  • Vote: I like it
  • +65
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
»
4 years ago, # |
← Rev. 4   Vote: I like it +12 Vote: I do not like it

For those who might be interested, here is my O(N) solution to beauty of tree: code

dp[i][0]: number of nodes in the subtree of node i such that they are at a distance of 0, a, 2a, 3a.... from node i.
dp[i][1]: number of nodes in the subtree of node i such that they are at a distance of 0, b, 2b, 3b.... from node i.

I will be adding a detailed video explanation on my YT channel by tonight and will add link in this comment :)

Video Explanation: Well detailed Explanation
Have added timestamps in a comment to save you some time.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I used LCA for doing this question, but this question has a much simpler solution.;)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Were you able to do the complete task using LCA ?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I use dp[nod] which tell me how many child is at ath distance from the current node. so the transition is dp[node] += d[child at ath distance] , so for finding ath node i use LCA .

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem Beauty,

Can You explain why are we adding the probabilities ? From what I know about expectations is that the answer should be,

$$$\sum_{i=0}^{n} i*P(i)$$$

Where $$$P(i)$$$ is the probability of $$$i$$$ number of nodes being selected,

How is the sum of all the probabilities of number of times each node occurs is equivalent to the above expression ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I have explained this part quite in detail in my video from 08:00 to 12:00.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    You should look for "Linearity of Expectation". The number of nodes selected ($$$X$$$) can be written as summation of all $$$X_i$$$ where $$$X_i$$$ is an indicator variable (1 if node $$$i$$$ is selected otherwise 0). Therefore, E($$$X$$$) = Summation of all E($$$X_i$$$)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You can solve B easily without DP.

Just keep track of how long the increasing or decreasing subarray you got and if it's length is more than 4 then increment your answer.

Here is my code. Here cnt1 is for increasing and cnt2 is for decreasing subarray'slength.

Spoiler
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Please look over my code, I could not find out which cases I am missing, Is my logic correct?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think your code will give 0 on the below test case while the answer should be 1.

      Test Case
      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi i am still unable understand prob 2 correctly. If we have to find when the aliens piano goes out of sequence we do ans++,but in the first test case it is 1,5,100,500,1. Why doesn't we add ans++ when at last element i.e. 1 since it decreases from the current increasing sequence....

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Suppose Alien piano has four notes A,B,C and D.

      These notes pitches are in increasing order. A < B < C < D.

      Now we can assign this four notes in the below order.

      1,5,100,500,1

      A, B, C, D, C

      other possible orders

      A, B, C, D, B

      A, B, C, D, A

      In above all orders answer will be 0.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oo....so if there were 600 at last position, that would give us a break of sequence....and thus ans = 1....

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A neater solution to problem C(Beauty of tree) :

AC-SOLUTION
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I think you should give credit of code to William Lin because your code is exactly match with his solution code

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, could anyone explain this part more clearly? I am unable to get it.

"If there are l opened doors on the Ki-th day, there needs to be at least f(l) opened doors to the right, so that the highest difficulty among the f(l) doors to the right is higher than the highest difficulty among the l doors to the right. An observation is that l+f(l) is monotonic. So the suitable l can be found via binary search."

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

My solution to 4th problem is similar to that of the editorial presented in this blog.

Let start be the starting room and k > 1.

Key takeaways:
1. Either Kth Room lies in [1,start-1] or [start+1,N]
2. Assume it lies in [1,start-1], pick any room X in the range [1,start-1]. Check if X is the Kth Room to be explored.
3. How do I check that? If X is the Kth room to be explored then 1 thing is that before we reach Room X we should have already explored Room X + K but No room to the right of room X+K must be explored before exploring room X.
This would suggest that atleast 1 door in range X to start — 1 must be harder to open than all doors in range start to X+K-1(the door you need to open to reach room X+K)
4."but No room to the right of room X+K must be explored before exploring room X" this would suggest that there should be no door harder to open in the range X to start-1 when compared to door X+K.

If both conditions are true we found our door, otherwise depending upon which of the two conditions (3),(4) fail re-adjust the search range and do a binary search.

If door isn't in left range, then use same idea for right range.

Poorly Implemented AC code: Will only see solve function

→ Reply