chokudai's blog

By chokudai, history, 2 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +134
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it -23 Vote: I do not like it

[deleted]

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Feels like a huge difficulty gap between E and F .

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +82 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you please give the link to your solution .

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            can u explain why we need the starts and bars part

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it +16 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

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

                  Submission

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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 )

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              I think the next term should be from dp[l+2][l+1]. The key idea i understood, is : there is a way of choosing one pack, dp[l+1][x-1], another pack dp[x+1][r], the sequence in both of them is decided. Then C(n1+n2+1,n2) are the ways of "merging" them, choose n2 positions for second pack.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

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());
        }
 
    }
 
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        1. If heap is not empty, then extract the min.
        2. Else, popleft() from deque. (It's guaranteed the operation won't be called on an empty list.)
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used Set and Queue and passed in time limit

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What was the solution of G?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it +30 Vote: I do not like it

      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:

      1. Make a new group
      2. 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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You should have used Multiset

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use multiset and queue

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve F?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    Spoiler
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Samples for F were poor.

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Source Code

Why TLE in E?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I used segment tree to solve E

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. use a deque instead of a vector
    2. don't insert in the multiset when q==1
    3. move everything from the deque to the multiset when q==3
    4. when q==2, use the deque or the multiset wisely
»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like 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.

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks bro <3, i was wandering why it goes tle all this time

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks, Can you give me source to this info if you can ?

»
2 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When $$$c=3$$$,put all elements into priority_queue,and when $$$c=2$$$,first to output the head of the priority_queue.If the priority_queue is empty when $$$c=2$$$,then output the head of queue. Understand?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What a STL race!(lol)

»
2 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

The questions D) and E) on this contest are mainly about using functions from data structures.

For D, I used a map to sort the marked cuts and retrieve the two marked cuts surrounding each query. My solution

For E, I used a map to record the front-and-sorted section of the sequence, and a queue to note the parts after the sorted section. Here's my solution

These problems can help new programmers to understand and learn more about functions and uses of Maps and other similar Data Structures.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Video tutorial for problem A, B, C, D, E : https://youtu.be/seoYYZiZL-0

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem F

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

  • »
    »
    6 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    CharlesWuQiushi Your Solution would give wrong answer for testCase mentioned below

    3 3

    1 4

    2 3

    5 6

    Output: 3

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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:

      1. $$$2,3; 1,4; 5,6;$$$
      2. $$$2,3; 5,6; 1,4;$$$
      3. $$$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!

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            Link