### awoo's blog

By awoo, history, 4 years ago, translation,

Idea: Roms

Tutorial
Solution (Roms)

1398B - Substring Removal Game

Idea: BledDest

Tutorial
Solution (Ne0n25)

1398C - Good Subarrays

Idea: Roms

Tutorial
Solution (Roms)

1398D - Colored Rectangles

Idea: BledDest

Tutorial
Solution (pikmike)

1398E - Two Types of Spells

Idea: Roms and BledDest

Tutorial
Solution (Roms)

1398F - Controversial Rounds

Idea: Roms

Tutorial
Solution (Roms)

1398G - Running Competition

Idea: BledDest

Tutorial
Solution (BledDest)
• +76

| Write comment?
 » 4 years ago, # |   -30 How to solve e
 » 4 years ago, # | ← Rev. 2 →   0 Can someone give an example of why greedy solution for D is incorrect?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 2 3 12 53 4 46Greedy will give : (6,5)+(4,2) = 38 But we can take (5,4)+(4,6)+(2,3) = 50
•  » » 4 years ago, # ^ |   +26 Consider the case 1 1 2 20 20 19 19 As you can see the optimum answer is 760, but greedy would give 400, issue being greedy only cares about maximum values, and not take into account the number of pairs available of each color.
•  » » 4 years ago, # ^ |   +3 Take Case 1 1 2 15 12 10 10 Greedy will give 15*12=180while maximum will be 15*10+12*10=270
•  » » 4 years ago, # ^ |   +3 Simplest counterexample: 1 1 2 3 3 2 2 Greedy will give 3*3=9 but we can do better with 3*2+3*2=12.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 3 3 3 3 4 4 4 4 Greedy = 16 + 16 = 32dp = 4*3 + 4*3 + 4*3 + 4*3 = 48
 » 4 years ago, # |   0 Please tell me in C why are we initializing the mapped value of 0 as 1
•  » » 4 years ago, # ^ |   +1 Because there is an empty prefix of length 0. So if any other prefix itself will be a good prefix then it should also be counted in answer, so it is paired with an empty prefix of length 0.
•  » » 4 years ago, # ^ |   +1 Because consider you don't initialise m[0] with 1, then if you come across a subarray of sum = 0 for the first time then you won't consider it as your answer, but indeed it should have been counted in your answer. Hope it helps :)
 » 4 years ago, # |   0 Can someone please tell me what am I doing wrong in C? Please help!Here is my code
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Your code doesn't take into consideration the subarrays that begin at the index 0. You need to initialize the answer with mp[0], not 0.
•  » » » 4 years ago, # ^ |   0 Can you please explain a little bit more? I still didn't understand.
•  » » » » 4 years ago, # ^ |   0 Yo have to take a zero value initially ,for the empty string part. for index 0 take value as zero and build a prefix array with 1 indexing on top of that.Otherwise you woould leave that edge case from consideration for example if string starts from the index zero itself.
•  » » » » » 4 years ago, # ^ |   0 Finally understood. Thanks a lot for your help.
•  » » » 4 years ago, # ^ |   0 And consider the case where "...20..."The prefix sum contains after first step the same value at both positions, after decresing by i two different values. But you would like to match those two positions, because it is a good subarray of size 2.
•  » » 4 years ago, # ^ |   +3 You need to initialise mp[0] as 1 , not 0. This is because if the sum of a prefix of the array is 0, you need to consider this prefix. If mp[0] is initialised as 0 you will not add such prefixes to the answer. Also you need to change ++mp[pref[i]-i] to ++mp[pref[i]-(i+1)] as the array indexing is 0 based.
•  » » » 5 weeks ago, # ^ |   0 why we need to do ++mp[pref[i]-(i+1)] instead of ++mp[pref[i]-i]?you said as it is 0 based indexing but I didn't get you? can you elaborate
 » 4 years ago, # |   +30 If you prefer a video format for solutions, I explain A-E here (timestamps are in the description).
•  » » 4 years ago, # ^ |   +10 Your video was awesome!!
•  » » 4 years ago, # ^ |   0 Good work.Thanks!
 » 4 years ago, # |   0 Here is a solution for Problem C using naive O(n2) solution and pragmas. https://mirror.codeforces.com/contest/1398/submission/90028294
•  » » 4 years ago, # ^ |   0 I used same approach still getting TLE on test case 3, link to my code is given below. Can you please tell me why it's giving TLE for the same logic: https://mirror.codeforces.com/contest/1398/submission/90044479
•  » » » 4 years ago, # ^ |   0 Add the three first lines i've written in my code. It makes the O(n2) solution faster
•  » » 4 years ago, # ^ |   0 Hello, TANGRA can u explain what are you doing, and what are pragmas. I'm a newbie
•  » » » 4 years ago, # ^ |   0 You can learn more about pragmas here https://mirror.codeforces.com/blog/entry/66279
•  » » 4 years ago, # ^ |   0 I used the same approach and added pragmas also, but still getting TLE on test 3. Please tell me where i am doing wrong. https://mirror.codeforces.com/contest/1398/submission/90298210
•  » » » 2 years ago, # ^ |   0 How is your code working @white_dwarf The first iteration I = 0 and j = 0 in that you will get -1 as the index
 » 4 years ago, # |   0 how People did 1398E - Two Types of Spells with segment tree?
•  » » 4 years ago, # ^ |   0 I think seg tree + binary search in this case could be used to get the answer to: What is the sum of the K greater spell powers? (but I think using two sets is way easier)
 » 4 years ago, # |   +31 I had a solution for F that also uses the harmonic numbers for $O(n \log n)$, but is otherwise very different.First, let's get rid of $?$'s that aren't unclear at all. If a block of $?$'s is bordered by the same number on both sides, or an end of the string on one side, we will only ever assign either $0$ or $1$ to these $?$. So just do that now.Now $s$ consists of alternating blocks of $0$'s and $1$'s with some $?$'s in between. Lets find all these blocks, and for each of them save $l$, the number of consecutive $?$'s to the left of the block $m$, the length of the block $r$, the number of consecutive $?$'s to the right of the block Going through these blocks left-to-right, we can greedily create $\lfloor\frac{l+m+r}{x}\rfloor$ blocks of size $x$ from a block. If we use some of the $r$ $?$'s to the right, we save that and adjust the next blocks $l$ value accordingly.To get to $O(n \log n)$, we consider that only blocks with $l + m + r \geq x$ are interesting to us. By increasing $x$ from $1$ to $n$, we can discard blocks whenever $l + m + r < x$. Since every character is counted for at most two blocks ($1$ block for $0$ and $1$, $2$ for $?$), there is at most $\frac{2n}{x}$ blocks for every value of $x$. Thus, the overall runtime is $O(n \log n)$.
•  » » 2 years ago, # ^ |   0 Doesn't this work in O(n) (if we are processing each block in O(1) as it requires just a division) as each block will be visited and accounted for at max l+m+r times, after which it is discarded. Since summation l+m+r over all blocks is bounded by 2*n. Hence we can attribute a cost of 2 to each character in amortised analysis and get an O(n) analysis.
 » 4 years ago, # |   0 The tutorial of D saids that we should choose larger sticks, and the code also sorts length in decreasing order. However, sorting length in increasing order also gets AC though I cannot clearly explain it. Does anyone have explanation or proof for this?
•  » » 4 years ago, # ^ |   +4 You initialized all the values of dp with $0$. Thus, you allowed it to skip any number of sticks from the prefix of any color. So as long as the suffix of each set is taken and the values are matched in the same sorted order, it gives the same answer.
 » 4 years ago, # |   0 In D, since the dp will iterate over all the possible combinations, why does sorting the array matter?
•  » » 4 years ago, # ^ |   0 It matters because if for the current dp state we're using some previous dp states, then we have to have already computed those previous dp states
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 Try this test case: 1 3 6 2 8 6 7 5 2 4 1 10 4 If you don't sort the arrays, your solution gives 142 and the optimal is 147, this is because it's optimal to take (10,8) and (7,5) and is impossible with the arrays unsorted (those pairs cross each other)
•  » » » 4 years ago, # ^ |   0 I got it. Since we may be skipping some of the pairs, its better to sort them first so we only pick a pair of larger length. thanks.
 » 4 years ago, # | ← Rev. 2 →   0 I like problem E very much. The same method as solving Dynamic median number problem by two Binary Beap(s) , but not easy to discover for me. Thanks a lot.
 » 4 years ago, # | ← Rev. 2 →   0 .
 » 4 years ago, # |   0 Problem G — I managed to get by using bitset to get all available sizes of horizontal segments. Run time is 1900ms ... I guess I'm lucky. (Submission 89952340)FFT is the way to go!
•  » » 4 years ago, # ^ |   +8 Actually, you can get even faster bitsets which fit comfortably in the time limit. Example: 90376940. I think this is because the pragmas (in particular -Ofast and -unroll-loops) improve performance significantly on bitsets.
 » 4 years ago, # |   0 plz someone help me with C problem,i couldn't understand it.
•  » » 4 years ago, # ^ |   0 I read this solution in the Announcement. But for problem C, You can subtract 1 from every term and the problem reduces to finding subarrays with sum 0 which is pretty standard.
 » 4 years ago, # |   0 Hello all, These are the links of my two submissions for problem D : 1. Accepted Solution 2. Getting runtime error on test case 14The only difference between the two submissions is in the size of vectors which I am using for storing the lengths of red, green, and blue sticks. In the second submission, the size of vectors exactly matches the number of sticks while in the accepted submission the size of vectors is 1 more than the number of sticks.In the whole code, I have made sure that I am never referencing any index which is out of bounds for the vectors. But still, I am getting runtime error on test 14 when I am using vectors of the exact size.It would be really helpful if someone can let me know the reason for this.
 » 4 years ago, # |   0 Why does priority queue is not working in 1398D - Colored Rectangles? we need to select two largest values each time and if all have equal then we will select two values from that queue which has larger size. Getting wrong answer on test case 7 My code submission[submission:89996393] Please help .
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Taking the largest wont work everytime beacause you could take two smaller values which add up greater than the larger one. Try this: 1 2 1 10 9 3 11 You could take 10 and 11 to get 110. But the optimal solution: 9*11 + 3*10 = 123
 » 4 years ago, # |   0 I read this solution in the Announcement. But for problem C, You can subtract 1 from every term and the problem reduces to finding subarrays with sum 0 which is pretty standard.
•  » » 4 years ago, # ^ |   0 yeah, I also did it that way.
 » 4 years ago, # |   0 Why there is a greedy tag on the problem D?
•  » » 4 years ago, # ^ |   +1 Picking numbers from largest to smallest is itself greedy I guess
 » 4 years ago, # |   0 Is there any implementation of E using segment trees for finding k maximums combining the two different set of elements.
 » 4 years ago, # |   0 Please can anyone tell why we need to sort the arrays before applying dynamic programming in problem D. Since we are calculating all the states of the DP isn't it unnecessary to sort them? However I get WA on test case 5 without sorting. Thanks in advance.
•  » » 4 years ago, # ^ |   0 It's necessary to sort as we need to proceed greedily. product of two numbers a*b is maximum when a is closer b. So, thereby sorting we are ensuring that we proceed on path of maximum value.
 » 4 years ago, # |   0 What means ld x = .0?
 » 4 years ago, # | ← Rev. 2 →   +7 The code of problem E is so short that it really does shock me.
 » 4 years ago, # | ← Rev. 3 →   +2 Div. 2 Educational round with FFT task? Are you kidding?
•  » » 4 years ago, # ^ |   0 Cause of we don't have Div 1 ER)
 » 4 years ago, # |   0 My recursive solution for problem D : https://mirror.codeforces.com/contest/1398/submission/90893065
 » 4 years ago, # | ← Rev. 2 →   0 problem E:Can anyone tell me what's wrong with this code as this is giving TLE on test 47. TIA.
 » 4 years ago, # |   0 I think there is a typo in the problem E editorial that confused me a little."All we have to do it maintain the set of x largest by power spells"Instead, i think it should be."All we have to do it maintain the set of x largest power spells"
 » 7 months ago, # | ← Rev. 3 →   0 Seems like $a-b=c-d$ identity is important to know in CP, its not the first time I saw itIf you never thought about it, you can still solve the problem C by subtract $1$ from each element in $a$. Then you are just finding $p_r-p_{l-1} = 0 \rightarrow p_r=p_{l-1}$.