### awoo's blog

By awoo, history, 3 years ago, translation, 1469A - Regular Bracket Sequence

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (BledDest)

1469B - Red and Blue

Tutorial
Solution 1 (Ne0n25)
Solution 2 (pikmike)

1469C - Building a Fence

Tutorial

1469D - Ceil Divisions

Tutorial

1469E - A Bit Similar

Idea: BledDest

Tutorial
Solution (BledDest)

1469F - Power Sockets

Tutorial
Solution (pikmike)  Comments (47)
| Write comment?
 » Here is an attempt to make a unofficial video editorial of Educational Round 101 by COPS IIT BHU (in Hindi-English) (Problem A-E).Do check it out. https://codeforces.com/blog/entry/86076
 » 3 years ago, # | ← Rev. 5 →   Pretty optimal solution of D if you fixed 8 and all other numbers from 3 to n-1 divide by n to obtain 1. These numbers are n-4, and after that will remain 9 operations. So you can obtain 1 from n in no more than 6 operations, and 1 from 8 in 3 operations. Since there is don't need to build binary search, this solution will be realised much faster
•  » » same goes to 16. You can fix 16 and then make all elements from 3 to n-1 except 16 to 1 by dividing with n (n-4 steps) and then every possible n will be divided by 16 to 1 in atmost 5 steps and then 16 to 1 in 4 steps by dividing by 2 so total would be n+5 atmost.
•  » » I think you meant 1 from 8 in 3 operations (using 2 as the divisor).
•  » » » Yes, i have fixed
•  » » Thank you so much for this solution.
 » 3 years ago, # | ← Rev. 2 →   I'm little bit confused about this test case for problem A "?))?" shouldn't it return "NO"?Or, am i missing something?
•  » » 3 years ago, # ^ | ← Rev. 2 →   The question mentions that initially there will be exactly 1 opening bracket and exactly 1 closing bracket
•  » » This is not a valid test case for problem A. Unfortunately, I think you missed this statement: "There is exactly one character ( and exactly one character ) in this sequence." (I also missed this statement initially and wasted an hour because of it)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Oh, that's why i couldn't get why they write the same statement twice.I read it like "There is exactly one character ( and exactly one character ).Now i'm clear. Thanks for the clarification.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   This variant would be clearer:There is exactly one character ) and exactly one character (
•  » » » » » Better if the statement like this "There is exactly one '(' and exactly one ')' ..."
•  » » » » » » Exactly one ')' and exactly one '('
•  » » » https://codeforces.com/contest/1469/submission/103575064This solution doesn't care about one '(' or one ')' only
 » 3 years ago, # | ← Rev. 2 →   In problem C, suppose the last fence's ground level is Hn. Why can't Hn be between(inclusive) [mn[n-1]-(k-1),mx[n-1]+k-1]
•  » » According to the problem statement, the first section and the last section must stand on the ground.
•  » » » Yeah Thats what I am saying. In have a range mx and mn fof last second fence bcz it can move. I just wanna check for last fence it it can be somewhere between this range.
•  » » » » You mean your code? Include a link next time then.In your code, looks like the former solution is wrong because it does not update l and r for the last section. Try changing for(int i=1;i
•  » » » » » what if in given qsn C, the height/length of fence is not constant i.e. not 'k' for all.. then how to approach??
•  » » » » » » Have you tried applying the same idea, about going from left to right and maintaining a segment of possible positions?
 » 3 years ago, # | ← Rev. 2 →   Can someone explain C in simpler words , its tricky for me rightnow
•  » » We have got an uneven ground (better if you think of them as unit wide platforms at possibly different heights) with level at point $i$ being $H[i]$ (size $n$).We also have n fence_wood_sections (fws) all of whose dimensions are same and more importantly height being $k$ (width assume unit length) and $i th$ fws is to be placed above point $i$ on the ground (whose height is denoted in H[i]).For all $1 < i < n$ we can keep the distance between ground and bottom of fws at max $k - 1$ (1st and last ones should have 0 distance from their respective ground levels) and each consecutive fws(es) should have a vertical overlap of at least 1 unit (as we need to glue / nail them together as we respect gravity). Now you are to tell whether this is possible to do or not.
•  » » 3 years ago, # ^ | ← Rev. 6 →   Keep the maximum and minimum y-coordinate of bottom each section from left to right. And then don't forget that last section must be in the land (coordinate h[n-1])Let's minimum of the current section is d, and maximum is u. The next section must touch the current one, so difference of its coordinates no more than k-1 by abs. value. Then minimum of the next section is max(h[i], d-k+1) and maximum is min(u+k-1, h[i]+k-1) where h[i] is the height of the next place •  » » » what is a[i] and h[i]?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Height of the place. I forgot replace a[i] with h[i], cos i wrote my code with a[i]
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Why would this always give the answer?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Segment [d1; u1], where d1 and u1 is minimum and maximum for next section, is intersection of segments [d-(k-1); u+(k-1)] and [h[i]; h[i]+(k-1)] So it's possible to choose any coordinate in segment [d; u] for all sections except first and last one
•  » » Now I think you were asking for explanation of solution. Damn me.
•  » » In very simple words, just go from 1 to n just keep track of all allowed bottoms for previous and with that compute the next allowed.It is simple and brute force solution question
 » Ended up doing 1469A — Regular Bracket Sequence using DP. Never read that there are only one '( and')' in the input string. Ended up costing me a lot of time thankfully the constrainst were quite small for a O(1) soln.
 » How to prove in D editorial that number of such segments isn't more than log(log n)?
•  » » This SO answer has a pretty good explanation.
•  » » 3 years ago, # ^ | ← Rev. 2 →   We can observe that left boundary of segment can be represented by $n^{1/2^x}$ where $x$ is number of the segment , now process will stop when $n^{1/2^x} <=2$ , taking log both sides we get $(1/2^x)*logn <= C$ , where $C$ is constant depending on base of log (if base is 2 then C=1).Now equation can be written as $logn <=C*2^x$ . Take log both sides one more time , $log(logn) <= log(C)+x*C$ i.e $(log(logn)-log(C))/C <= x$ hence $x$ is $ceil((log(logn)-log(C))/C)$ , constant factors can be ignored , for log base 2 it will be $ceil((log(logn)-1))/2)$You can read properties of log if you are not able to get some step.
 » /****************************************************************************** Online C++ Compiler. Code, Compile, Run and Debug C++ program online. Write your code in this editor and press "Run" button to compile and execute it. *******************************************************************************/ #include using namespace std; int main() { int t; cin>>t; while(t--) { int m,n; cin>>m; vectorv(m),v1(n); for(int i=0;i>v[i]; cin>>n; for(int i=0;i>v1[i]; int maxi=0,run_max=0; for(int i=0;i<(min(m,n));i++) { run_max+=v[i]; if(run_max>maxi) maxi=run_max; run_max+=v1[i]; if(run_max>maxi) maxi=run_max; } int i=min(m,n); for(int j=i;jn){ run_max+=v[j]; if(run_max>maxi) maxi=run_max; } else if(mmaxi) maxi=run_max; } } cout<
•  » »  int m,n; cin>>m; vectorv(m),v1(n); for(int i=0;i>v[i]; cin>>n; `You declare a vector of lenght "n", while n has an undefined value
 » D problem has cheat-solution.We can for one operation remove number $a_x$ from array if $\exists y, a_x < a_y$. So let's delete all numbers except $n$(we can't remove it). Also we won't delete $2^k, 2, \lfloor{\sqrt{n}} \rfloor$. Using two operations we can divide $n$ to $\dfrac{n}{\lfloor\sqrt{n}\rfloor} = n^\prime$ and $\lfloor{\sqrt{n}} \rfloor$ to $1$. Then let's divide $n^\prime$ by $2^k$ until it is $1$. So if $d(n , k)$ is number of operations needed to divide number $n$ by $2^k$, we need $d(n^\prime, k)$ operations to do it. Also we need to divide $2^k$, it will take $k$ operations. We will use $(n - 5) + d(n^\prime, k) + k + 2$ operations, so we need $d(n^\prime, k) + k + 2 \leqslant 10$, which can be easily secured. In my case $k = 2$ worked. (for all numbers less than $1000$, $d(x, 2)$ will be less than $5$)Maybe we can find such $k$, that we don't need to reduce $n$ to $n^\prime$. It is much easier than author's solution, and also can be easily implemented, and it doesn't need observations like "number of iterations needed sqrt to become 1 is $\log \log n$"
 » It's possible to solve F in $O(n)$.The bound on the $l$ values means these can be sorted in linear time. Moreover, instead of doing range updates, we can simply save where the two ends of the chain currently being used will end. This allows us to just iterate through the $cnt$ array. Solution: 103280970 (unfortunately probably unreadable) and some C++ nerds could probably speed up this idea to get the lowest execution time here too.