### awoo's blog

By awoo, history, 4 years ago, translation, 1132A - Regular Bracket Sequence

Tutorial
Solution (BledDest)

1132B - Discounts

Tutorial
Solution (Roms)

1132C - Painting the Fence

Tutorial
Solution (BledDest)

1132D - Stressful Training

Tutorial
Solution (PikMike)

1132E - Knapsack

Tutorial
Solution (BledDest)

1132F - Clear the String

Tutorial
Solution (Roms)

1132G - Greedy Subsequences

Tutorial  Comments (51)
| Write comment?
 » My solution for C: Make an array a of n vectors where ai contains all the painters who paint the ith panel. Find 'total', the total number of painted panels using all of the painters. Then, we make a 2D array 'count' that is initialized to 0. Here, 'count[i][j]' is 'the number of sections that have no one painting them if i and j are removed.So, loop over all elements of a. If a[i].size()==2, then count[a[i]][a[i]]++ and count[a[i]][a[i]]++. If a[i].size()==1, then for all j ≠ a[i], perform count[a[i]][j]++ and count[j][a[i]]++. Then, simply find the minimum value of count[i][j], and subtract that from total to get your answer. Solution works in O(n2).This took me an embarrassing amount of time to figure out, and, in addition to my A getting hacked (due to a REALLY embarrassing careless mistake which wasn't caught in the pretests), my rating really took a hit this contest :'( Which is such a shame because I got F pretty early and I thought this contest was gonna be one of the good ones... from 3rd place to 900something, lmao. Someone play Viva la Vida.
•  » » By the way, great contest! I wasn't able to get E, but i especially like it and shall try upsolving it later. The problems seem really interesting and generally should have been doable if I didn't choke so hard — oh well. My only comment is that F is WAY easier than E and D, and perhaps even C for a lot of us.
•  » » I did the same thing but without the crucial if(section[j].size() < 3) so it got MLE hacked. Although why exactly it MLE on that specific hack is still unclear to me.
•  » » » Oh wow, I did have that < 3 check in my solution, yeah. I didn't think it'd end up being important! That's a weird MLE
•  » » can you please share your submission on problem c. I am still struck on it. Thanks in advance
•  » » » #include #include #include #define N 5000 using namespace std; vector section[N+1]; int count[N+1][N+1]; //Get i and j bool covered[N+1]; int main() { ios::sync_with_stdio(false); cin.tie(0); memset(covered,false,sizeof covered); int n, q; cin >> n >> q; for(int i = 0; i < q; i++) { int u, v; cin >> u >> v; for(int j = u; j <= v; j++) { if(section[j].size() < 3) section[j].push_back(i); covered[j] = true; } } int total = 0; for(int i = 1; i <= n; i++) total += covered[i]; memset(count,0,sizeof count); for(int i = 1; i <= n; i++) { if(section[i].size()==1) { for(int j = 0; j < q; j++) if(j!=section[i]) count[section[i]][j]++, count[j][section[i]]++; } else if(section[i].size()==2) { count[section[i]][section[i]]++, count[section[i]][section[i]]++; } } int minnie = 1000000000; for(int i = 0; i < q; i++) for(int j = i+1; j < q; j++) minnie = min(minnie,count[i][j]); cout<
•  » » » » Can you please explain why did you ignore the painters when it's more than 2? if(section[j].size() < 3) section[j].push_back(i);
•  » » » » » We only care about the sections that could become unpainted if we removed 2 painters. If there are at least 3 people painting a section already, then no matter who you remove, that section is already 'locked in'.Sorry for not responding to your other comment. I generally don't like debugging other people's code for them. But I think taking the min(ans) at each iteration of the loop is a mistake — if you look at my code, i have a big 2D array, do all the computations, THEN find the minimum at the end.
 » Third question is little bit more tricky from last div2"s third question.
•  » » I agree, that was much harder than C questions normally are. I think the next easiest question after B is actually F (which is a standard and straightforward DP)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   Depends on how good you are with DP, I solved C and D, and found both of them pretty straight forward to be honest, the only thing was that the time limit for D was a bit tricky, but it took me quite a while to upsolve F after the competition ended actually. While I'm not completely hopeless at DP I still have a bit to go before I'm completely comfortable with it though.
 » Can someone explain problem F with example, I am not able to understand the dp state
•  » » 4 years ago, # ^ | ← Rev. 2 →   1.let str[i][j] (i<=j) be the string formed by characters between ith and jth characters (inclusive). 2.define dp[i][j] to be the minimum number of steps to remove all the characters of str[i][j]. 3.This removal can be done in two ways. i.remove the jth character on its own, in this case dp[i][j]=1+dp[i][j-1] ii. dont remove the jth character on its own. rather remove it another character same as the jth. there may be many such characters . let nth character be same as jth and of course i<=n
•  » » » But this approach isn't taking into consideration if deleting jth elements say all three together. i.e. adaba, suppose (1-base indexed) j be 5, then we will only be checking if aa(1, 5) or aa(3, 5) or a(5) can be deleted together, why shouldn't we check deleting together aaa(1,3,5) ?
•  » » » » if u want to delete aaa then first u have to get aa . then we will get aaa
•  » » » » » that's my point, if we already got aa and you are deleting it in one operation, next time you have to delete remaining 'a' in another operation- thus increasing the deletions to 2, instead of 1.For example, I was going with this greedy approach first compress the string, i.e. compressed array will have all the adjacent elements different, (e.g. aaabbabb changes to abab). Then I was solving it considering the element with highest freq. to be deleted as the last all together. Its failing on 5th test case. But this approach of mine only covers the fact that, all occurrences of highest freq. element must be deleted all together at last — that's why this dp based question is still bugging me :(
•  » » » » » » However ur greedy technique is wrong . Try this one 7 acbabca correct answer : 4 but ur greedy technique outputs 5
•  » » » » » » » Thanks for such a short test case, will look into the dp based approach carefully then :)
 » My solution for E:Notice that if the total sum is bigger or equal than W, the answer must be between W-8 and W. So I approached the total sum to between W and W+8 by greedly removing the itens and then I checked if I could remove the difference between the actual sum and the answer, this could be done using smaller knapsacks as the difference would be no more than 16 (W+8-(W-8)).
•  » » thanks for awesome tip.
•  » » The cool part is that this solution can solve the same problem with a larger limit and the knapsacks can also be optimized by using bitmasks. :)
 » Could someone please explain me why did my code get accepted? (I have no idea O.o, i thought that a pseudo brute force should work but i'm not sure why or maybe there are weak test cases, idk)My codeThanks in advanced.
•  » » Please take a look at this code. It is as yours but I just reduce the number of iterations performed by you in outermost for loop(100 -> 2) and it still gets accepted.
•  » » 4 years ago, # ^ | ← Rev. 4 →   Interesting, but yes you were just lucky. Your code fails on 5406 0 0 0 0 44500000 0 31700000 449000000 Basically take any test case that doesn't work with attempting greedily adding as much as you can from all permutations, and then just make sure that you more than max(j) (which is 100 in your case) extra of each type needed and it'll break. Like this you would need a j of about 10^16 for your code to passEdit: This is test case 21 from system tests with zeros added to each of the counts, your code outputs 5405 when it should output 5406Edit2: Even simpler. Actually it's so easy to break. Take this case: 18 0 0 0 0 100000 0 0 100000 The answer is simply take 2 5s and an 8, but your code outputs 16 as it always tries either 3 5s first or 2 8s which won't work
 » I am not able to understand the solution of E .can some one elaborate it,please?How the equation could be written like this ? Thank you in advance.
 » I solved C in something like O(nlog(q) + q^2).Keep two prefix sums of how many segments are covered by exactly 1 and exactly 2 painters respectively. You build these in O(nlog(q)) with a sweep line over the n segments keeping track of how many painters are in each. Also keep just a single integer keeping track of how many total segments are covered by at least one painter.Now iterate over each pair of painters and for each pair take the number of segments covered by any painter and subtract from this number the number of segments which only 1 painter (this painter) covers. Then if they intersect subtract the number of segments with exactly two painters covering it (exactly these two painters). This can all be done in O(1) because of the prefix sums built before. In my code I also added back in the number covered by exactly 1 in the intersection but as I'm writing this I see that it's of course always zero as two painters are intersecting, so it's redundant.
 » there is a typo in the tutorial of F:clear the string. It should be s_i = s_l.
 » In C,my thought process was in the following direction. Sort all the pairs according to their interval length and then iterate over each interval along with maintaining a boolean array to mark which sections are painted.Can we reach the solution using this approach,if yes how?
•  » » 4 years ago, # ^ | ← Rev. 2 →   I don't think so. As it's not only the length it's also the position. Imagine this list of segments 0 5 0 4 0 3 0 2 0 1 6 6 7 7 Obviously the answer would be taking the 0-5 interval, the 6-6 and 7-7 interval and then all rest are redundant but your algorithm would take the 0-5 interval and then the 4 redundant ones
 » Can C be solved using segment trees? If yes, then can someone please share an efficient solution?
•  » » It can but u dont need to cause there are no updation such as changing the range of a painter. So we will solve it using only cumulative sum array or prefix array.
•  » » » Yeah a prefix array would be enough here. I just wanted to know if it was possible to write a segment tree solution. Thanks for the reply!
•  » » » » Indeed it is possible . U can determine range sum in O(logn) complexity using segment tree . However using prefix array complexity would be O(1).
•  » » check my solution, i used segment trees to count number of '1' and '2'https://codeforces.com/contest/1132/submission/50845077
•  » » » Thanks! I'll look at the solution.
 » 4 years ago, # | ← Rev. 3 →   My solution For G:dsu on treehttps://codeforces.com/contest/1132/submission/50995547
•  » » Hey, I saw a few others with dsu solutions. Can you elaborate on your idea?
 » Why is G not Increasing subsequence problem? can someone elaborate the what does the meaning of the problem G in simple way.
•  » » For a = [1, 2, 100, 3, 4], you could not choose a index subsequence like [1, 2, 4, 5] because 4 is not the minimum number such that a > a.The only choice is [1, 2, 3].
 » 4 years ago, # | ← Rev. 2 →   G: Managed to squeeze HLD O(n * log^2(n)) with Fenwick tree and binary search 51106103 Solution shortly : go from right to left and keep multiset of possible ending of sequence, add and delete nodes as you go. While deleting node, erase it from multiset, and add it's children to multiset. While adding node, find highest parent which you can improve with HLD & binary search. After finding this node just do += 1 from added node to it.
 » In the editorial for G, what makes a vertex marked?Is it "if it has a node that points to it in the current subsegment"?
•  » » 4 years ago, # ^ | ← Rev. 2 →   we mark the first k vertex and the maximum is answer.then we unmark vertex 1 and mark vertex k+1, and the maximum is answer.and so on.
 » 4 years ago, # | ← Rev. 3 →   Can anyone help me. I find the test when a parsed program for problem G gives an incorrect result.6 6 3 29 5 5 28 6 True answer : 3( a, a, a )Answer in program: 2Or i have mistake?
 » Can someone provide a test case where this solution of E fail or provide a proof of its correctness? https://codeforces.com/contest/1132/submission/50862512
 » Can someone explain problem B ? I am not able to follow the tutorial.
 » //Solution: DIV2 — CSimple Bruteforce Solution:https://codeforces.com/contest/1132/submission/54590211
 » In problem F, the recurrence according to the editorial isf(l, r) = min f(l+1, i-1) + f(i, r) But since we are combining s[l] with s[i], can we not have a recurrence like:f(l, r) = min f(l+1, i-1) + 1 + f(i+1, r) the +1 coming from combining s[l] and s[i] and we start the 2nd recursive call from i+1 instead of i. How are the two different?
•  » » It is not written that we are exactly combining s[l] with s[i], instead it is written that s[l] and s[i](maybe along with some s[k]'s such that s[k]=s[l]) will be deleted in a single turn.Your reccurence is for s[i] and s[l] only will be deleted in a single turn, which is wrong(since it may not be optimal).
 » 3 years ago, # | ← Rev. 3 →   Alternative solution for problem DBinary search the answer. Suppose that you are checking the charger with power $x$. At the beginning, consider each laptop separately and charge it as late as possible, and keep an array $c$ with the number of laptops that should be charged each minute. There are two cases: $x \geq b[i]$: in this case, it would be optimal to charge the laptop iff its current power is $< b[i]$. This is easy to simulate in $O(\text{number of charges})$. $x < b[i]$: in this case, it would be optimal to charge the laptop only in a suffix of minutes (because the power of the laptop is always decreasing). Of course, if the total number of charges becomes $\geq k$, we can just return false.The problem with this approach is that we are not considering that we can't charge more than one laptop in a minute. However, we can consider the total number of laptops that should be charged until each minute by taking the prefix sums of the array $c$. The condition is easy: the charger with power $x$ can be used iff $c[i] \leq i + 1$ for each $i$.Submission: 90456305
 »
 » Can someone please help me figure out why O(N^3) solution for Problem-F is getting accepted ? Since N is 500 , N^3 should give TLE .