### lucifer1004's blog

By lucifer1004, history, 4 weeks ago, , 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  Comments (27)
 » 4 weeks ago, # | ← Rev. 4 →   For those who might be interested, here is my O(N) solution to beauty of tree: codedp[i]: 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]: 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.
•  » » I used LCA for doing this question, but this question has a much simpler solution.;)
•  » » » Were you able to do the complete task using LCA ?
•  » » » » 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 .
•  » » » » » Can you please share your kickstart handle, so that I can refer to your submission ?
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →
•  » » » » » » » Link is redirecting to Indian ranklist , just tell your username I will find by myself
•  » » » » » » » » try again
 » Thank you..!
 » 4 weeks ago, # | ← Rev. 2 →   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 ?
•  » » I have explained this part quite in detail in my video from 08:00 to 12:00.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   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 weeks ago, # | ← Rev. 2 →   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 int ans = 0,cnt1 = 1,cnt2 = 1; for(int i = 1; i < k; i++){ if( a[i - 1] < a[i] ){ cnt1++; cnt2 = 1; } else if(a[i - 1] > a[i]){ cnt2++; cnt1 = 1; } if(cnt1 > 4 || cnt2 > 4){ cnt1 = cnt2 = 1; ans++; } } cout << ans << '\n' ; 
•  » » 4 weeks ago, # ^ | ← Rev. 5 →   Please look over my code, I could not find out which cases I am missing, Is my logic correct?
•  » » » I think your code will give 0 on the below test case while the answer should be 1. Test Case181 2 3 4 3 2 1 0
•  » » » » Yaa I got it, Thanks
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   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....
•  » » » 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,1A, B, C, D, Cother possible ordersA, B, C, D, BA, B, C, D, AIn above all orders answer will be 0.
•  » » » » Oo....so if there were 600 at last position, that would give us a break of sequence....and thus ans = 1....
•  » » » » » Yes. You are right.
•  » » » » » » Thanks man for taking time to ans this silly question... appreciate it
 » This is something which I needed badly, tanks to CF and you!!!!!!
 » 4 weeks ago, # | ← Rev. 2 →   A neater solution to problem C(Beauty of tree) : AC-SOLUTION// credits William Lin #include using namespace std; #define ld long double #define int long long #define ar array #define pb push_back #define vi vector #define FOR(i,n) for(int i=0;i adj[mxN] ;ld ans=0 ; int n,ca[mxN],cb[mxN],a,b; void dfs(int v=0,int p=-1,int d=0){ int la = ca[d%a],lb=cb[d%b]; ca[d%a]++;cb[d%b]++ ; for(int x:adj[v]) if(x^p) dfs(x,v,d+1); int na = n-(ca[d%a]-la),nb = n-(cb[d%b]-lb); ans+=1.0-na*nb/(ld)n/n ; } void solve(){ ans=0 ;cin >> n >> a >> b ; FOR(i,n-1){ int p;cin >>p;--p; adj[i+1].pb(p);adj[p].pb(i+1); } memset(ca,0,sizeof(ca)); memset(cb,0,sizeof(cb)); dfs();cout << ans << "\n"; FOR(i,n) adj[i].clear(); } signed main() { cout << setprecision(20) << fixed ; int t;cin >> t; FOR(_,t){ cout << "Case #" << _+1 << ": "; solve(); } } 
•  » » I think you should give credit of code to William Lin because your code is exactly match with his solution code
•  » » » It's William Lin himself on his alt account
 » 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 weeks ago, # | ← Rev. 2 →   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