Educational Codeforces Round 149 [Rated for Div. 2]
By awoo, history, 19 months ago, translation, In English

Hello Codeforces!

On May/25/2023 17:35 (Moscow time) Educational Codeforces Round 149 (Rated for Div. 2) will start.

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 Adilbek adedalic Dalabaev, 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:

Harbour.Space

Seize the Opportunity: Full Scholarships Available at Harbour.Space Bangkok

Exciting news Codeforces! Harbour.Space Bangkok Campus is offering 10 full scholarships to study Computer Science or Data Science!

Join us at Harbour.Space in the heart of Bangkok, Thailand, and unlock a world of opportunities. We're proud to share that we recently emerged victorious at SWERC, one of the most prestigious programming competitions.

At Harbour.Space, you'll have the privilege of learning from renowned experts like Mike MikeMirzayanov Mirzayanov and Kamil Errichto Debowski. These exceptional individuals bring their wealth of knowledge and industry insights to create a dynamic learning experience.

By becoming a part of our vibrant and inclusive community, you'll collaborate with brilliant minds, fostering a culture of growth and innovation. Our students, who are qualified and talented, have the opportunity to compete in ICPC, showcasing their skills on a global stage.

Join our alumni who have gone on to work at leading companies such as IBM, Google, Deloitte, Amazon and more, paving their way to success.

Requirements:

Study Commitment: 3 hours/day. You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.

University requirements

  • CV
  • High School/Bachelor's Degree
  • English proficiency
  • Medalist in any Programming competition is a plus!

Make sure to apply before June the 30th, 2023, to be eligible for the scholarship and reduced application fee!

Ready to embark on your path to success? Apply now here.

We can't wait to welcome you to our amazing community.

All the best, The Harbour.Space Team

UPD: Editorial is out

  • Vote: I like it
  • -67
  • Vote: I do not like it

Comments Comments (153)
| Write comment?
»
19 months ago, # |
  Vote: I like it +67 Vote: I do not like it

I seriously want that Mike's T-shirt...

→ Reply
»
19 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Please don't be another SpeedForces Edu Round, otherwise excited about this.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    Please don't be another HackForces Edu Round

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

    they literally just made speedforces

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      not really, actuallly problem F seems pretty easy ( I didn't solve it, my solution fails at 23 test case ) .

      My implementation is little hard, SSRS_ has implemented is very easily with two priority queues.

      basically, we need to apply binary search on the final time, and maintain how many editorials we can write in the given time, if we split at index 'i' ( splitting that first person writes as many as editorials from index '1' to index 'i', and second person writes as many editorials from 'i+1' to 'n' within given time ) .

      → Reply
»
19 months ago, # |
  Vote: I like it +18 Vote: I do not like it

its taking too much time to be in queue is it problem on my end or happening with yall

→ Reply
»
19 months ago, # |
  Vote: I like it +87 Vote: I do not like it

WHY ARE THERE NO TESTERS FOR ANY EDUCATIONAL ROUNDS?

→ Reply
»
19 months ago, # |
  Vote: I like it +22 Vote: I do not like it

https://mirror.codeforces.com/contest/1837/problems never gets updated! I waited 10 minutes and then finally got to know it's WA on test 1 after 10 minutes when solutions were rejudged. queue is also long, taking so much time for the verdict

→ Reply
»
19 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Still in queue for B. Should i resubmit?

→ Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

stringforce

→ Reply
»
19 months ago, # |
  Vote: I like it +30 Vote: I do not like it

"problems and examples will be in announcements"forces

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    by the way speedforces too HUUUUUUUUUUUUUUUUUUUGE gap between D and E

    → Reply
»
19 months ago, # |
  Vote: I like it +53 Vote: I do not like it

(()deforces

→ Reply
»
19 months ago, # |
  Vote: I like it +29 Vote: I do not like it

I dont think i will participate in edu rounds anymore. I asked if my submission is going to be judged after it was in queue for 10 minutes. While I got the answer it was judged and the answer was "No comments". There is no need to be arrogant and in my opinion that was. Also, this would not happen if they tested the round.

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +46 Vote: I do not like it

    "No comments" is very classic answer if they don't want to tell you anything, it wasn't arrogant (in my opinion).

    → Reply
»
19 months ago, # |
  Vote: I like it +164 Vote: I do not like it

→ Reply
»
19 months ago, # |
  Vote: I like it +36 Vote: I do not like it

This contest is really bad. What is this problem D? The solution is pretty dumb for a D. I think ABCD were really silly and this round is really bad. I liked problem E though.

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

    so u will be getting +delta then!?

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      I won't but I'm not mad about that. It's just that the contest is unbalanced and problem D shouldn't be like that

      → Reply
»
19 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Why time constraint was so small on F? my nlog^2n solution with segment tree could not pass, had to remake it into a priority_queue solution with same nlog^2n. (smaller constant with priority_queue)

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

    did you use only segment tree ? or was it persistent seg tree ?

    can you please enlighten how to do it with normal seg tree ? ( i used persistent seg tree ) which was huge implementation. :( .

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

      I used normal segment tree. First I created a vector of pairs where I put { a[ i ] , i } the I sorted that vector and assigned an index to each pair. I use that index to store them in segment tree. Then I binary search on the answer. I use two segment trees, for each answer I rebuild both segment trees in the following way: first segment tree is empty, and second segment tree is full with activated nodes. In each node of segment tree I store pairs, where first element is the sum of times of activated verticies and second one is the amount of them. While checking the answer I go from right to left, activiating each vertex of the current pair { a[ i ] , i } in second first segtree and deactivating in the second one. Now what I need to check is if I can get some prefix of both seg trees such their activated times are less then the answer I am checking and the amount of activated verticies is maximum possible. For that I create a recursive function for each segment tree, where I first check the root of tree and its value, if the time of activated verticies stored in the root is less or equal to answer(which I am checking) time then I simply return its activated verticies count, otherwise I check for its left and right children.

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

      207253723

      I used ord array to compress the indices.

      → Reply
    • »
      »
      »
      19 months ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      You can maintain prefix sums on a Segment tree.

      My solution
      → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

the worst contest

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

another really bad educational round

→ Reply
»
19 months ago, # |
  Vote: I like it +52 Vote: I do not like it

B completely ruined my round,TEST YOUR PROBLEMS.

→ Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

For the problem D is there any chance that we need to use more than 2 color because i tried many sequence ans only i found only 2 color is enought to paint.

→ Reply
»
19 months ago, # |
  Vote: I like it +84 Vote: I do not like it

Worst contest I have ever seen!..

The sample test case was wrong and it delayed me a lot. Also, because of rejudges, there was a queue so I could not see my verdict for a while.

Also, I could not submit my code in the last 30 seconds maybe it was about my internet but giving the sample wrong was a big mistake :(

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

    I was also unable to submit my code in the last minute. I think we should try using m1.codeforces.com for the next contest

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

may anyone help me ,plz? i dont know why does it give me WA (problem B:) https://codeforces.net/contest/1837/submission/207236832

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 15   Vote: I like it 0 Vote: I do not like it

    1

    10

    <<<<<<><<<

    your answer : 9

    correct answer : 7

    1<2<3<4<5<6<7>1<2<3<4

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Test case
    → Reply
»
19 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Unrated would be better than this situation

→ Reply
»
19 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Nice E, solved it 2 minutes after contest:)

→ Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The last 2 rounds made me realise that expert is not for me ;(.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i'm gonna cry because of the problem E....

→ Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Really bad Contest . Solutions can be easily guessed .

→ Reply
»
19 months ago, # |
  Vote: I like it +14 Vote: I do not like it

This is really the most unexperienced game, abcd is violent, e is too big, there is no room to learn, total useless。

→ Reply
»
19 months ago, # |
  Vote: I like it +20 Vote: I do not like it

→ Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Again, a shit educational round. Problem A,B,C,D can be done in 25-30 minutes and rating depends on whether or not you incorrectly submit B. Last educational round for me,you learn nothing and only have headache.

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

Worst Contest !!! Didn't liked the problems at all

→ Reply
»
19 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Very Cool F except the TL

→ Reply
»
19 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Very bad experience, all the time was wasted on understanding the meaning of the question, and I once doubted whether I was from Earth

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

    That's a very serious concern if you did indeed doubt your origins as you mention...

    → Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I don't know why I wasted time waiting in the queue. Could have solved other Problems earlier. LMAO

→ Reply
»
19 months ago, # |
  Vote: I like it +40 Vote: I do not like it

Solved A-E and passed pretest of F in 3899ms (which will be TLE in system test).

A: If x%k!=0, we just need to move by x, otherwise since k>=2 we need to move by x-1, and then move by 1.

B: Consider the longest maximal block of same symbol, let it's length be k. Then If we put 1 at every local minimum and k+1 at every local maximum, we always have enough numbers from 2 to k to fill other positions.

C: We can see that a consecutive block of same numbers (0 or 1) plays the same role as a single number, and more blocks takes more operations to sort the string. Therefore, we can fill '0' into a block of '?' between '0' and '0', fill '1' between '1' and '1', and fill '0' or '1' between '0' and '1'. For these blocks at the front or the back of the string, we can assume that there's an additional '0' at front and '1' at back of the string, which won't affect the answer.

D: For any beautiful sequence the number of occurences of '(' and ')' will be the same, so if they are not the same we can simply output -1. Otherwise, there must be a solution with k<=2. In fact, we can record the prefix-sum of the string (assume '('=1, ')'=-1) and change color whenever the sign of the prefix-sum changes, then brackets with non-negative prefix-sum will form a regular sequence, and other brackets will form a reversed regular sequence.

E: We can see that teams of number [2^(k-1)+1 , 2^k] will lose in the first round, teams of number [2^(k-2)+1 , 2^(k-1)] will lose in the second round, and so on. So in the first round, we check 2^(k-1) pairs of adjacent positions, and each pair must contain a team with number larger than 2^(k-1). If any of such a pair contains 2 numbers > 2^(k-1) or 2 numbers <= 2^(k-1), there's no solution. Otherwise we have 2^a*(b!) ways to arrange teams of number [2^(k-1)+1 , 2^k], where a=(how many pairs of positions are both undefined), b=(how many pairs of positions contains no teams with number > 2^(k-1) ). Then we can eliminate teams with larger number in every pairs, and solve the problem recursively.

F: I tried to solve it by segment tree and ternary search in O(n*(log(n))^2), but it takes too long times to pass the system test. Maybe there will be solution with smaller constant.

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

    Not sure if it is compatible with your solution, but in F replacing segment tree with a priority queue or a set gives AC in approx 3 seconds.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      Nope, my solution with std::set gives TL on 23 pretest though I changed cin/cout to scanf/printf and had no stupid memory allocation.

      207257375

      I wish in C++24 std::set is automatically substituted by priority_queue if my code does not contain iterators, BS and etc :)

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

        Probably requires minor constant optimizations. 207226137 passed in 3 seconds.

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

          Quote: "...but in F replacing segment tree with a priority queue or a set..." I mean std::set can't pass TL but std::priority_queue can.

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

            Might be possible, my bad.

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

    Can you explain bit more about "2^a where a=(how many pairs of positions are both undefined)" in your E's solution?

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      If a pair of position is -1 -1, then we can put the team with larger number on the left or right of this pair, so each pair gives us 2 options. Otherwise, which number will be larger is determined in this pair.

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

        Dont the numbers in range [1,2^(k-1)].Doesn't they impose constraint on other number ? How can they be placed freely ?

        For suppose, if 1 is place in Xth pair then 2 cant be placed in (X+1)th pair, if they get placed they 2 will get eliminated in second round but they need to continue until finals ?

        → Reply
        • »
          »
          »
          »
          »
          19 months ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          If a team cannot be decided in kth turn, you bring it to the next turn with -1, You can only count those teams can be determined in kth turn within (2^k-1, 2^k] and leave those undetermined to the (k-1)th turn. The key observation here is when a team gonna lose is fixed at the beginning. So the whole process is like you assign a seed to a team only if that team will lose in that turn.

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

    use binary search on answer in F instead of ternary search, and then priority queue to find maximum numbers <= sum in prefix and suffix

    mine runs in 2.7s

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

    Sorry YocyCraft:( (Hacked)

    → Reply
»
19 months ago, # |
  Vote: I like it +7 Vote: I do not like it

10k ACs on C and 4k ACs on D, wow! Never seen anything this extreme before.

→ Reply
»
19 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Nice contest. Incase you are stuck on Problem A, Problem B, Problem C, Problem D. You can use check the following video tutorial- video link

→ Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it +26 Vote: I do not like it

The Worst Education Round I ever seen.

Reasons:

1.Big changes on problem B:Wrong sample,too long queue(after change),etc.This is terrible.

2.Speedy Edu.Problem A,B,C,D is too easy and E is hard.4,600 people passed D,but only 367 pass E.This mean the rank between ~400 and ~4000 is FULLY depend on the Penalty.

More I know:the B is similar as atcoder contests

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

    were they really too easy and im just dumb? because i only managed to solve A :D

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      S/he's speaking from the perspective of an Expert. Don't feel too down about your performance. :)

      → Reply
»
19 months ago, # |
  Vote: I like it +9 Vote: I do not like it

My solution to B got WA on test 1 at first, but once the samples were changed (and before the announcement that the previously solutions would be rejudged) I resubmitted the same code with a no-op to see if it would pass. Then both solutions gave a WA time penalty :(.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't know that a priority queue is faster than a multiset, and if the intended solution has a complexity of O(n * log^2n), then, in my opinion, should have also considered the multiset solution.

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

    Priority queue is a binary heap which is faster than any balanced binary search tree by the constant factors and the access time of O(1)

    → Reply
»
19 months ago, # |
  Vote: I like it +19 Vote: I do not like it

So many errors in the statements... Contests of such scale should be thoroughly tested!

→ Reply
»
19 months ago, # |
  Vote: I like it -14 Vote: I do not like it

worst contest I have ever seen!

this round should be unrated due to long queue time(~1 min for every submission) and wrong examples in B.

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

    yes

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

    You are wrong. Here's why.The authors and coordinator put weeks of work into it!

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      No, all of the educational rounds are being prepared in the contest day.

      → Reply
»
19 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Problem B has a quite similar approach with this problem.

I find it a bit funny tho because problem B is about <>, problem C is about 01 and problem D is about () lol

→ Reply
»
19 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Using discrete to convert time complexity from nlog(1e18)log(1e9) to nlog(1e18)log(3e5) then pass pretest on Problem F. Time limit is toooooooooo tight.

→ Reply
»
19 months ago, # |
  Vote: I like it +36 Vote: I do not like it

One tip if you got WA on test 8 of E: Please notice the input format.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    you are perfectly right! In the contest I have great confidence in my algorithm. But always WA in test8.Damn!When I saw test 8 after contest, I just realized that I mixed up the team ID and seed ID，Oh Damn Damn Damn!!!

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

      Same here, 1h wasted trying to find the WA test 8...

      → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please assist me with submission :207266027 ? I am unable to determine why my submission is incorrect. Thank you very much.

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

    no need ,the input format is really annoy

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

      I don't understand how this type of input format couldn't have been identified in any of the 6 examples.

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

      Me too, sadly

      → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

800-Forces

→ Reply
»
19 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Can anyone please explain why the answer to this test case is 4 for question 'E':

3 -1 7 -1 8 2 -1 -1 5

What I understood from the question is illustrated below: _ & 5th | _ & _ | 8th & _ | 2nd & 4th So according to this arrangement, 4th would have rank '5' which is not desired. So shouldn't the answer be 0?

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    plz someone explain this UPD- They are seed-wise arranged

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

      It is given that team 'ai' has seed 'i' ;-;

      Therefore for given example: 3 -1 7 -1 8 2 -1 -1 5

      Team 3rd has seed 1.

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

    Got my answer. Should have read the input properly ;-;

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

      what is your answer?? having same problem

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

        It is given that team 'ai' has seed 'i' ;-;

        Therefore for given example: 3 -1 7 -1 8 2 -1 -1 5

        So, Team 3rd has seed 1 Team 7th has seed 3 .. and so on

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

    Is not it 3rd can 5th for the last bracket? I think you have off-by-one error.

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B ruined my contest. Please at least take a glance and make sure that the examples are correct (it was so obvious that the examples were wrong ...).

→ Reply
»
19 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Hello, I enjoyed this contest. thanks to the problem setters.

During the contest, I solved problems $$$A - E$$$. Just after the contest, I solved problem $$$F$$$.

Problem $$$A$$$: if $$$N \mod K == 0$$$ it's $$$N-1$$$, $$$1$$$ otherwise it's $$$N$$$.

Problem $$$B$$$: the answer is the longest increasing(or decreasing) subarray.

Problem $$$C$$$: how many disjoint $$$1$$$ s are there ($$$-1$$$ if the last number is $$$1$$$).

Problem $$$D$$$: if the number of opening brackets isn't the same as the number of closing brackets it's $$$-1$$$. otherwise, if it's a beautiful bracket sequence the answer is $$$1$$$ otherwise $$$2$$$. We can color the biggest beautiful bracket sequence with the color $$$1$$$ and the remaining brackets make a beautiful bracket sequence.

Problem $$$E$$$: We know which players will be eliminated in the first round. Let's say there is a $$$P$$$ number of $$$(-1, -1)$$$ matchup, and $$$Q$$$ number of players we need to eliminate on that round. On round $$$k$$$ the number of ways we can place the players that should be eliminated is $$$(2^{P_k}\cdot Q_k!)$$$. Then, we can assume those players are eliminated on that round and solve the problem for $$$k+1$$$-th round. Thus, we can recursively find the answer.

Problem $$$F$$$: I didn't solve this problem during the contest. I used multi_set, which I later changed into priority_queue to get accepted. My time complexity is $$$O(N \log^2 N)$$$. I don't know if the problem setters intended to cut submissions that used set. The idea of this problem is to find the answer with a binary search. For a chosen value, we check for each element to be the last problem of the Monocarp, and find the maximum number of editorials we can make in that situation. If it's over or equal to $$$k$$$ we can make it in for the chosen value. I still think the time limit for this problem is a little too tight.

Overall it was a good contest :)

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

The problems were very easy till D , it must be somewhat tough at least for C and D.

→ Reply
»
19 months ago, # |
  Vote: I like it +33 Vote: I do not like it

please start writing div3 contests

→ Reply
»
19 months ago, # |
  Vote: I like it +40 Vote: I do not like it

I passed F in last two minutes! Hope it won't FST.

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

D can u tell what's wrong with my soln first i eliminate all the regular seq from string and colored them with 1 then i reversed remaining and colored them with 2, if finally the stack is not empty i print -1; then did above process again but this time i reversed first then printed min of above 2 processes

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    nvm , got it, didn't print -1 ,i am an idiot

    → Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Seeing even experts getting WA for first time in B is such a relief..

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B is bad :( Promblem D is easy but I made many stupid mistakes... bad experience.

→ Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

"How many greedy questions have you prepared for this contest?" Problemsetters: Yes

→ Reply
»
19 months ago, # |
  Vote: I like it +34 Vote: I do not like it

This was not a good contest for div2. All problems were very easy compared to their expected hardness.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain why my solution is incorrect?

207239600

https://codeforces.net/contest/1837/submission/207239600

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    >>><>>><>>><

    Your approach: [0 1 2 3 2 3 4 5 4 5 6 7 6] best answer: [0 1 2 3 0 1 2 3 0 1 2 3 0]

    → Reply
»
19 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Was this the easiest div 2D ever in terms of problem rating and solve count?

→ Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

queue is so long!

→ Reply
»
19 months ago, # |
  Vote: I like it +6 Vote: I do not like it

maybe change the problemsetters for some time

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give a counterexample where my code gives a wrong answer?

207246737

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is this: not accepted / accepted
Only difference that the first one may only print out 2s instead of ones, but there is nowhere specified that colors must start with 1...

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

    It is given in the problem statement that we have to print from 1 to k

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, I am little surprised to see the number of submissions of B. Was the solution leaked somewhere ?

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

    There were also more participants than usual in this contest

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi this is the first time I join in a competition. But I only resolve the first three problems (A, B, and C). Will I get a rating score? Because I saw that my score is still 0 in my profile.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

very high time limit for F

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +55 Vote: I do not like it
Standings big picture
Problem calculated difficulties
→ Reply
»
19 months ago, # |
  Vote: I like it +10 Vote: I do not like it

gordan ramsay after giving todays contest.

"My gran could do better!"

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F is the most messed up problem I've ever seen. I can't believe it's that easy yet I can't solve :(

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

In problem B, if I start with the number X initially, if I encounter '<' I increment X else decrement X . Here is the code for it

vi ans;
ans.pb(5);
ll val = 5;

f(i, 0, n)
{
    if (s[i] == '>') {
        val--;
        ans.pb(val);

    }
    else {
        val++;
        ans.pb(val);
    }
}

deb(ans);

set<ll>st(all(ans));
cout << st.size() << endl;

}

Why is this approach wrong?

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    If the sequence is ">><>>" then

    Your answer: $$$[5, 4, 3, 4, 3, 2]$$$

    Optimal answer: $$$[5, 4, 3, 5, 4, 3]$$$

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

      I'm still getting the wrong answer when I apply your logic.

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

        That's why I edited it. You have to do it for both '>' and '<'.

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

someone pls explain how to solve problem F

→ Reply
»
19 months ago, # |
  Vote: I like it -10 Vote: I do not like it

My approach for Problem F:

Let us say we already have the k elements which are picked out from the original array, we can create a prefix and a suffix sum array and then iterate over the two picking the minimum of max(prefix[i], suffix[i]).

So now all we have to do is to find the k elements, we can find the k smallest elements in the original array and then take the maximum of that array, then check if we can/have to pick more than one occurrences of the max element from the original element, if yes we somehow have to find which occurrences of the max element do we have to pick in order to reach the minimum later on when we calculate the answer, I understand that the position of the max element matters but I cannot figure out how to optimize it in such a way so that it leads to the minimum ans.

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

    even then you will mp fail on testcase n=4,k=3 and a=[2,3,2,4]

    → Reply
»
19 months 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).

→ Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Trash round.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My rating was updated to expert few days ago and today it is showing back to specialist, it has reduced by some points in this contest. Have anyone else faced this?

→ Reply