### ch_egor's blog

By ch_egor, 7 months ago, translation,

Thanks for the participation!

1313A - Fast Food Restaurant was authored by Endagorion and prepared by ch_egor

1313B - Different Rules was authored by meshanya and prepared by DebNatkh

1313C2 - Skyscrapers (hard version) was authored by meshanya and prepared by Sehnsucht

1313D - Happy New Year was authored and prepared by voidmax

1313E - Concatenation with intersection was authored and prepared by isaf27

• +80

 » 7 months ago, # |   +92 How Can I read Such a big editorial for B. havoc editorial to read...
 » 7 months ago, # |   -8 In the B problem, I think we just need to compare a + a with b + c
 » 7 months ago, # |   +52 Solution for B looks like some neural network ;)
•  » » 2 months ago, # ^ |   0 can you explain how to do the problem i am not able to understand the tutorial
 » 7 months ago, # |   +34 Contest has become mathforces with B
 » 7 months ago, # |   +17 All comments are related to B :D
 » 7 months ago, # |   +7 Is there any easier understanding of problem B?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +24 For the minimum possible overall place: For a number $a$ in round 1 and another number $b$ in round 2, we should make sure $a + b \geq x + y + 1$. $1$ should find $x + y$, $2$ should find $x + y - 1$... And if $x + y > n$, $1$ should find the smallest number in round 2 which can be selected.So, we can see that the final answer will be $x + y - n + 1$, cause we can not arrange number $[1, x + y - n]$ to make them greater than $x + y$, and don't forget the ans must in $[1,n]$. For the maximum possible overall place: In round 1, for each number $a$ between $1$ and $x-1$(it can be empty), we can find a number $b$ in round 2, and make $a + b \leq x + y$.In round 2, for each number $b$ between $1$ and $y-1$(it can be empty), we can find a number $a$ in round 1, and make $a + b \leq x + y$.We cannot find any other pairs to make $a + b \leq x + y$. Thus, the answer is $x - 1 + y - 1 + 1$, and don't forget the ans must in $[1,n]$.Let $a = x - 1, b = y + 1$, while $a$ is decreased by $1$, we can add $1$ for $b$. If $b$ is greater than $n$, we can select any number remaining, cause at this time, $a + b < x + y$. To proof the second one, we can just swap the round 1 and round 2.It seems like it's a kind of greedy, but the editorial can proof the answer strictly. And also sorry for my poor English. Wish it can help you. :DUPD: swap((a,b),(x,y)), sorry for the mistake.
•  » » » 7 months ago, # ^ |   +13 what is a & b ?
•  » » » 7 months ago, # ^ |   0 thanks
•  » » » 7 months ago, # ^ |   0 thx, it helped alot
•  » » » 7 months ago, # ^ |   0 For the first case (minimum possible overall place) did you find a+b>=x+y+1 because it will give the count of all the combinations of final ranks which are more than x+y sum's rank? Also, I don't understand what you are saying in the next line ( the x+y>n condition)
•  » » » » 7 months ago, # ^ |   0 Of course, we can't make sure we'll always find such $a$ and $b$ that $a + b \geq x + y + 1$. And at that time, the answer will be increased by 1, because whichever we select the $b$, we can't make $a + b >= x + y + 1$, in other world, the person who get the $a$ place in round 1 will finally placed before Nikolay.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +24 Not sure if it is easier, but I solved it with the following intuition: let's rephrase this task in a different way: you have a square grid of size n. Each participant with scores (xi, yi) will mark one cell with same coordinates. There should be only 1 marked cell on each vertical and horizontal line. Total score of a participant is xi + yi and participants with a same score share same diagonal (from top-right to bottom-down), participants with lower score are on diagonals on the left, and participants with higher score are on diagonals on the right.Now the task is the following — having Nikolay's mark on (x, y) how can we put other marks in order to have max or min number of marks on a right side from Nikolay's diagonal. You can check three cases depending on a position of Nikolay's diagonal from main diagonal x + y ? n + 1, where ? on of <,=,>
•  » » » 7 months ago, # ^ |   0 awesome.
•  » » » 7 months ago, # ^ |   0 Awesome. Thanks for sharing your intuition.
•  » » » 7 months ago, # ^ |   0 Could You please explain "You can check three cases depending on a position of Nikolay's diagonal from main diagonal x + y ? n + 1, where ? on of <,=,>"..How did you determine the position.
•  » » 7 months ago, # ^ |   -8 Fire woman is beautiful!~
 » 7 months ago, # |   -16 can anyone write the bruteforce solution for problem A.
•  » » 7 months ago, # ^ | ← Rev. 4 →   0 The problem clearly states- * All visitors should receive different sets of dishes and each visitor should receive no more than one portion. So, if a b c is the input: Only seven sets are possible they are as follows a,b,c,ab,bc,ca,abc. and their permutations. Here comes the greedy portion. For input: 1 2 2 3 a=2 b=2 c=3 Visitor 1 takes a, therefor new values are: a=1 b=2 c=3 Visitor 2 takes b, therefor new values are: a=1 b=1 c=2 Visitor 3 takes c, therefor new values are: a=1 b=1 c=2 Visitor 4 takes ab, therefor new values are: a=0 b=0 c=2 OUTPUT: a,b,c,ab 4 which is not optimal as (ca and bc) could have served two visitors and (cc) don't satisfy the conditions. For an optimal answer, we first sort all three number in reverse then map values to a, b and c, which are a=3 b=2 c=2 now automatically ab and ac will be chosen. OUTPUT: a,b,c,ab,ac 5
•  » » » 7 months ago, # ^ |   0 thanks sir
•  » » 7 months ago, # ^ |   0 You can check my solution https://codeforces.com/contest/1313/submission/71659186
•  » » » 7 months ago, # ^ |   0 thankyou
•  » » 7 months ago, # ^ |   0 you just if else about 7 case. First you need to sort element to non-decreasing. I call it a[0], a[1], a[2]. a[0] for smallest, a[2] for largest. First 3 case is, a[0] have at least 1, a[1] have at least 1, a[2] have at least 1. For next 3 case is, a[2] and a[0], a[2] and a[1], a[1] and a[0]. For the last case is a[0], a[1] and a[2]. Each food is have at least 1 amount in each if else statement. You should use variable to count how many case above true, each case true you should add 1 to count variable. Then output count as the answer.
•  » » » 7 months ago, # ^ |   0 thank you
•  » » 7 months ago, # ^ |   0 This is how I approached it — https://codeforces.com/contest/1313/submission/71659645
•  » » » 7 months ago, # ^ |   0 thank you
•  » » 7 months ago, # ^ |   0 t=int(input()) for i in range(t): count=0 n,m,r=sorted(map(int,input().split()))[::-1] if n>=1: count+=1 n-=1 if m>=1: count+=1 m-=1 if r>=1: count+=1 r-=1 if n>=1 and m>=1: count+=1 n-=1 m-=1 if m>=1 and r>=1: count += 1 m-= 1 r-= 1 if r>=1 and n>=1: count += 1 r-= 1 n-= 1 if n>=1 and m>=1 and r>=1: count+=1 n-=1 m-=1 r-=1 print(count)
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 @sanjeevkumar113f did ur soln. gave AC?
•  » » 7 months ago, # ^ |   0 You can use Greedy method  /// Sort a > b > c if (a < b) swap(a, b); if (a < c) swap(a, c); if (b < c) swap(b, c); int res = 0; /// Take 1 disk if (c) res++, c--; if (b) res++, b--; if (a) res++, a--; /// Take 2 disks if (a && b) res++, a--, b--; if (a && c) res++, a--, c--; if (b && c) res++, b--, c--; /// Take 3 disks if (a && b && c) res++, a--, b--, c--; cout << res << endl; 
•  » » » 7 months ago, # ^ |   0 thanks
•  » » 7 months ago, # ^ |   +8 Notice that you should take (a-b) and (a-c) before take (b-c) else you will get WA
•  » » » 7 months ago, # ^ |   0 i have sorted them in increasing order i consider them m ,n r this solution is accepted during contestbefore sorting i was getting error what you have noticed
 » 7 months ago, # |   +12 B looks so hard in the editorial:)
 » 7 months ago, # |   +56 I would like to understand D. Why we use bit mask of size k?What does it mean if "we can find free bit and create match to this segment" to create the dp?
•  » » 7 months ago, # ^ |   +2 Let’s imagine this situation. You gave every segment some number 1..k, such there are no intersecting segments with the same number. In this case you can easy maintain dp.When we try to add new segment, we take some remaining color to match it to this segment (you have mask of free colors). So we came back to previous situation.
•  » » » 6 months ago, # ^ |   0 Why no need to consider the combination of segments with same number after numbered them according to your method? According to 71735081 from barakraganosungam, numbers for each segment are determined before doing dp. When leaving color 3 available and color 4 taken, why can't another later segment with number 4 take the available color 3?
•  » » 7 months ago, # ^ |   +31 Suppose we sort and process a start/end event queue over the segments. At each start event, we will assign that segment the smallest integer not in use by another active segment. Since there is no index with more than $K$ segments covering it, during this process we will assign segments at most $K$ unique values.These values correspond to an index of a bit in a bitmask; this bit is on if we currently have this segment selected. Because each index is covered by at most $K$ segments, a bitmask $[0, 2^K)$ can uniquely identify any subset of segments which are crossing some index.Then, you can write a take/leave DP on the segments, and score ranges you cover based on the parity of your bitmask. code
•  » » » 7 months ago, # ^ | ← Rev. 5 →   0 The language of the question is a bit confusing. Does this line — "It is also known that if all spells are used, each child will receive at most $k$ candies." mean that the intervals that are supplied already satisfy this criteria or does it mean that our selection of intervals should be such that this criteria is satisfied (i.e. at most $k$ intervals pass through one point)? because I think only in the latter case this algorithm would work.
•  » » » 7 months ago, # ^ |   +8 thanks a lot
•  » » » 6 months ago, # ^ |   0 Thanks for the hint and code.A side question: no need to worry about stack overflow for recursive dp implementation since N <= 1e5?
•  » » » 5 months ago, # ^ |   0 What happens when a certain bit / color is on and you arrive at a the start of a segment of the same color? Wouldn't it mean that two segments that the parity flips because you now have two segments that don't intersect? I see that you are adding them instead of XOR
•  » » » » 5 months ago, # ^ |   0 Ah, it seems that this cannot happen because if they are of the same color, then they don't intersect, meaning eventA.end < eventB.start. Then therefore, the color / bit would have been switched off before arriving at the start of the new segment.
 » 7 months ago, # |   0 Can someone please help me find error in my logic with question B.my submissionFor minimum case, I started making pairs such that their score is one greater than our score. Then after that, some scores in first contest remain which are greater than a, and some in second contest which are greater than b. we take min of these to give additional people with score greater than us.sg1 = min(n-1-x, y-1)sg2 = min(n-y-1, x-1)og = min(n-x-sg1, n-y-sg2)mn = n - sg1 -sg2 - ogSimilarly I do for max, but for this case, we search for equal score. After that we search for scores less than a in first contest, and scores less than b in second contest. We add min of these to give additional people that may come at or before us in position.gr1 = min(n-x, y-1) gr2 = min(n-y, x-1)ol = min(x-1-gr2, y-1-gr1)mx = gr1+gr2+ol+1
•  » » 7 months ago, # ^ |   0 The answer should in range [1,n].
•  » » » 7 months ago, # ^ |   +3 my god I feel silly now. I only had to change sg1 and sg2 so that they dont go negative! Thanks mate. The problem was that when a, b were last then sg1 and sg2 should have been zero, but I overlooked that issue!
 » 7 months ago, # | ← Rev. 2 →   +18 Problem B For worst rank: Round 1 ......x........ Round 2 ..........y.... The total score needs to be made as greater as possible. So, Step 1 — We can couple entries like (x+1,y-1), (x+2,y-2)..... and (x-1,y+1), (x-2,y+2)..... Step 2 — After this step we will be left with some left out numbers is the first few ranks of few rounds, so we'll couple them together. The reason we are going only for the starting ranks is that coupling of these elements will result in score less than (x+y). For example: Round 1: 1 2 3 4 5(x) 6 7 8 9 10 Round 2: 1 2 3 4 5 6 7 8(y) 9 10 In step 1, we'll couple (6,7),(7,6),(8,5),(9,4),(10,3) and (4,9), (3,10) After step 1, we'll look for the left out ranks among the starting ranks of rounds 1 and 2 --> 1,2 (round 1) and 1,2 (round 2). So, we'll couple them. Answer = 1(including itself) + 5(same score part 1) + 2(same score part 2) + 2(score less than x+y) For best rank: Similar to the worst rank case. Here we will try to make score greater than (x+y). Sum = (x+y+1) will yield the most number of possible results, so we'll aim for sum to be x+y+1 (similar to what we did for sum=x+y in the previous case). Edge case: min(x-1,n-x-1) may produce negative numbers, so we'll need to take max with 0. This will give us the maximum possible number of scores that are greater than (x+y). So we'll subtract this from N. Code for reference: // worst rank part1 = min(x-1,n-y) part2 = min(y-1,n-x) w = part1 + part2 + min(x-1-part1,y-1-part2) worst = 1 + w // best rank part1=min(y-1,n-x-1) part2=min(x-1,n-y-1) part1=max(part1,0) part2=max(part2,0) best = N — (part1 + part2 + min(n-x-part1,n-y-part2)
•  » » 7 months ago, # ^ |   0 I did exactly same as this, but stupidly I didnt do the part1 = max(part1, 0) for best rank. Bye bye expert, on the bright side I can give div 3 ;-)
 » 7 months ago, # |   0 Problem B. I forgot about the borders and place max(1,min(n,x+y-n+1)) wrote max(1,x+y-n+1). and finally I didn't solve the problem during the time of the Contest
•  » » 7 months ago, # ^ |   0 I know that feel, bro
 » 7 months ago, # |   +3 Why cant I view other people's code ? :/
 » 7 months ago, # |   0 What is the approach of finding "nearest" numbers to the right and to the left that are smaller than the current one?
•  » » 7 months ago, # ^ |   0 Maintain a monotonic stack
•  » » 7 months ago, # ^ |   0
 » 7 months ago, # |   0 Can someone tell me what's the problem in this code? https://codeforces.com/contest/1313/submission/71672652
 » 7 months ago, # |   +3 How to search the "nearest" in c2 (second solution)?
•  » » 7 months ago, # ^ |   +1 Pls, check mine, there are comments: https://codeforces.com/contest/1313/submission/71813248stack approach from here helped me: Next smaller element
•  » » » 7 months ago, # ^ |   0 Thanks man
•  » » » 7 months ago, # ^ |   0 This helped me a lot. I never needed nor thought about how to precompute this information. Thank you!
 » 7 months ago, # | ← Rev. 2 →   0 Problem C. in editorial(second solution). please help. can you this code O(n*n) optimize to O(n log n) or O(n). I could not find j faster. for (int i = 1; i <= n; i++) { int j = 0; for (int k = 1; k < i; k++) { if (m[k] <= m[i]) { j = k; } } l[i] = l[j] + (i - j) * m[i]; } 
•  » » 7 months ago, # ^ |   0 you can use segment trees or fenwick trees for log n search of minimum element in a range
•  » » 7 months ago, # ^ |   0 Use a strictly ascending stack (one for L and one for R) — O(n) as every element will only be popped once.
•  » » 7 months ago, # ^ |   0 Only I can't understand the answer of problem C?
 » 7 months ago, # | ← Rev. 2 →   0 Can anyone explain D. What do those bits represent. For ex. what would the state represent, and what does dp calculate (I guess it gives the maximum score for that particular state but I am not sure). I am not getting any ideas. Also, I am not completely convinced -> because for the case when k = 1, this won't work.
 » 7 months ago, # |   0 can someone please share the code of the 1st solution mentioned for c2 problem? it is quite difficult to understand just with the editorial.
 » 7 months ago, # |   +2 What if in C2 we have more than one min element??
•  » » 7 months ago, # ^ |   0 It does not matter, in case it has more than 1 min elements, choose the first one and divide the array into two parts — one that is left to it and one that is right to it. Calculate ans recursively for them
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 S.Jindal I am doing exactly the way you are telling but still I am not able to get the maximum possible answer...can you help my submission 71992921
 » 7 months ago, # |   +3 Please explain solution of problem 'D' in detail
•  » » 7 months ago, # ^ |   +6 Well detailed and explained solution of problem 'D' Dp states explained71761226 Hope it helps :)
•  » » » 7 months ago, # ^ |   +10 good job bro
•  » » » 6 months ago, # ^ |   0 How can we memoize using dp[id][mask] ? The same mask can denote a different set of segments right ?
•  » » » » 6 months ago, # ^ |   0 A mask can represent different set of segments but a mask at a particular 'id' represents a unique set of segments.(This is due to the fact that atmost only 8 segments can be active)
•  » » » » » 6 months ago, # ^ |   0 Is the fact that only 8 segments can be active the only reason why for an id, a mask corresponds to a unique segment set ? I didn't understand how the code is ensuring that a mask for an id is a unique set of segments.
•  » » » 6 months ago, # ^ |   0 for a segment, why is l, r+1 added and not l, r ?
•  » » » 6 months ago, # ^ |   0 Woah
 » 7 months ago, # | ← Rev. 5 →   +5 I am getting Runtime error "Exit code is -1073741571" on problem C2 with C++1471730114while the same code is ACCEPTED with C++17 71727975What could be causing the difference?
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 I looked further into this and surprised to know that stack size limitation is the culprit. Default "8192" KB (in linux) is too low. Setting it to "100000" worked for me, and looks as if a higher value is set for c++17. Not sure what could be the reason for setting this as low for c++14
•  » » 4 months ago, # ^ |   0 https://codeforces.com/contest/1313/submission/81457914took me 2 hrs to understand ur code but i did it ..... thank you very much for posting ur solution , learned a lot about Segment Trees.
 » 7 months ago, # |   +5 In the recursive approach for C2 how to make choice after finding minimum i.e, if we have to recurse on the right or left part?
•  » » 7 months ago, # ^ |   +3 You have to recurse on both the parts and calculate their respective scores. Depending upon which side has better score, you need to set the opposite side to the min value.
•  » » » 7 months ago, # ^ |   0 thanks, but what if there are multiple minima ? do we have to consider any one of those or
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Yes just consider the first such minima (from left) and break the array at the point.
•  » » » » » 7 months ago, # ^ |   0 thanks! so for finding minima(RMQ), we have to use segment tree/ sqrt decomposition. What is the O(N) approach?
•  » » » » » » 7 months ago, # ^ |   0 Sparse table.
•  » » » » » » » 7 months ago, # ^ |   0 sparse table supports query operation in O(1) time but O(N Log N) preprocessing time.
•  » » » » » » » » 7 months ago, # ^ |   0 And segment tree preprocessing is O(N logN)? But with sparse table you can answer RMG query in O(1).
•  » » » » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Segment Tree construction is O(N), because there are ~2*N nodes in the tree and each node needs constant time.Query/Update takes O(Log N) time
•  » » » » » » » » » 7 months ago, # ^ |   0 And solution with segment tree is O(N logN) and with sparse table is O(N).
•  » » » » » » » » » 7 months ago, # ^ |   0 We look to main solution complexity in this we always say that preprocessing take O(NlogN), and solution take O(N).
•  » » » » » » » » » 7 months ago, # ^ |   0 Hi in (C1)easy version problem i have found the minimum element and then found the sum of elements on the left side of minimum and similarly on the right hand side . If the sum on the right side is less than that of left side then then i have assigned minimum value to all elements to the right side and vice versa. can u pls tell why this approach is not working
•  » » » » » » » » » 5 months ago, # ^ |   0 see example 7 2 4 1 2 3 1 2 or other examples which contain duplicates.
 » 7 months ago, # | ← Rev. 2 →   0 Why second solution work(for problem C2), can someone explain?
 » 7 months ago, # |   0 Anyone solve problem B with binary search? Cause this problem has this tag.Please show me.
 » 7 months ago, # |   0 Thanks for the tutorial <3
 » 7 months ago, # |   +1 what stand between me and the rating add,is the math
 » 7 months ago, # |   0 I tried a recursive approach for C1, getting WA can anyone tell me whats going on !!My code
 » 7 months ago, # |   0 I wrote a segment tree & divide and conquer solution for C2, based on the first idea in this tutorial of problem C2. But I get TLE here: https://codeforces.com/contest/1313/submission/71738916. I tried many times at my local machine, using a variant to count the time complex and found the divide and conquer procedure is O(N), and my segment tree is O(17) = O(logN). So I used ST table to reduce complex from O(N logN) to O(N) here: https://codeforces.com/contest/1313/submission/71741474, get Accepted.
•  » » 5 weeks ago, # ^ |   0 What is ST Table ?
•  » » » 5 weeks ago, # ^ |   0 Sparse Table
 » 7 months ago, # | ← Rev. 2 →   0 .
 » 7 months ago, # |   +8 Can anyone just explain D more clearly ? I'm too stupid to understand the given editorial.
 » 7 months ago, # |   -8 How to solve the problem C2 recursively in first solution,isn't it got a comlexity 2^n?
•  » » 7 months ago, # ^ |   0 Learn about sparse table you will get the answer
 » 7 months ago, # |   0 Help needed in problem c2.My approach: for selecting the pick index I calculated the following for each index.sum=dpl[i]+dpr[i]-a[i] here dpl[i] is sum from 1..i making non decreasing segment and dpr[i] is same from n..i for which index I get the maximum sum I selected that index to be the peak index. And then just calculated the final result. Can someone please tell me why this is wrong or any test case? my code: 71701033
 » 7 months ago, # | ← Rev. 2 →   0 In (B) some proofs may become much more symmetrical if you notice that you can make the substitutions $x\leq y$ Change $x,y$ so that (case 1) $x=y$, or (case 2) $x+1=y$. Also an observation is that you don't have to solve a completely new problem for the minimum after solving the maximum problem; specifically if $x+y = c$, then the worst possible for $x,y$ corresponds to the best possible for some imaginary opponent with $x'+y' = c+1$; one just needs to subtract the number of "ties" in the $x',y'$ case, and add in a $+1$ because $x,y$ beats itself.
 » 7 months ago, # |   0 In C2 editorial second soln, what's an optimal way to find "nearest" numbers to the right and to the left that are smaller than the current one.
•  » » 7 months ago, # ^ |   0
 » 7 months ago, # |   0 Can anyone help me with problem Skyscrapers (Hard Version), I am getting memory limit exceeded for my solution I used Sparse Table for finding range minimum query and did a recursive method My submission
 » 6 months ago, # | ← Rev. 2 →   0 There are death of resoures to understand DPBitmasking concept . I am feeling helpless. please someone share enough the resource to get this concept easily. This would also enable me to solve problem D at myown
 » 6 months ago, # | ← Rev. 2 →   0 I struggled a lot with problem C / C2 (skyscrapers). Some comments said to use a monotone stack, which was a big hint, however I have only done a few problems with this approach and I didn't know what the stack actually represents. Finally I came up with it:For now we'll focus our attention on nondecreasing skylines. For every index $i$, we will identify the optimal skyline from index $1$ to $i$ inclusive. For $i=1$, clearly we use $a_1=m_1$. More generally, for $i=1$ to $n$, we push $i$ onto the stack $s$ after popping all elements $j$ such that $m[j]>m[i]$. Finally we push $i$. The stack right now describes the optimal skyline ending at $i$; Specifically, if $s$ contains $i=i_k > i_{k-1} > \cdots > i_1$, then we make assignments as follows: indices $(i_{k-1},i_k]$ get height $m[i_k]$, indices $(i_{k-2},i_{k-1}]$ get height $m[i_{k-1}]$, $\ldots$, and indices $(0,i_1]$ get height $m[i_1]$. It is a little exercise to see that this is a valid assignment and optimal.Let's call $maxIncreasingSkyline[i]$ the sum of the heights of this optimal skyline. It can be computed in amortized $O(1)$ at each step while doing the popping/pushing.One can do the same procedure for nonincreasing skylines, by iterating from $n$ to $1$, and similarly obtain $maxDecreasingSkyline[i]$, which represents the optimal skyline that "begins" at index $n$ and ends at $i$.Now the actual optimal skyline will be one of 3 possibilities: a nondecreasing skyline (whose value is $maxIncreasingSkyline[n]$), a nonincreasing skyline (whose value is $maxDecreasingSkyline[1]$), or a combination of the two, in other words, there is some $j$ such that $maxIncreasingSkyline[j]+maxDecreasingSkyline[j+1]$ is maximal. The latter can be computed in $O(n)$ time since we have already prepared the two arrays. Then one does another linear scan to reconstruct the assignments $a[\cdot]$ from the stack.My submission is here but hopefully the explanation above is adequate.
 » 6 months ago, # |   0 How they created those diagrams for the editorial of B problem ... ???
 » 5 months ago, # |   0 Hardest Div2B ever. Were past Div2B's always this hard? :(
 » 5 months ago, # |   0 In problem C2, what is the neatest way to implement the recursive approach? Recursive approach is prone to exceed the default stack size limit.
 » 5 months ago, # | ← Rev. 2 →   0 I am having problem in problem C1...can anyone plz tell where my code is going wrong?..tried al lot..still test case 9 giving wrongusing namespace std;int main() {ll n; cin>>n;ll a[n],s = 0,m = INT_MAX,ind = -1;rep(i,0,n) { cin>>a[i]; }ll i = 0,j = n-1;while(j>i) { m = LLONG_MAX,ind = -1; rep(i1,i+1,j) { if(m>a[i1]) { m = a[i1]; ind = i1; } } ll s1 = 0,s2 = 0; rep(i1,i,ind) { if(a[i1]>m) s1+=a[i1]-m; } rep(i1,ind+1,j+1) { if(a[i1]>m) s2+=a[i1]-m; } //cout<<"i and j"<<" "<s2) { rep(i1,ind+1,j+1) if(a[i1]>m) a[i1] = m; j = ind-1; } else { rep(i1,i,ind) if(a[i1]>m) a[i1] = m; i = ind+1; }}rep(i,0,n) cout<
 » 5 months ago, # |   0 Are there any restrictions for i = 1 and i = n? see 79077157 for more details. Please someone tell me where my code is not correct. Thanks in advance.
•  » » 5 months ago, # ^ |   0 for problem C1 of div2
•  » » 5 months ago, # ^ |   0 I think that my solution is correct
 » 5 months ago, # |   0 In the first approach mentioned in the editorial for problem C2, how to determine which side(right or left) should be equated to $a_{i}$?
 » 3 months ago, # |   0 Can anyone please explain or tell me why are we creating an array l and r in c2(harder version) and what is algorithm behind that.
 » 3 months ago, # |   0 Solution for C2 using the divide and conquer approach: 85811938
 » 2 months ago, # |   0 EDITORIAL OF C2OBJECTIVE: Find the Optimal Peak by both Methods:Method 1: Create a Segment Tree which returns the index of the smallest element in [l,r].Now , we search for the smallest element in [l,r]. Suppose it is at minindex. Then we make 2 recusrive calls, -> First we assume that all a[l....minindex] have been changed to a[minindex] , so we have a value of a[minindex]*(minindex-l+1) . Then we make the recursive call on [minindex+1,r].-> Second is when we change all a[minindex+1....r] to a[minindex]. Then we have a value of a[minindex]*(r-minindex +1 ). Then we make a Recursive call on [l,minindex-1].In our base case, (l==r) , we have the value i.e. final sum of the array if l(or r) were the Peak. We simply find the Optimal Peak, i.e. the one with max. value. (Have a look at the code, I have made 2 special checks in case [l>r].See just below the recursive calls)Once we have the optimal Peak, we can easily calculate the Array.Method 1 CodeMethod 2: This Method is nicely explained in the editorial. I referred to this to make 2 arrays pre and suf to find the smallest element on the left and right of a[i] with overall O(n).Then I calculate value for each a[i] in left[] and right[] as per described Method in Editorial and found out the Optimal Peak. Then answer can again be calculated easily.Method 2 Code
»
2 months ago, # |
0

Can anyone help me in C1 . I m getting wrong answer at test case 9 . I m using divide and conquer technique .Provide me some test cases or check my soln . 1313C1 - Skyscrapers (easy version)

# include<bits/stdc++.h>

using namespace std;

# define pb push_back

int main() { ll n,i,j,k,l; cin>>n; ll a[n+1]; for(i=1;i<=n;i++){ cin>>a[i]; }

i=1;j=n; while(i<=j){

ll mi=1000000003;
ll pos=-1;
for(l=i;l<=j;l++){
if(a[l]<mi){
mi=a[l];
pos=l;
}
}
if(pos==i){
i++;
continue;
}else if(pos==j){
j--;
continue;
}else{
ll a1=0,a2=0;
for(k=pos+1;k<=j;k++){
if(a[k]>a[pos]){
a2+=a[k]-a[pos];
}
}

for(k=pos-1;k>=i;k--){
if(a[k]>a[pos]){
a1+=a[k]-a[pos];
}
}

if(a1<=a2){
for(k=pos-1;k>=i;k--){
a[k]=a[pos];
}
i=pos+1;
}else if(a2<a1){
for(k=pos+1;k<=j;k++){
a[k]=a[pos];
}
j=pos-1;
}
}

}

for(i=1;i<=n;i++) cout<<a[i]<<" ";

}

 » 2 months ago, # | ← Rev. 2 →   0 Problem C2 2nd solution explanation: From any position find the leftmost smallest building position from the right and get the area. From that position find the rightmost smallest building position from the left and get the area. Sum up both areas to get the total area. Subtract b[i] from that as it is counted twice. so this is the result when b[i] is considered to be the tallest building. Similarly, we will do this for all buildings. The main idea of the solution is to find the optimal tallest building by finding the maximum area. As the width is fixed, so for maximizing the area it is necessary to maximize the height. xianzhi, rmm_0304, Ugnwd, SavicS, dongdziz hope you guys find this useful :D
•  » » 5 weeks ago, # ^ |   0 This illustration is quite useful. Thanks a lot!