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:

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

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

Me too!

me too, how to buy this, please anyone

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

Please don't be another HackForces Edu Round

Now it became guessforces.

they literally just made speedforces

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

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

WHY ARE THERE NO TESTERS FOR ANY EDUCATIONAL ROUNDS?

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

Still in queue for B. Should i resubmit?

stringforce

"problems and examples will be in announcements"forces

by the way speedforces too HUUUUUUUUUUUUUUUUUUUGE gap between D and E

F seems easier than E to me.

(()deforces

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.

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

Don't wanna be this man, but since when experts struggled to solve C?

it's a bit of an exaggeration, but there was Educational Codeforces Round 133 (Rated for Div. 2) last year where C had under 1k solves.

I'm aware about that, just wanted to point out that it is a bit odd comparison.

one time Div2C was NP-hard

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.

so u will be getting +delta then!?

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

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)

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

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.

207253723

I used

`ord`

array to compress the indices.You can maintain prefix sums on a Segment tree.

My solutionIterate on every prefix-suffix pair $$$i$$$ and binary search on the minimum time required to finish the editorials if Monocarp only covers from the prefix and polycarp only from the suffix. Then if you keep a prefix-sum segment tree on the sorted list of editorial times you can quickly search for the last position where $$$sum \leq x$$$ which gives you the maximum number of editorials either of them can cover.

Updates are basically $$$0 \rightarrow a[i]$$$ when $$$a_i$$$ is added to the available for set for either of them and vice-versa.

I used KACTL's Fenwick implementation for it but the idea is the same. 207239500

the worst contest

another really bad educational round

B completely ruined my round,TEST YOUR PROBLEMS.

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.

No. 2 is sufficient

Submission can you give me some sample cases where my code fails. Couldn't find any test case as of now.

1

10

)))((())((

2 : 1 1 1 1 2 2 2 2 1 1

You can just reverse the whole string which is 1 color

2 is enough.

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

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

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

1

10

<<<<<<><<<

your answer : 9

correct answer : 7

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

Test caseAnswer should be 3, but your code gives 4. In line 42, why are you doing cnt1--?

Unrated would be better than this situation

Nice E, solved it 2 minutes after contest:)

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

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

Really bad Contest . Solutions can be easily guessed .

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

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.

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

Very Cool

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

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

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

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.

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.

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

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

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.

Might be possible, my bad.

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

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.

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 ?

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.

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

Sorry YocyCraft:( (Hacked)

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

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

Amazing and very clear video tutorial <3

Very helpful sir ❤️❤️

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

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

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

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

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.

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)

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

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.

yes

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

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

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`()`

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

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

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

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

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

no need ,the input format is really annoy

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

Me too, sadly

800-Forces

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?

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

It is given that team 'a

_{i}' has seed 'i' ;-;Therefore for given example: 3 -1 7 -1 8 2 -1 -1 5

Team 3rd has seed 1.

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

what is your answer?? having same problem

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

oh

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

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

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

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

please start writing div3 contests

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

Hello. I am from the future. It FSTs.

You are wrong. Here's why.

you are lucky enough!!!

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

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

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

Candidate Master also get WA in problem B

I second this

I got 2 WA for B but 0 WA for A, C, D... what a contest.

i got 3 WA on B...

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

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

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

Can anyone please explain why my solution is incorrect?

207239600

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

`>>><>>><>>><`

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]

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

queue is so long!

maybe change the problemsetters for some time

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

207246737

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

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

i wish i could read

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

There were also more participants than usual in this contest

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.

Yes,Wait for some time

very high time limit for F

Standings big pictureProblem calculated difficultiesgordan ramsay after giving todays contest.

"My gran could do better!"

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

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

}

Why is this approach wrong?

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

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

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

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

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

someone pls explain how to solve problem F

will i be able to becomes red one day :/

you will be if you cut the suffix. ✧(≖ ◡ ≖✿)

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.

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

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

Poor English. It is 'trash' instead of 'trush'

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?