### chokudai's blog

By chokudai, history, 17 months ago,

We will hold AtCoder Beginner Contest 217.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

• +134

| Write comment?
 » 17 months ago, # |   +12 Feels like a huge difficulty gap between E and F .
•  » » 17 months ago, # ^ |   0 It sure does, at first it seemed solvable but as the time progressed (and 3 WAs) I started to give up. Hope it goes better for the others :)
•  » » » 17 months ago, # ^ |   0 I felt the same , thought it was solvable , then coded then ran on Sample TC , 2nd one gave WA , realised it is much more tougher than I thought , Didn't made any submission as I knew the solution (even thinking) is completely wrong.
•  » » » » 17 months ago, # ^ |   +6 Mine passed 13 tests so I thought it had some right parts to it, but then I realized why it could fail and that my approach probably couldn't be adapted :P
•  » » 17 months ago, # ^ |   +26 It is a nice exercise to learn range DP and you can also learn it from the USACO guide.
•  » » » 17 months ago, # ^ |   0 Can you please provide link to the USACO Guide covering such DP idea.
•  » » » » 17 months ago, # ^ |   +5
•  » » » » » 17 months ago, # ^ |   0 Well , Thanks , BTW I knew about it (I asked Because I was assuming to get something very related to problem ), used same Range DP . But Was unable to manage the Permutation part , like {{1,2},{3,4}} and {{3,4},{1,2}} are different . Any help on how to do this would be really appreciated . ':)
•  » » » 17 months ago, # ^ |   0 Could you elaborate, as I did use $O(N^3)$ range DP, but probably wrong transitions.
•  » » » » 17 months ago, # ^ |   +82 Let $dp_{l,r}$ denote the number of ways to pair up all the students between l and r. Now to find the transition between dp states, we consider which student between l and r would be paired up with l. Let this student be x. It should be evident that the number of students between l and x has to be even. Also, l and x has to be on good terms. If the above conditions are satisfied, then we recursively find $dp_{l+1, x-1}, dp_{x+1,r}$. It should be clear that removing pairs between l+1, x-1, and x+1, r is independent and also the pair removal between l+1 and x-1 has to come before removing the pair l and x. Now, we have to figure out the number of possible orderings of the pairs. Let n1 be the number of pairs between l+1, x-1, and n2 be the number of pairs between x+1, r. $n1 = (x-l-1)/2, n2 = (r-x)/2$. The number of ways to order all the pairs is ${{n1+n2+1}\choose{n2}}$ (to prove this use stars and bars). Therefore, $dp_{l,r} = \sum_{x=l+1}^r dp_{l+1, x-1}*dp_{x+1, r}*{{n1+n2+1}\choose{n2}}$ where x satisfies the mentioned conditions, and $dp_{l+1,l} = 1$.
•  » » » » » 17 months ago, # ^ |   0 Can you please give the link to your solution .
•  » » » » » » 17 months ago, # ^ |   +14 Sure. Link to my solution
•  » » » » » » » 17 months ago, # ^ |   0 Thanks
•  » » » » » 17 months ago, # ^ |   +6 Thanks, I missed the stars and bars part and that's why my solution didn't work. I overlooked the fact that if there is a way to remove a segment it takes its length divided by two moves. :(Thanks again.
•  » » » » » » 17 months ago, # ^ |   0 can u explain why we need the starts and bars part
•  » » » » » » » 17 months ago, # ^ |   +16 Let's suppose we are calculating $DP[i][j]$. We need to calculate the number of ways if we decide to pair $i$ with $k$.Notice these three properties:For every segment $l, r$ the total number of operations done is equal to $(r - l + 1) / 2$, because we remove 2 elements per every operation. To remove $i$ and $k$ we obviously have to remove every element that's between them $({i + 1}, {i + 2}, ..., {k - 1})$ because otherwise they are not adjacent.Elements greater than $k$ are not dependent on the ones $\leq k$, because we can't pair them with any elements in range $[i, k]$.Combining these facts we can notice that we can independently solve for range $[i, k]$ and range $[k + 1, j]$. Let the first range take $p$ operations and second one take $q$ operations to completely erase. Since these ranges are independent, it implies that we need to find the number of ways to reorder the given $p + q$ operations, such that all the operations of type $p$ can't be distinguished between themselves and the same holds for the $q$ operations. This results in the provided stars and bars formula.Since we need to do this for every possible sequence of operations, we multiply it by $DP[i + 1][k - 1]$ and $DP[k + 1][j]$.I hope this was clear, if not hit me up and I'll provide an example.
•  » » » » » » » » 17 months ago, # ^ |   +3 Thanks for the explaination. Actually, i also implemented the range DP solution, but i missed this part in those calculations which resulted in 15 WAs (o_o).
•  » » » » » » » » 17 months ago, # ^ |   +3 So for example, if $p=3$ and $q=2$, then the following pattern $"**|*|"$ means performing this sequence of operations: 2 operations of type p, 1 operation of type q, 1 operation of type p, 1 operation of type q, right?
•  » » » » » » » » » 17 months ago, # ^ |   0 Correct, you use operations of type $q$ as delimiters.
•  » » » » » » » » » 17 months ago, # ^ |   +1 why not is C(n1+n2,n1)?
•  » » » » » » » » » 17 months ago, # ^ |   +1 They are equivalent essentially, here's my code which uses your formula.Submission
•  » » » » » » » » » 17 months ago, # ^ |   0 No they are not. We do C(n1 + n2 + 1, n2) because we have n2 pairs out of range from l to x, so we can remove them at any time, that means we don't need to remove them before we remove [l,x] pair.
•  » » » » » » » » » 17 months ago, # ^ |   +3 In my explanation they are, just take a look at my submission. I may be wrong, but I don't think so, it's how I implemented it.
•  » » » » » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 Yeah I know that you did like that, but I'm just saying that C(n1 + n2, n1) and C(n1 + n2 + 1, n2) are not same. You just said that they are equivalent which is not true.
•  » » » » » » » » » 17 months ago, # ^ |   +3 Yeah, my bad, I referred to different n1 and n2 in this context.
•  » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 Thanks for this, that's really cool. I was doing the same thing, I was considering the same idea, the only difference was I was considering all pairs of elements in range l to r. Leading to O(n^4) dp. Didn't realize the position of (l,x) only matters.
•  » » » » » 17 months ago, # ^ |   +3 by doing this dp(l+1,x−1)∗dp(x+1,r) we will get the all combinations, can u elaborate why we need the combinations(n1+n2+1 n2 )
•  » » » » » » 17 months ago, # ^ |   +1 You can imagine a sequence of $n_1 + n_2 + 1$ "gaps". You need to fill $n_2$ of these gaps using the second sequence. The number of ways to do this is ${n_1 + n_2 + 1} \choose {n_2}$. The remaining gaps will be filled by the first sequence followed by the pair $(l, x)$.
•  » » » » » 17 months ago, # ^ |   0 why is dp[l+1][l]= 1 ? why not 0 ?how do you come up with that edge case ?
•  » » » » » » 17 months ago, # ^ |   0 Consider $dp_{l,l+1}$ where l and l+1 are on good terms. It should be obvious that $dp_{l, l+1} = 1$,and by our dp transition shown above, $dp_{l, l+1} = dp_{l+1, l}*dp_{l+1, l}*{1\choose 0}$ (substituting x = l+1, r = l+1). From this equation, it is clear that $dp_{l+1, l} = 1$.
•  » » » » » 17 months ago, # ^ |   0 Is there any solution with time complexity lesser than O(n^3). Would be eager to know if there is some.
•  » » » 17 months ago, # ^ |   0 I realized that F was range dp, however still got WA. Can you elaborate on the transitions please?
 » 17 months ago, # | ← Rev. 2 →   -9 For problem E) sorting queries I used a deque and got a TLE.EDIT Well, here it is deque d; for(ll i=0; i> op; if(op == 1) { ll x; cin >> x; d.push_back(x); } else if(op == 2) { cout << d.front() << "\n"; d.pop_front(); } else { sort(d.begin(), d.end()); } }
•  » » 17 months ago, # ^ |   +3 I don't think using a queue or a deque matters, but rather the other parts of your code were probably the reason why you got a TLE.
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 I used Deque and MultiSet Both , Still passed way within Time Limit.
•  » » » 17 months ago, # ^ |   0 I used the same but got tle. Can u share your code?
•  » » » » 17 months ago, # ^ |   +3 https://atcoder.jp/contests/abc217/submissions/25610896This is what I came up after the contest ended. I used deque and min heap. The idea is that whenever we have to do sorting, we move all the elements from deque to min heap. In this way, we don't have to do O(n*log(n)) for sorting rather just add elements to the heap in O(log(n)) time. When asked to add element, we add the elements in deque and while printing the front element, there will be 2 cases -> If heap is not empty, then extract the min. Else, popleft() from deque. (It's guaranteed the operation won't be called on an empty list.)
•  » » 17 months ago, # ^ |   0 sorting part gives tl, you have to optimise it in some way
•  » » 17 months ago, # ^ |   +6 First of all , provide link to your code and don't paste it directly , and secondly sorting is the reason for TLE . Just think , first 10^5 operation of append and then 10^5 operation of sorting , Operation will be (10^10)*log(10^5)
•  » » 17 months ago, # ^ |   0 I used Set and Queue and passed in time limit
•  » » » 17 months ago, # ^ |   0 set gives you WA, i am sure you also used multiset :v
•  » » » » 17 months ago, # ^ |   0 emmm,but I truly used set submissions
•  » » » » » 17 months ago, # ^ |   0 Then u used also map to count.
•  » » 17 months ago, # ^ |   +7 I used a minheap for the prefix and a deque for the suffix. operation 1 -- add to suffix operation 2 -- pop from minheap if not empty, else popleft from suffix deque operation 3 -- pop everything from suffix and push to minheap The time limit I think was generous to let us Pythonites in. I think that resorting after every operation 3 was intended to get TLE, but the relaxed python limits might have let that slide for C++.
 » 17 months ago, # |   +6 I feel like G was easier than F in terms of implementation.
•  » » 17 months ago, # ^ |   0 What was the solution of G?
•  » » » 17 months ago, # ^ | ← Rev. 3 →   +30 Let $dp_{i,j}$ be the number of ways to split up 1~i having j groups. Then there are two cases for our transitions: Make a new group Add it to an existing group For the first case, it is simply $dp_{i,j} += dp_{i-1,j-1}$. For the second case, we just have to figure out how many groups already contain a person that has the same id in modulo m as i. Obviously, each group can have up to one person that has the same id in modulo m due to the restriction, so the number of "bad" groups is actually just $\frac{i-1}{m}$, the number of people that have the same id in modulo m as i. So the transition here would be just $dp_{i,j} += dp_{i-1, j}*max(0, j- \frac{i-1}{m})$. This results in a nice $O(n^2)$ solution
•  » » » » 17 months ago, # ^ |   0 Nice! Thank you =)
•  » » » 17 months ago, # ^ |   0 I broke the solution into three parts: Figuring out the ways to split the numbers into at most $k$ labeled groups for $k$ in $1,2,...,N$. Figuring out how to split the numbers into exactly $k$ labeled groups by using the above array and inclusion/exclusion (with binomial coefficients) Converting from labeled groups to unlabeled groups (i.e. just multiplying by the inverse of $k!$). I also did this one before prob F after not immediately seeing the DP for F. Fortunately I had time to come back to F and got it working with about 5 minutes to spare.
•  » » 17 months ago, # ^ |   0 Yes, I also think that G seemed easier. Switched to it after I noticed that rainboy took less time to solve G than F. Still couldn't make it in time and only got a correct answer for the 2nd sample so far. Trying to upsolve it now.
 » 17 months ago, # |   +3 Not being able to solve H is what I get for delaying to learn slope trick.........
 » 17 months ago, # |   0 Any idea how to solve E? I used set for the sorted items and queue for the unsorted. Implementation was full of bugs I suppose as I got 8 WA.
•  » » 17 months ago, # ^ |   +3 You should have used Multiset
•  » » » 17 months ago, # ^ |   +3 oh what a silly mistake. Thanks!
•  » » 17 months ago, # ^ |   0 use multiset and queue
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 Maintain a queue of elements that are inserted and two sets (one for the sorted part and the other for the non-sorted part). When sorting query is applied, just use small to large merging and the rest two cases are pure implementation and case work in 3-4 lines.EDIT: Small to large merging is not needed lmao. IDK why I opted to use it, but as others described you can just do single multiset and queue.
•  » » 17 months ago, # ^ |   +3 I think I did what you are describing. Basically, use a set to maintain the prefix of the sequence that is sorted, and a queue for the rest. For type 1 queries, you either add an element into the set if the queue is empty and the element is greater or equal to the highest value of the set, or you add it to the queue. For type 2 queries, you either remove the smallest element from the set or if the set is empty, just remove the front element of the queue. Lastly, for type 3 queries, you simply insert all the elements in the queue into the set. Make sure to use a multiset
 » 17 months ago, # |   +1 how to solve F?
•  » » 17 months ago, # ^ |   +8 SpoilerLet answer for range (x,y) be dp[x][y] Let's iterate through b such that there is an edge between x and b and x<=b<=y. Then, dp[x][y] += dp[x+1][b-1]*dp[b+1][y]*BC(y-x+1,b-x+1) where BC is Binomial cofficient (nCm)This means we are choosing the edge (x,b). And for every two different bs we choose, the ways won't coincide.Why Binomial coefficient? — Let's consider some possible way to choose the answer for each of two consecutive ranges (x, a),(a+1,y). We basically need to insert one sequence in the same order into the other sequence.
•  » » 17 months ago, # ^ |   0 Consider a subsequence l,rif l and r are a good pair we can solve pair l,r, then the seq l+1,r-1.And, we can solve l,l0 (in (l0-l)/2 steps), then l0+1,rWe need to combine all these combinations, with stars'n'bars formular.
 » 17 months ago, # |   +3 solved first 5 in 30 min then kept staring the screen for the rest 1 hour 10 min.any idea how to solve F.
 » 17 months ago, # |   +13 I'm shocked to see so many people solving H and in such a short time. Is maintaining a convex function really popularized nowadays or does it have easier solutions?
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 I agree with you.It costs me a huge amount of time coding the similar problem : ARC070C qwq...
 » 17 months ago, # |   +16 Samples for F were poor.
 » 17 months ago, # |   +16 Can anyone tell me when will the editorial be posted? There's no editorial last ABC, either. This ABC is a really exciting one! I got 5 questions right!
 » 17 months ago, # |   0 How to solve F and G? Any ideas? Help me!
•  » » 17 months ago, # ^ |   +13 F: dp[L][R]: answer to the problem when you start with students numbered L, L+1, ..., R-1. (R-L must be even). dp[1][2N+1] is the answer.For transition, iterate over all possible way of pairing student L. Let that student be M. We can't have any student between L and M paired with a student outside of the range [l, M]. Therefore, we can independently count those two separate range, and merge.G: For fixed, k, we can solve it in O(k) with PIE. If we require z (0<=z<=k) groups to be empty, there are k choose z ways to choose such groups. Looking at a specific remainder R modulo M, there are either floor(N/M) or floor(N/M)+1 numbers with remainder R mod M. Each of those numbers contribute to the answer the exact same way. Do little bit of combinatorics to count the exact contribution.
•  » » » 17 months ago, # ^ | ← Rev. 3 →   0 Got it, great explanation
 » 17 months ago, # |   +1 Source CodeWhy TLE in E?
•  » » 17 months ago, # ^ |   +6 curr = all; takes O(n^2) time.Consider not using the set all. It is enough to have the curr set and the vector. On operation 3 push all elements from the vector into the set.
•  » » » 17 months ago, # ^ |   +3 Thanks
 » 17 months ago, # |   +15 Still wondering how in the world authors decided that both E and F are worth 500 points.
 » 17 months ago, # | ← Rev. 2 →   +1 I used segment tree to solve E
 » 17 months ago, # | ← Rev. 2 →   0 Why is my solution giving TLE for Problem E? Query 1 and 2 takes O(logN) while query 3 Takes O(N) to copy the elements .
•  » » 17 months ago, # ^ |   +6 Op 3 is O(N), and is called up to N times, so O(N^2)
•  » » » 17 months ago, # ^ |   0 I see. But why solutions where each element from the queue is being inserted into a multiset are under the time element? Because in this case the time complexity of query 3 should be O(NlogN) as there are 'N' elements in the queue and logN for insertion operation of multiset ; like this solution : https://atcoder.jp/contests/abc217/submissions/25598249
•  » » » » 17 months ago, # ^ |   +3 The total number of individual multiset insert operations handled by the type 3 queries can't exceed N during the whole lifetime of the program. So the time complexity of all the type 3 queries lumped together can't exceed O(NlogN) in the worst case. I have explained this to another person, who asked the same question earlier. You can read the "Amortized analysis" chapter of the Competitive Programmer's Handbook to learn more about it.
 » 17 months ago, # |   +8 Nice contest! I love problem D and E, they are tricky. And I found a lot of different solutions of E, they are of great educational value, and I have gained a lot.
 » 17 months ago, # |   +2 set.upper_bound(element) is much faster than upper_bound(set.begin() , set.end() , element)Today while giving AtCoder Beginner Contest 217, I noticed that set.upper_bound(element) is faster than upper_bound(set.begin() , set.end() , element). During the contest I used upper_bound(set.begin() , set.end() , element) and got TLE. But after the contest I resubmitted my code with set.upper_bound(element) and got AC.contest link : https://atcoder.jp/contests/abc217/tasksProblem link : https://atcoder.jp/contests/abc217/tasks/abc217_dTLE solution link : https://atcoder.jp/contests/abc217/submissions/25614807AC solution link : https://atcoder.jp/contests/abc217/submissions/25614873
•  » » 17 months ago, # ^ |   +1 This is because upper_bound does not take advantage of structure of sets, as far as I know, upper_bound is implemented in a way such that it acts like binary search in an array but in sets elements are arranged differently so binary search doesn't works here and the function need to go for every element in order to return the desired result, giving worst case complexity of O(N). While set.upper_bound is implemented in a different way, so it works faster in O(logN). Same is true for lower_bound and set.lower_bound too. :)
 » 17 months ago, # |   +20 ABC's give us some really cool classical DP, which are really rare in other contests nowadays.
 » 17 months ago, # |   0 Can someone tell in E how solutions using a priority queue(min heap) isn't getting TLE? When sorting is needed, I see the solutions moving all elements from a queue\list into the heap. Isn't the complexity now q*( q log(q) ) with q=2e5 and q*log q for inserting all elements in heap?? How does that passes??
•  » » 17 months ago, # ^ |   +3 There can't be more than Q elements total to be inserted into the heap during the whole lifetime of the program. The amortized time complexity is $O(Q\ log\ Q)$.
 » 17 months ago, # |   0 Video tutorial for problem A, B, C, D, E : https://youtu.be/seoYYZiZL-0
 » 17 months ago, # | ← Rev. 3 →   0 Problem FI didn't update DP data in the way explained in official editorial. My solution did it like this:$dp[i][j]$ is the number of ways to tackle all students in segment $[i, j]$. Let $l = i - j + 1$. It is obvious that $l$ must be even. Case 1, the $i^{th}$ student is paired with the $j^{th}$ student. It is possible only when the segment $[i + 1, j-1]$ has been tackled, and the two are on good terms. Case 2, the whole segment is devided into two seperate segments, that their operations can be implemented respectfully. Let the length of the first sub-segment be $2k$. We pair all students in $[i, i + 2k - 1]$ and $[i + 2k, j]$. Therefore $dp[i][j] = dp[i + 1][j - 1] * friends[i][j] + \sum\limits_{k=1}^{l / 2 - 1}{dp[i][i + k * 2 - 1] * dp[i + k * 2][j] * C_{l / 2}^{k}}$.I wonder if there are any mistakes in my solution. Have I overlooked anything? Here is my submission.
•  » » 17 months ago, # ^ | ← Rev. 4 →   0 CharlesWuQiushi Your Solution would give wrong answer for testCase mentioned below3 31 42 35 6Output: 3
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 Could you please explain why the answer is $2$? Statement says "Two ways to do the operation $N$ times are considered different when there exists $1\leq i\leq N$ such that the pair of students chosen in the $i$-th operation is different in those two ways."Then these three ways are different: $2,3; 1,4; 5,6;$ $2,3; 5,6; 1,4;$ $5,6; 2,3; 1,4;$ You see, the pair $2,3$ is always removed before $1,4$, and the pair $5,6$ can be placed anywhere in the order.I'm not a native speaker, so I may have misunderstood it. Could you please explain it more clearly? Thx a lot!
•  » » » » 17 months ago, # ^ |   0 CharlesWuQiushi Yes, u r right, its answer would be 3. So, have you find any mistake in this approach as I was also using same approach but didn't get correct results
•  » » » » » 17 months ago, # ^ |   0 No, unfortunately. I felt quite confused as well. I wonder where we can download test data.
•  » » » » » » 17 months ago, # ^ |   0 Atcoder provides link to test cases of all contests but the test cases for this Contest have not been uploaded there.Link