We will hold AtCoder Beginner Contest 217.

- Contest URL: https://atcoder.jp/contests/abc217
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210904T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 8
- Writer：kyopro_friends, math957963, Nyaan, physics0523, sheyasutaka
- Tester: leaf1415, sugarrr
- Rated range: ~ 1999

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

We are looking forward to your participation!

Feels like a huge difficulty gap between E and F .

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 :)

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.

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

It is a nice exercise to learn range DP and you can also learn it from the USACO guide.

Can you please provide link to the USACO Guide covering such DP idea.

USACO range dp

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 . ':)

Could you elaborate, as I did use $$$O(N^3)$$$ range DP, but probably wrong transitions.

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$$$.

Can you please give the link to your solution .

Sure. Link to my solution

Thanks

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.

can u explain why we need the starts and bars part

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.

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).

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?

Correct, you use operations of type $$$q$$$ as delimiters.

why not is C(n1+n2,n1)?

They are equivalent essentially, here's my code which uses your formula.

Submission

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.

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.

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.

Yeah, my bad, I referred to different n1 and n2 in this context.

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.

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 )

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)$$$.

why is dp[l+1][l]= 1 ? why not 0 ?how do you come up with that edge case ?

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$$$.

Is there any solution with time complexity lesser than O(n^3). Would be eager to know if there is some.

I realized that F was range dp, however still got WA. Can you elaborate on the transitions please?

For problem E) sorting queries I used a deque and got a TLE.

EDIT Well, here it is

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.

I used Deque and MultiSet Both , Still passed way within Time Limit.

I used the same but got tle. Can u share your code?

https://atcoder.jp/contests/abc217/submissions/25610896

This 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 ->

sorting part gives tl, you have to optimise it in some way

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)

I used Set and Queue and passed in time limit

set gives you WA, i am sure you also used multiset :v

emmm,but I truly used set submissions

Then u used also map to count.

I used a minheap for the prefix and a deque for the suffix.

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++.

I feel like G was easier than F in terms of implementation.

What was the solution of G?

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:

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

Nice! Thank you =)

I broke the solution into three parts:

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.

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.

Not being able to solve H is what I get for delaying to learn slope trick.........

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.

You should have used Multiset

oh what a silly mistake. Thanks!

use multiset and queue

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.

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

how to solve F?

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.

Consider a subsequence l,r

if 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,r

We need to combine all these combinations, with stars'n'bars formular.

solved first 5 in 30 min then kept staring the screen for the rest 1 hour 10 min.any idea how to solve F.

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?

I agree with you.It costs me a huge amount of time coding the similar problem : ARC070C qwq...

Samples for F were poor.

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!

How to solve F and G? Any ideas? Help me!

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.

Got it, great explanation

Source Code

Why TLE in E?

`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.

Thanks

Still wondering how in the world authors decided that both E and F are worth 500 points.

I used segment tree to solve E

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 .

Link : https://atcoder.jp/contests/abc217/submissions/25610922

Op 3 is O(N), and is called up to N times, so O(N^2)

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

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.

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.

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/tasks

Problem link : https://atcoder.jp/contests/abc217/tasks/abc217_d

TLE solution link : https://atcoder.jp/contests/abc217/submissions/25614807

AC solution link : https://atcoder.jp/contests/abc217/submissions/25614873

This is because upper_bound does

nottake 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 ofO(N). While set.upper_bound is implemented in a different way, so it works faster inO(logN).Same is true for lower_bound and set.lower_bound too. :)

ABC's give us some really cool classical DP, which are really rare in other contests nowadays.

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??

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)$$$.

Video tutorial for problem A, B, C, D, E :https://youtu.be/seoYYZiZL-0Problem 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.

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.

CharlesWuQiushi Your Solution would give wrong answer for testCase mentioned below

3 3

1 4

2 3

5 6

Output: 3

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: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!

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

No, unfortunately. I felt quite confused as well. I wonder where we can download test data.

Atcoder provides link to test cases of all contests but the test cases for this Contest have not been uploaded there.

Link