AtCoder Beginner Contest 217 Announcement

3 years ago, # |

+12

Feels like a huge difficulty gap between E and F .

→ Reply

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

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.

→ Reply

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

+26

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

→ Reply

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

USACO range dp

→ Reply

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

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

→ Reply

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

→ Reply

3 years ago, # ^ |

Can you please give the link to your solution .

→ Reply

3 years ago, # ^ |

+14

Sure. Link to my solution

→ Reply

3 years ago, # ^ |

Thanks

→ Reply

3 years ago, # ^ |

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.

→ Reply

dkkv0000

3 years ago, # ^ |

can u explain why we need the starts and bars part

→ Reply

3 years 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.

→ Reply

MojoAlpha

3 years ago, # ^ |

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

→ Reply

jigsaw7

3 years ago, # ^ |

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?

→ Reply

3 years ago, # ^ |

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

→ Reply

zbctd

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

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

Submission

→ Reply

aimoon

3 years ago, # ^ |

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.

→ Reply

3 years ago, # ^ |

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.

→ Reply

aimoon

3 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

3 years ago, # ^ |

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

→ Reply

darkcoder123

3 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

dkkv0000

3 years ago, # ^ |

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 )

→ Reply

crimsonred

3 years ago, # ^ |

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

→ Reply

tmaddy

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

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

→ Reply

aopo

3 years ago, # ^ |

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

→ Reply

sharmaharisam

3 years ago, # ^ |

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

→ Reply

tmaddy

3 years ago, # |

← Rev. 2 →

-9

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

EDIT Well, here it is

 deque<ll> d;
 
    for(ll i=0; i<n; ++i) {     
        ll op;
        cin >> 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());
        }
 
    }

→ Reply

3 years ago, # ^ |

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.

→ Reply

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

3 years ago, # ^ |

← Rev. 2 →

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

→ Reply

theviz

3 years ago, # ^ |

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

→ Reply

hotel_california

3 years ago, # ^ |

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

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

→ Reply

majorro

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

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)

→ Reply

3 years ago, # ^ |

I used Set and Queue and passed in time limit

→ Reply

Rudro25

3 years ago, # ^ |

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

→ Reply

3 years ago, # ^ |

emmm,but I truly used set submissions

→ Reply

Rudro25

3 years ago, # ^ |

Then u used also map to count.

→ Reply

m1sterzer0

3 years ago, # ^ |

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

→ Reply

3 years ago, # |

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

→ Reply

Taha1506

3 years ago, # ^ |

What was the solution of G?

→ Reply

3 years 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

→ Reply

Taha1506

3 years ago, # ^ |

Nice! Thank you =)

→ Reply

m1sterzer0

3 years ago, # ^ |

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.

→ Reply

ssvb

3 years ago, # ^ |

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.

→ Reply

MidoriFuse

3 years ago, # |

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

→ Reply

jojonicho

3 years ago, # |

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.

→ Reply

3 years ago, # ^ |

You should have used Multiset

→ Reply

jojonicho

3 years ago, # ^ |

oh what a silly mistake. Thanks!

→ Reply

toomatho

3 years ago, # ^ |

use multiset and queue

→ Reply

3 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

3 years ago, # ^ |

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

→ Reply

majorro

3 years ago, # |

how to solve F?

→ Reply

YPK

3 years ago, # ^ |

Spoiler

→ Reply

spookywooky

3 years ago, # ^ |

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.

→ Reply

pksingh290

3 years ago, # |

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

→ Reply

feecle6418

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

→ Reply

Achtoria

3 years ago, # ^ |

← Rev. 2 →

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

→ Reply

ScarletS

3 years ago, # |

+16

Samples for F were poor.

→ Reply

3 years 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!

→ Reply