Блог пользователя lucifer1004

Автор lucifer1004, история, 4 года назад, По-английски

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
  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +12 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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$$$)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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
  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Test Case
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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....

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

AC-SOLUTION
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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."

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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