Take the min number, and try all 1k possible X sort the numbers, scan from left to right, if num(a[i] ) > num(a[i] + X), bad, otherwise, reduce both a[i] and a[i] + X Note: we can use two pointer techinque here instead of sets, because the first pointer should never catch up with second one because x is positive !!!
Round 45: Remove Update
Use sweep line to calcuate the final results after all updates. and then calculate maxStart[i]= max value in 1…i, maxEnd[i] = max value in i….n
For each segment, the answer is max(maxSeg - segV, maxStart[i], maxEnd[i]), and we take the minimum.
Note that we can use the partial sum trick to simulate operations!!!
- calculate s[i] = a[1] +…..a[i]
- p[l] = v, p[r] = -v
Also, note that to minize max value, we need to consider intervals that contains all maximal values after applying all entries, which is also the max value we are looking for!!! Becaues if the interval does not cover all max As, then the remining max A entry will remain the new max value after removal. Even better, in implementation,we can just assume max value is such for ANY interval anyway, because those do not satify this will not affect our final results - maxStart and maxEnd will cover that!
Round 44: Check DFS
Idea 1
we start with the node, at every step. if p(i) and current stack top is an edge, we add it the stackkeep going. Otherwise, we pop the stack until we have it!, and then add to the stack
terminating condition is we go through all perms
Idea 2
If node v is visited before node u, then we know v can not appear after u in adjacency list. Therefore, we sort adjanent list by the order in permutation!!! In the end do a native DFS and compare orders
Read full article from CS Academy Notes
No comments:
Post a Comment