By awoo, history, 3 years ago, translation, In English

Hello Codeforces!

On May/16/2021 11:00 (Moscow time) Educational Codeforces Round 109 (Rated for Div. 2) will start. Please, note the unusual start time.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Dear Codeforces!

We are reaching out to make sure you have everything you need to begin your journey at Harbour.Space University. That’s why we are hosting our very first Virtual Open.Day on May 20th at 4:30 p.m. (CET).

This Open.Day is an opportunity for our university to open its doors (virtually) for you to get an idea of what to expect in terms of the academic experience, student life, living in Barcelona and asking any questions you might have.

Remember, we have a full scholarship available for competitive programming! This scholarship is for Bachelor’s and Master’s students wanting to join any of our tech-related programmes and our dynamic programming team. Joining the Open.Day is the perfect opportunity for you to ask questions and make sure Harbour.Space is the right place for you.

Register for our Virtual Open.Day and see first-hand what life is like as a Spacer and the success stories of our scholarship recipients.

Here is a sneak peek: https://www.youtube.com/watch?v=y6f999g7qFA

Register Today→

Good luck on your round, and see you next time!

Harbour.Space University

UPD: Editorial is out

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

| Write comment?
»
3 years ago, # |
  Vote: I like it -88 Vote: I do not like it

i hope i can get top 10 in this contest

»
3 years ago, # |
Rev. 6   Vote: I like it +71 Vote: I do not like it
Finally a contest
»
3 years ago, # |
  Vote: I like it -30 Vote: I do not like it

When is the next contest?

»
3 years ago, # |
Rev. 3   Vote: I like it +65 Vote: I do not like it
Necessary Meme

UPD1:After seeing c8kbf's comment down below it has been decided that only trusted participants of the third division can reply to this comment.

Regardless of whether you are a trusted participant of the third division or not,you can still upvote this comment.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I will choose the red pill. As my logic is right so I just need to optimize my code a little and boom Accepted.

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

      If you TLE on test 2, how are you sure your logic is right? TLE != slow AC... so getting TLE on test 2 is just as bad as WA on test 2.

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

    WA on test 2 with CF Diagnostics because that could (possibly) be a silly mistake like array out of bounds.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this is for you keertan

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

"Please, note the unusual start time." bruhh

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

A contest after so many days feels like an eternity

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

and our dynamic programming team

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I hope to become Expert this time.

»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

why my code is giving runtime error in CSES dp-7th problem (book shop)??.Please help me. link to code- https://cses.fi/paste/31a10089630000cd20d9fe/

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Notice the unusual start time!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Super unusual start time!

»
3 years ago, # |
  Vote: I like it +157 Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally we have a contest!!

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

long time no see "codeforces contests"..where were you?

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I hope I manage to wake up

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Even if there are meteor showers tomorrow, please keep this round rated

»
3 years ago, # |
  Vote: I like it +136 Vote: I do not like it

Life is hard on the west coast...

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

    Will you participate, btw?

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

      Maybe, I woke up at 6:30 AM today for Code Jam and haven't slept since :P and I have exams next week, but contests are fun too :D

      Upd: Ended up taking!

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

    Good time for people with fucked up sleeping schedules like me! :D

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

finally a contest but the start time is really unusual

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with this

"The penalty for each incorrect submission until the submission with a full solution is 10 minutes"

Does this mean if we submit the correct answer for a question then all the penalties from incorrect submissions on that question will get canceled?

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

    No. It means that if you wrong answer N times and get accepted eventually, you get 10*N minutes penalty. But if you didn't get accepted, then you won't receive any penalty for the failed submissions.

»
3 years ago, # |
  Vote: I like it +144 Vote: I do not like it

Upvote this comment if you also think that task $$$C$$$ was a piece of shit.

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

C is my new favorite problem ever!

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

    I struggle on C for quite a long time... I wonder if there's solution that is easy to implement.

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

    Looks like it was just me who implemented a 150+ line abomination

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

crispy difficulty distribution.

»
3 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

;)

186965872-1454227278276034-6398230913908316733-n

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve D?

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

    $$$dp$$$[person number][max number of used seat] = answer, So if there are $$$m$$$ people, and $$$n$$$ seats answer will be $$$dp[m][n]$$$

    Transition:

    1) place $$$i$$$ is used originally: $$$dp[i][j] = dp[i][j - 1]$$$

    2) place $$$i$$$ is not used originally: let's try to use it and update result from previous person best result (where $$$i$$$ seat wasn't used): $$$dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1] + |seat_i - j|)$$$

    (initially make all dp values = $$$INF$$$, except $$$dp[0][..]$$$)

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C?

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

    Notice that you can split the problem. The points can intersect when they arr both even or odd. So now look on odd numbers (even will be the same). Sort all values and go from left to right and keep values in a stack in a such way.If now element goes to left. If stack is empty just add an element. If you now try to add an element that goes to the left and the last one in stack goes to the right you can update the answer for both values.((now - was) / 2). If both go to the left you also can update the answer for both of them((now - was) / 2 + was). And remove the last element from stack. If now element goes to the right you can keep it in stack. In the end there can be some cases. 1. Stack has one L and some R. Or all R. You finally can iterate stack from right to left and update answer. (try to find formula yourself)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain to me the approach for problem B ? Thanks in Advance !

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

    1 2 3 -> 0, if all are in position ans is 0.

    1 3 2 -> 1

    2 1 3 -> 1, if first or last are in position ans is 1.

    3 1 2 -> 2, if first and last are not in position ans is 2.

    3 2 1 -> 3, if first is in the last position, and the last one is in the first, ans is 3.

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

    hint : You can't take array of size n. but can take array of size n-1 and make it sorted array.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    1: if array is sorted, then 0

    2: if the first element is 1, swap [2; n] hence 1

    3: if the last element is n, swap [1; n — 1] hence 1 (this is the 2nd case but reversed)

    4: if 1 and n are in the middle of the array, then you need one swap to bring 1 to the front, and one swap for [2; n] (which is the 2nd case), hence 2

    5: if the first element is n and the last element is 1, then you need two swaps to bring 1 to the front, and the case is now exactly the 3rd case (1 at the front), so another 2, hence 3

»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

C was nice.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how to solve D? I learnt that we can solve it using Hungarian algorithm (by adding dummy rows since we have less rows) but that would take O(n^3)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Man I should have looked at the last sample case for C. I was solving thinking that the coordinates were sorted. :(

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

Can D be solved using Flows? It might be an overkill but still..

The idea to find the minimum cost matching of the bipartite graph formed between 1's and 0's. Just add an edge between every 1 and 0 whose weight is the distance between them. The number of edges in the graph are $$$O(n^2)$$$. I just don't know how to solve it but I can feel that it's some standard.

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

    Yes, i wrote this.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain your solution?

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

        Add edges from sourse to $$$ones$$$ and from $$$zeroes$$$ to sink with $$$capacity = 1$$$ and $$$cost = 0$$$. Also add edges between adjacent elements with $$$capasity = inf$$$ and $$$cost = 1$$$.

        Now just search the flow.

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

          Wouldn't the number of edges between the $$$ones$$$ and $$$zeros$$$ be of the order O(n2)?

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

            There $$$n-1$$$ pairs of adjacent elements, so the number of these edges is $$$2*(n-1)$$$.

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

          Is there a way to prove that it's faster than O(n3)? (I misread the problem into a version where the chairs are arranged in a circle, and this solution, if proven to be sufficiently fast, can solve that too.)

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

            I guess no, because exist graphs on which SPFA algo works in $$$O(n*m)$$$.

            But on non-specific graphs (like in this task) it works really fast, usually faster that Djikstra (I tested).

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

              I'm aware of that, but even if we consider that SPFA runs in O(m) (which was what I'm assuming actually, since in MCMF SPFA often reaches that complexity), shouldn't the complexity be O(n * m^2), and since m = O(n) it should be O(n^3)? I know that the constraints on the edges are quite... interesting, but I'm not sure if we can actually prove that those constraints would lead to a reduction in terms of flow pushes?

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

                If SPFA runs in $$$O(m)$$$, the total complexity is $$$O(n*m)$$$, because $$$|flow|$$$ is number of $$$ones$$$, which is $$$O(n)$$$.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I see. That was stupid of me :)

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

      TLE 36 with MCMF with Levit`s shortest path algo. What is wrong?

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

      Is my problem in Levit`s algo? Swap it to dejikstra or what?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved D with min-cost-max-flow, 0.7/2.0 seconds. Is it possible to hack?

»
3 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Can anybody explain how to solve D

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

Could only solve A and B :/ Tried greedy in D but failed on the 7th pretest. Where did I go wrong? I tried to match every one on the nearest left or right zero. 116376030

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this O(N^2) code giving TLE on TC5? :( https://codeforces.me/contest/1525/submission/116381276

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my dp solution fails in D?

»
3 years ago, # |
Rev. 2   Vote: I like it +50 Vote: I do not like it

It seems that I may have overcomplicated C a bit. A quick question to all those who think it's just annoying implementation — do you think it would be better if the robots were sorted in the beginning, or do you dislike the problem for some other reason? Because I agree that dealing with unsorted coordinates can be a bit annoying, and I'm sorry I've noticed that it would be better to sort them beforehand during the contest; but if it's not the reason why you dislike the problem, I'd like to hear why.

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

    lots of room for bugs imo, but implementation (concept wise translating into code) should not be too terribly bad. It's probably because it's a 4am contest (at least for me) + deques rarely pop up (at least in my experience so I kept fucking up ordering of removal) is why it was kinda frustrating, but that's just coding experience not rly an issue w/ the problem. also yeah sorted at beginning would be kinda nice but not rly that important.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I loved it However I was not able to solve it :)

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

    I dislike this problem because:

    0). Stupid annoying implementation problem

    1). Bad input format: $$$x1, L, x2, R, x3, R$$$ better than $$$x1, x2, x3, L, R, R$$$.

    2). Unsorted coordinates.

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

      If you have experience in coding cleanly, then absolutely none of the things you listed should be more than trivial issues.

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

        I just hate this problem, so I tried to find some reasonable reasons to hate it :)

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

    I don't think having the coordinates sorted would make much of a difference, since I think most stack-based solutions still have to keep track of the indices anyway.

    I personally thought that the implementation was nontrivial but not especially annoying. I was honestly quite surprised to see that more people solved D than C.

    For what it's worth, I really liked the problem!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Likely people did not handle the case of going off walls well, resulting in painful casework. This could be easily avoided however with nice implementation where you do the classic stack idea and just move starting position of leftward moving values when they don't collide with something right away.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Unsorted positions didn't annoy me much. I just found it difficult to deal with the boundaries.

    My idea was building 4 sets, two for odd/even positions of robots moving right, the other two for those moving left. Those moving left will have a reflected one out of the boundary moving to the right, so for those initially moving left, e.g., robot at 1 moving L will introduce a {1} in the left-odd set, and {-1} in the right-odd set.

    And then check the closest pairs between two sets of opposite direction but same odd/even property. However, I cannot deal with those around the boundary, e.g., the closest for robot at 1 moving left will be -1 moving right, which is itself...

    It could be a wrong idea tho. Let's see what the editorial says :)

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

    I gave up working on it after having analyzed some cases...

    Odd positions, even positions, direction of movement, does the parity of M has to be considered? From my point of view it is that casework which makes it uncomfortable to work on this problem. Independent of the initial sorting.

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

    Probably the most annoying thing about the problem is the casework formulas for calculating collision times. To be honest though, it wasn't enough to ruin it, I just wish there was a way to introduce the same problem ideas in a way that made implementation a little more appropriate for 2C.

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

      To get rid of some cases in these formulas, I suggest to try treating the left wall as a mirror. Mirroring the robot that goes to the left wall helps a lot here.

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

    dude, the problem was fine & case handling was nice in my opinion and i liked the problem!

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

    I think it’s a nice problem, with room for some of the smaller improvements that others have suggested, but I think perhaps it was too big a jump from B to C. It seems that 90% of participants were unable to tackle it, which is quite high for problem C.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

What the hell is the "Test Case 8" for D?

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

    Something that fails for greedy and works for dp?

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

      My greedy attempt managed to pass up to testcase 31 :D

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was the first test case which don't work for greedy approaches.

»
3 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Was D some assignment problem or hungarian algorithm BledDest ? Same idea of question was also asked in infosys coding test a while back.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope, just straight dp. The idea is to hold dp[i] is best solution using prefix up to i, and you transition by considering taking a range and moving all values forward or all values backwards plus the dp value before the range. You have to make sure it is possible to move all values forward or all values backward with something similar to parentheses prefix sums making sure it is always greater than 0. Hopefully my code makes it clear what I mean.

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

      Never thought like that, what I did was make 2 vectors of containing positions of 1's and 0's then made a cost matrix from that using cost[i][j] = abs(p1[i]-p0[j]) then we have to solve it like an assignment from N workers(number of 1's) to M jobs(number of 0's) each having a cost. It is a standard assignment problem. After solving A,B in like 15 minutes I spent the rest of time reading on Hungarian algorithm and transportation problem lol.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it using DP

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

    It was dp.

    Let's say that the starting position of people are $$$x_1, x_2, \dots, x_k$$$ (in sorted order) and ending positions of people are $$$y_1, y_2, \dots, y_k$$$ (also in sorted order). It's always optimal to match these starting and ending positions in sorted order: the leftmost starting position is matched with the leftmost ending, the second starting position is matched with the second ending, and so on.

    Using this fact, we can implement the following dynamic programming: $$$dp_{i, j}$$$ is the minimum time if we considered $$$i$$$ first positions and picked $$$j$$$ of them as the ending ones. Transitions are the following: we either take the current position as the ending one (if it's not a starting one), match it with the $$$j$$$-th starting position and go to $$$dp_{i+1, j+1}$$$, or we skip the current position and go to $$$dp_{i+1,j}$$$.

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

      For Problem D: Let's consider 1-indexing.

      Let's say the empty_index = [1,2,4,5] and filled_index = [0,3,6], then why don't we choose for index 2 in the full_index array(whose value is 3), a choice of index 1(whose value is 1) in the empty_index array in our dp calculation?

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

      Problem D:

      Wrong ans on test 37

      Can you pls tell me where i was wrong ?

      Submission Link : 198729784

      Thanks in Advance .

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

    I solved it using DP but can it be solved using flows? Isn't Hungarian O(V3) ?

    2147483648 has solved using flows, but I couldn't understand his/her solution 116362662

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest! Really educational. I always thought this is for div3 (< div2 since it is educational) but apparently the difficulty is around div2.

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Hack my D! otherwise I may become Expert.

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

    If you are sure, your solution will be correct, then you are already an expert. Since you are an expert, you should be listened to and your solution will be hacked. Do you really want this? But then you will not reach Expert and people will ignore you and the loop begins... which keeps running forever. EDIT: Added the TLE criterion and fixed small error.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      $$$Numbers\,Never\,Lies.$$$ If my potential is of expert level then I will definitely become someday. There is no hurry(I have huge patience).

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

The problems diffucilty was like that :

»
3 years ago, # |
Rev. 2   Vote: I like it +41 Vote: I do not like it

I really liked the contest problems! I thought they were fun (even though I didn't manage to solve F). The implementation for C isn't even that bad if you have nice ideas. Seriously, too many people bash out the first ugly casework idea that comes to mind, then blame the problem setters for "annoying" implementation problems. Typical...

On another note, I especially liked how in E,

E spoiler
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I was the victim of that bait :)

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

    I was a victim of that bait while introducing and preparing the problem.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would you like to write down a formular how calculations in E work? For me it is hard to understand. I thought about to calc the propability foreach point to be occupied after ith turn, and from that find expected number of points... but that did not work out somehow.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      3 years ago, # ^ |
      Rev. 4   Vote: I like it +22 Vote: I do not like it

      Because of linearity of expectation, we can independently consider the probability that each point will be occupied, then sum all those probabilities up.

      So, we can essentially rephrase the question as, "For some point, find the number of permutations such that this point is occupied." Let's instead solve for the complement---find the number of permutations such that the point is not occupied.

      We note that for point $$$j$$$ to not be occupied, we must have $$$p[i] \geq (n+2)-d_{i,j}$$$ for all $$$i$$$. Let $$$options[d]$$$ be the number of $$$i$$$ such that their position must be $$$\geq d$$$. Then, we can use the following loop.

      LL total = 0;
      for(int d = 1; d <= n; d++)
      {
      	total += options[d];
      	ans = (ans*total)%MOD;
      	total--;
      }
      

      Basically, count the number of guys you can put at each position, put one there, and multiply over all positions.

      Please tell me if you have more questions :))

      You can inspect my full submission at https://codeforces.me/contest/1525/submission/116376637 if you need more detail.

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

      The approach is to count the number of permutations of the cities in which each point gets conquered. We don't have to check all permutations for this. We first count the frequency of distances of every point from all the cities. For the given example, the frequency array will be: freq[ith point][number of cities at j distance] $$$=[[3, 0, 0, 0], [0, 0, 0, 3], [1, 0, 0, 2], [0, 0, 1, 2], [0, 1, 1, 1]], 1<=i<=m, 1<=j<=n+1$$$.

      We will count the number of permutations in which the $$$i$$$ th point doesn't get conquered for all $$$1<=i<=m$$$. (We will subtract this count from $$$n!$$$ for the valid count).

      Observe that for a point not to be conquered, it must not be conquered by each of the cities. Hence for any point $$$i$$$, with $$$freq[i][j]$$$ cities at a distance $$$j$$$. All these $$$freq[i][j]$$$ cities must have their permutation values belonging to the set {$$$1,2,...,j-1$$$} of maximum distance that can be covered by them(i.e. these correspond to building a museum in these cities in the $$$n,n-1,...n-(j-1)+1$$$ th turn). So the number of choices for the $$$j$$$ th city is $$$(j-1)P(freq[i][j])$$$ (where $$$nPr=n!/(n-r)!$$$).

      However, for the next city we're considering, we can't choose the $$$freq[i][j]$$$ values previous city which we've already considered. We keep a variable counted which stores the number of distinct distance values(i.e. the distinct turn numbers) already counted. So the formula will be $$$(j-1-counted)P(freq[i][j])$$$ for the $$$j$$$ th city. We increment counted by $$$freq[i][j]$$$ each time.

      The total number of ways the $$$i$$$ th point cannot be conquered is just the product of values of the above expression for all values of $$$j$$$.(Note that if at any iteration $$$freq[i][j]>=j-counted$$$, that point can never be not conquered). Subtract $$$n!$$$ from this to get the number of ways the $$$i$$$ th point can be conquered. Sum of this value for all the points is the required answer($$$x$$$). $$$y$$$ is just the total number of permutations($$$n!$$$).

      You can see this for reference https://codeforces.me/contest/1525/submission/116385486

»
3 years ago, # |
Rev. 5   Vote: I like it +69 Vote: I do not like it

Solutions to A-E

1525A - Potion-making

Spoiler

1525B - Permutation Sort

Spoiler

1525C - Robot Collisions

Spoiler

1525D - Armchairs

Spoiler

1525E - Assimilation IV

Spoiler
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For Problem D:

    Any reason why this holds true?

    The relative order of people remains the same in the optimal configuration.

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

      If $$$l_1 < r_1$$$ and $$$l_2 < r_2$$$, $$$|l_1-l_2|+|r_1-r_2| \leq |l_1-r_2|+|l_2-r_1|$$$. Hence, you shouldn't have any pair of people with a different relative order.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Great, this makes a lot of sense!

        During the contest, I was worried about how would I tackle the case if the ordering is reversed, as I would have needed to store the previous indices which are not used.

        This certainly simplifies the DP recurrence relation. Thanks :D

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

First time i able to solve D in any Educational round,

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to identify if we have to apply dp on any problem? If i could figure this out i would have solved it too!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can implement a dp if you find a dp. Just formulate dp[i][j]=... something that makes sense

      You are expected to do this in kind of every problem as part of the analysis. Of course there are more points to consider, but that is definitly one of them.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When ever the question asks for optimal solution. Dp comes into play. Yeah many questions will be solved by greedy approach also. And the constraints in the question will help you judge as in D question.. The constraints were 5000 so.. N^2 solution is accepted. From that you can judge how it's related to dp

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

C++17(64-bit) is really fast(For $$$E$$$ TC-15 takes more than 2000ms while same code runs in 841ms on C++17 on TC-15), I managed to AC $$$E$$$ in $$$O(n^{3}m)$$$

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Lol E is easier than C and D

»
3 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Could some one please provide small counter test case to my submission of problem D. Test case 44 is very big. dp[i][j] means minimum answer to accommodate all 1's till position $$$i$$$ in such a way that they remain within $$$1$$$ and $$$j$$$.

UPD : I found the mistake. This was counter test case : 10 0 1 0 0 1 1 1 1 0 0

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

116407151 why I am getting RT at testcase 11 ?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really liked the 4th/D problem. I had encountered the problem with the same idea on Leetcode. I tried solving the problem using set but end up failing on pretest 8.

During the contest, I wasn't able to give proof to myself that greedy approach would fail.

Leetcode problem link

My approach to solve problem D:

Insert all the empty seats into set. traverse from left, and do the upper_bound to find the next available seat for current occupied seat.

it = upper_bound(i)

pick the seat from it, or --it whichever gives the minimum answer.

If there is a tie between it, and --it then select --it to give priority to the first available pointer.

Can someone help here why is it failing?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider input like 000111000011111000, ie a gap in the middle. You do not know for which of the persons in the two blocks of 1s it is optimal to move them left, or move them right.

    What you are basically doing is moving them all to the left (or right, depends on implementation). Consider further that there can be severeal such "gaps" next to each other...foreach one the same problem, youc annot know if it is better to move the people left or right.

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

    consider this input :

    7

    0 0 0 1 1 1 0

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it -24 Vote: I do not like it

      sober_phoenix

      <spoiler summary=" ~~~~~ #include <bits/stdc++.h> using namespace std; using namespace std::chrono; #define int long long #define endl '\n' const int nax = 1e5 + 9; const int MOD = 1e9 + 7; struct Node { public: int val; }; //comparator for min heap bool operator<(const Node& lhs, const Node& rhs) { return lhs.val > rhs.val; } //priority_queue Q; void test_cases() { int n; cin >> n; set s; vector vec(n + 5); for (int i = 1; i <= n; ++i) { cin >> vec[i]; if(!vec[i]) s.insert(i); } int ans = 0; for (int i = 1; i <= n; ++i) { if(!vec[i]) continue; auto lower_it = upper_bound(s.begin(), s.end(), i); if(lower_it == s.end()) { --lower_it; ans += abs(i — *lower_it); s.erase(*lower_it); } else if(lower_it == s.begin()) { ans += abs(i — *lower_it); s.erase(*lower_it); } else { auto another = lower_it; --another; if(abs(i — *lower_it) >= abs(i — *another)) { ans += abs(i — *another); s.erase(*another); } else { ans += abs(i — *lower_it); s.erase(*lower_it); } } } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int t = 1; // cin >> t; while(t--) { test_cases(); } return 0; } ~~~~~"> ...

      Above is the implementation which I did during the contest. seems to be giving the wrong answer on the test case.

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

        please put your code in spoilers. Otherwise it makes the comment section unnecessary lengthy.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Guess who just showed up at 8pm on a Sunday night to give the contest only to realize it was at an unusual time. One more contest to reach 1200 Let's goooo!!!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one tell why i am getting tle on test case 26 in Problem D Armchairs. 116422974

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

    while passing the vectors in the function use call be reference method otherwise the whole vector will be copied in every function call. 116426242

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. 116419179 why I am getting MLE ?
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're missing this line if(dp[i][j]!=-1){ return dp[i][j]; }

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

    Your problematic line is setrecursionlimit(10**6).

    1. Using setrecursionlimit(10**6) takes a lot of memory on PyPy. 768 * n bytes to be exact (where n = $$$10^6$$$ in your case). That is the reason why you are getting MLE.
    2. Even if you had enough memory to run setrecursionlimit(10**6) it still wouldn't allow you to recurse to depth $$$10^6$$$ because of the default stack size being very limited. C++ also has this same exact issue, but in the case of C++ it is fixed by compiling it with the flag --stack=268435456.

    So how do you do deep recursion in Python? A while back I made this to basically allow for infinite recursion. You can read about it here.

    Here is your submission using it 116495993. (Unfortunately it gets TLE since $$$O(n^2)$$$ with $$$n=5000$$$ in Python requires fast running code).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do failed hacks decrease my place/rating?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i think problem C was so hard for being C in div2

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

Has systests started?

My solution was hacked for TLE, but I used the same hack on my solution and it did not TLE (1933ms / 2000ms)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's really strange.

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

    There are different runtime randomisations done which affect the runtime of a program every time it is ran differently.. It can be analysed that since the solution just passed the time limits barely, this may have been the cause.

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

    I believe that the hacks have not yet been added into the tests. I reran a couple of mine and found that they were subject to exactly the same set of tests. My guess is that they will be added soon and then a full system test will follow.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this competition unrated?

»
3 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Please can someone explain me in an easy way to solve D.

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

    Suppose the sequence is as follows 001001101110. Let the number of 1's be k here. Just invert the sequence 110110010001. Let the number of 1's be m here

    Now think like this.The number of 1's in the inverted sequence must be k.So the problem reduces to choosing k ones from the m ones in the inverted sequence.We can use dp to solve this.I have designed dp[i][j] as following: dp[i][j] stores the minimum number of minutes to attain the situation that uptil i index the number of 1's in the inverted sequence is j.Example dp[4][2] implies that uptil position 4 if there are 2 ones what is the minimum number of minutes I have to spend.

    As we can see in the inverted sequence till position 4 '1101' is possible. The 2 ones could be anywhere.dp[4][2] could have attained minimum at any of the following configurations which we are calculating using dp: '1100','1001','0101'.So we can see that we are choosing just 2 '1's out of the 3 positions where 1 can be put and finding dp[4][2].I know its a little complicated ,but once you understand what dp[i][j] means I guess you can understand the way I am approaching.You can check my solution for the complete code.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the ratings be updated

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

    System test is still pending. Once it will get complete ratings will get updated. (We should ask for editorials rather than updating ratings)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the System test done?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not yet started

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. But hacking phase was over well before 6 hrs. I guess. I thought it was done. Thanks for clarifying.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why didn't i get points after i finish the competition? (1 ranked 3500) please help me. i'm new here

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

    The rating result sooner or later will came out, Don't worry about that.

    You can check out the unofficial rating prediction in https://cf-predictor-frontend.herokuapp.com

    It's pretty accurate.

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

      it did not work it show Good luck & high rating! every time

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

        It(the extension) changes the html of the website and you need not click it. Just go to standings page on codeforces and as last column of the standing table you can see rating changes. In their website you can directly see rating changes of everyone

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

Is the editorial released for this contest?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the problem D for me ? like the state and the transition of the dp !

Thanks

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://codeforces.me/blog/entry/90729?#comment-791594

    Check this comment.

    You can refer to my code for the implementation part. 116414468

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    • Firstly you have to store indices of '1' in array A and indices of '0' in array B in sorted manner.
    • Now every element of array A will have to be paired with exactly one element of Array B (Note : any element of array B can be paired up with only one element of array A also) for reaching required final condition.
    • dp(i,j) where i is the current index of array A and j is the current index of array B gives minimum time to reach final condition from current position (i,j).
    • For position (i,j) we will have two option :-
      • (1) Pair up i with j and move to (i+1,j+1).
      • (2) Leave j and move to (i,j+1).
      • and dp(i,j) will be minimum of above two.
    • Final answer will be dp(0,0) (i.e minimum time required to reach final condition from initial position (0,0)).
      You can see my solution : 116400573
      Hope explanation gives you some feel of intuition.Thanks!
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody give me a test case where my code for problem C will be wrong? 116456536

Or if you can notice any mistake, that'll be helpful too.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am under 2100 but my rating didn't change, can someone tell me why is that?

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

editorial?

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

No editorial?

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

When will we see the rating change for this round?

»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Eagerly waiting for editorial .

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Tutorial available now !!!

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

Why I think D is much harder than C and E?

Can anyone give me any suggestions on how to learn dp well?

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

    I have found improving my DP one of the most difficult things — you are not alone. The key to thinking about it for me is defining a 'state' of some description. How can I use the variables I have to define a particular state? The best way to improve this thinking is just lots of practice, and reading editorials.

    I then need to work out 3 things:

    • the base state: this is usually the position we start from

    • the end state: what position are we trying to reach?

    • how do I transition between states (and which variables do I iterate over, and in what order)?

    There is no 'algorithm' to define the states. This is the difficult bit. What makes sense? What information do I have?

    In this case the information I have is the number of people I have already moved, and where I have moved them to; in particular, what is the furthest right 0 I have used? I can therefore set up a two-dimensional array iterating over these variables: dp[i][j] = the minimum cost of moving i people into positions ending no further right than position j. I need to use the information of previous states, and the information of the starting positions, to define what an acceptable transition looks like. This is detailed in the editorial.

    What are the base states? I can move 0 people at no cost, ending at any position. So dp[0][j] = 0 for all j. Call dp[i][j] = INF for i > 0 initially. If it is not possible to achieve i transitions to the first j spaces, this value will not change.

    What is my final answer? I need all the people to move (say there are X ones in the original array), and I don't mind where the furthest right position is, so my answer is min(dp[X][j]) for all j. Since we know there are at least N/2 free positions, we are guaranteed a solution, so the answer will not be INF. If there were < N/2 free positions, the answer would be INF, indicating 'impossible'.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep. My suggestion.

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it
Rating update
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When will rating change

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

Finally, system tests are about to end

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

    I thought it took so long because you removed the cheaters

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved two problems why i get -14 ? :((

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The rating is given according to your place, not number of solved problems. You were too slow to get your expected place.

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

What happened !! My previous rating was before this contest 1481 why it's 1424 after it's rolled back it should be 1481

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

Problem D :

Wrong Answer on test 37

Submission link 198713081

Can you pls tell why it's wrong ?

Thanks in Advance.