Hello Codeforces!

We're glad to invite you to Codeforces Round #610 (Div. 2), which will be held on Dec/24/2019 17:35 (Moscow time). It will be rated for **all participants with a rating below 2100**. You will be given **six problems** and **two hours** to solve them.

The problems were invented and prepared by the team from ITMO University: Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, MikeMirzayanov.

Special thanks to MikeMirzayanov for great systems Codeforces and Polygon and coordinating round preparation.

**UPD1:** Special thanks to the ITMO University testers team: Nebuchadnezzar, Alexvsalex, Darui99, golikovnik, sharepoLOVEDDD, Mr.Hakimov, zergey.gad, MeowMr, Ilya-bar, 1ncendiary

**There is an interactive problem in the round**. You can read the guide for interactive problems here.

**UPD2:** Scoring: **500 — (500 — 1000) — 1750 — 2500 — 2500**

We hope you will enjoy the problems. Good luck, wish you a high rating!

**UPD3:** Congratulations to the winners!

- Tsypkokokokoko
- K.Yuuki
- hyhtsdy
- ptica
- junukwon8
- A_n_o_n_y_m_o_u_s
- AnotherRound
- ark_84
- rtilikay
- p1rattttt

Editorial will be published soon.

**UPD4:** Editorial is out!

hoping good contest :D

Any subtasks?

This is an online contest so there will be no subtasks

I think you meant: This is an Official Codeforces Round so there will be no subtasks

He seemed to mistake subtasks of problems to subtasks of pretests. Why is everybody going so hard on him lmao?

I am very worried about the fact that Mirzayanov’s pawns can hold two contests a month, while the rest are waiting in line for six months

New pawn of sorry_marymarine

Hello everyone — Good luck for all I hope I can become a Candidate Master after contest

I am sure you will, brother. ALL THE BEST!

Before round:

Round is rated for Div.2 participants

After round:

UNRATED!Sad story......

that is a very bad joke.

Finally there is an interactive problem after 9 rounds ! :D

hope interactive problem is not a binary search. pleaaase

It can be a geometry problem too.

or a probability one

are there interactive problems in ICPC contests !

Yes there are!!!

hope for short statements like the last round !

it's look like interesting contest

I hope this contest should be good.

We can see interactive problem in Codeforces after a long time.so everyone should learn what is interactive problem and be ready for contest. All the best and wish u high rating

Can someone please explain what is an interactive problem and whats the difference between and regular problem and an interactive one?? Bcuz i did not really understand the meaning by reading the blog from MikeMirzayanov :) tnx for your help!

Interactive problems(over simplified): the input isn't given all at once, or it's in a "Q&A" style.

Which problem will be Interactive ?

I just finished my graduate entrance exam.It is so excited that I can join contest now.

Exciting for contest after semester exam.

Interactive problem and 20 questions ..

can somebody help me with interactive problems

you give the jury some numbers and it will give some information about that. then you should use this information for next question or guess the answer.

What interactive problem will be A,B,C?

Unlikely

I bet that 80% participants of this contest has no girlfriend. It's Christmas Eve!! Go hang out with friends!!

Code with gf =)))

Why you don't go !?

I guess that

100%is much more accurate!!!for sure 1% of this 10000 person have girlfriend.Don't you think?

Well that sounds true but I'm confident enough they are not more than 5%!

Me either.

Yesterday I was broken up with her. :< Sad ChristMas

Pressing F for you

[deleted]

Can anyone provide link to the mirror website m1/m2/m3 I am not sure where to find it

They will put it just before the contest I think.

m1.codeforces.com

m2.codeforces.com

m3.codeforces.com

Tnx.

Thanks

Merry Christmas!!!

Good contest

feeling orz................

Problem statements are longer than my

~~hair~~.Hope for strong pretests. Merry Christmas!!

What is test 6 for D?

What is the test case 2 for Problem B.

Am I the only one who over-killed

Cwith segment tree and stuff and later realize it could have been done simply:((Am I the only one who doesn't know how to do C?

I think C cab be solved by Sorting by overriding the comparator function. if we create array and sort this such that after sorting wrt mandatory time i.e. by giving most preference to the problem with least mandatory_time. Arr[i] holds info about problem (actual index of the problem, it's mandatory time and it's easy/hard). and putting some constrain on current time and total time while going through this sorted array can solve this.

I didn't got time to submit. I will do it after system_testing

I think problem C has some problemProblem C- In statement: 2 <= n <= 1e5

Whereas just changing maxn=1e5+5 to 2e5+5 changed an RTE to AC

This should be rejudged with proper input files and first ac submission should be counted.

UPD5:sorry seems like, I've missed the announcementIt's written 2e5 in C statement

It was 1e5 at the start of the round and updated during the round.

How to solve D?

Solution of D :

You can get length of required string and number of 'b' by asking two queries.

String of 300 a's will give you value = 300 — n + no. of b's.

String of 300 b's will give you value = 300 — n + no. of a's.

Plug them to get above length and no of b's.

Take a string of n a's and start locking the indexes in order by using provided answer and no. of b's left to be selected.

Just curious: Are you intentionally dropping your ratings?

No.

My approach for D, making at most $$$n+2$$$ queries: 67539477

First make two queries, one with 300 A's and the second with 300 B's to figure how many A's and B's are in the string, and therefore its length.

Notice that the edit distance from a string of length $$$k$$$ with all of the A's already placed is $$$n-k$$$ if and only if between no two A's we have more B's than in the hidden string (as then we could not make only insert-operations).

Using this, add B's before the first A until the edit distance doesn't decrease, then place the first A and repeat. Thus after the $$$i$$$th operation, we know a prefix of length $$$i$$$ of the hidden string. Thus after $$$n-1$$$ operations we know the entire string (as we know character counts). Including the first two queries, we make at most $$$n+2$$$ queries in total.

To get number of A's and B's you can also query a single "a" first, and then an all "b" string of length equal to answer of first query.

I think I did this, but I'm getting WA on Q5 with the comment:

Do you know what is wrong?

My solution is failing with input abababababababab, and the error message is

wrong answer Line [name=s_17] equals to "", doesn't correspond to pattern "[ab]{1,300}"

However, when I tested locally it seems to work, and I also added asserts to check that I never output empty strings. My code is below.

http://codeforces.com/contest/1282/submission/67561919

Thank you!

I couldn't solve the problem, but I think you should look over here probably. This comment

Hey simp1eton, Could you tell what the problem was. I am receiving the same verdict as you mentioned. I used 300 a's and 300 b's to find the length. Here is my submission 67569644

I assumed wrongly how edit distance is computed. I think if your program throws and exits for any reason, the checker says that your program outputs an empty string

Can anyone help me why I am getting wrong answer for Div2 B1??? My approach- Sort the array. Check if you can buy all items till index 'i' supposing that you got i-1 item for free. 67533371

Do you consider the case when you purchase the first item itself, and not for free?

YES

Your program outputs 4 for this, but should be 6

Can you please clarify your test case what are you taking?

The test case is as follows -

1

6 4 2

1 1 1 1 2 2

Answer should be 4 right???

No, you can buy all, choose the 2nd 1, the 4th 1 and the 6th 2

Update — I think you somewhere forgot to do i += 2

please explain solution of B1 i am beginner here

Sure, for the case of $$$k = 2$$$ (which is easier actually, since you need to solve the problem in $$$O(n)$$$ time); first of all, sort the array on the basis of prices. Now try to understand the points mentioned here as to why they're true. Now, going ahead, since k is just 2, you either choose the first one and then keep taking 1 on 1 as the offer; or you take all goods on offer, the answer is the max of the two.

with two 1's can take other two other 1's and with one '2' can take other '2', in all 6 while spending 1+1+2=4.

Got it. We can apply the offer again and again. I thought that we can apply it only once. Wasted an hour on this.

Oh shit dude (cries in corner)

what is the hack of B2??

O(k*k) Algorithms will not work. While there were no tests as such in Pretests.

how to solve B2?

first sort all items. then you make a list with size k that ith element is the cost if you take i starting elements alone. for each item(after k initial items) you update the list.

can you please elaborate more?

Sort the array first.

Try to understand the following facts -

If not choosing to use the offers, you should buy only the first few(< k) items, and not from any later part of array.

Once you buy some or all of the first k items, you would only use the offer now, and no individual buyings.

thanks a lot.

Can someone please explain why I got TLE in the problem Div 2-B2 ? Here is the link to my solution.Solution

Because PriorityQueue.remove() function has O(n) complexity instead of O(log n) in Java

Got it thanks a lot. There was actually no need of priority queue. I just removed it and got the solution accepted.

1

6 17 2 6

0 0 1 0 0 1

7 6 3 7 10 12

Why should that give us 1 as an output? (Problem C-petya and exam) can someone help me?

At t = 2, you can solve any one of the non mandatory easy problems

oh thank you man, I've understood it now

Ultra fast system testing

Ok codeforces

*your worst

Hey man, your contribution is already -26. So I strongly recommend you think twice before you make a comment .

I agree tbh. The problem statements are overcomplicated and the score distribution is really not balanced. Who decided to put D = E?

E was a very nice problem. Among the best I've seen in a while. Too bad I had a silly bug in my code during the contest.

D was also nice. Hats off to the authors.

One of the fastest one I've ever seen...

For problem B2, why are so many solutions getting TLE on test case 12 or 13?

D&E are realy good problems! ABC — stupid idealess problems!

Hello Codeforces, I didn't see the notification that the bounds for problem C were changed. As a result, I didn't notice the change for a long time. Would it be possible to unrate me? thanks!

My first

correctsub with wrong bounds: https://codeforces.com/contest/1282/submission/67543972 Changed to 2e5: https://codeforces.com/contest/1282/submission/67558110No

Unrate :eric:

Am I the only one who did B by handling $$$K >= \sqrt{N}$$$ and $$$K < \sqrt{N}$$$ differently?

Well, I was planning to do the same at first :D

I'll post a screencast of the round within 12 hours. (I will also add those 5 minutes which I did not have enough to pass E).

UPDI hope the screencast will be available tomorrow at 07:00(MSK) by this link in good qualityUPD2It is availableApprox 25% of all ACs of D ended up in fst, the edge case being bbbb...300 times. This was an obvious edge case and I do not get why you guys did not include it in pretests. Was this deliberate by any chance?

Fortunately, Tsypkokokokoko hacked my solution with this test case and I managed to correct my solution

Congratulations on your 1st rank, Tsypkokokokoko!

Actually I do not understand what is the difference between bbbb… 8 times (as in test 4) and 300 times. What's more, I wonder why would anyone want to include the 300 constant in their program (and so, it's no longer an "Edge case")

Well I was checking your code and it seems the rand() part saved you. try printing just "a" in the beginning and you will know.

Oh, that's like the weirdest thing that happened to me for the past 2 years on Codeforces :P If I print just "a" in the beginning (which I tried to do, submit #1...) I get TLE 4 (which is the first monochrome test). There are MANY such tests up to #67, so idk why those solutions make it that far...

Seem like you got really lucky :p

More like time trouble :)

With 5 minutes left, I couldn't figure out how to find |s| and I just made this leap of faith, haha

Btw, I was 110% sure this would fail the systests and even now I don't know why it passed (there were soooo many monochrome strings)

My program uses aaa..aaa (301 times) as second query in this case and for some crazy reason it is not allowed. I would be very angry if this was an actual round for me, not the one where I do educational video.

Guess, it's time to rewrite this one :D https://codeforces.com/blog/entry/62744

More like reread, and also the story with Golovanov399 and 22 vs 20. Yes, double standards.

Rereading this particular fragment would be enough I guess:

Nope, this is not it. I didn't ask for a clarification. Also I'm not that mad to consider the problem bad because of small issue.

Well, you don't have to build so literal analogies. It's up to you to decide what conclusions you leave for yourself from this situation. I just suggest you to think why you call not allowing

`string(301, 'a')`

"crazy" and compare this to that sentence from your blog.There is a clear divide between ranting about the problem during the contest in a clarification and ranting about the contest afterwards.

Also I didn't call

allowingcrazy.And yes, I already did admit that there is a resemblance, what's the problem?

Test 67 for D?

bbbbb....300 times

67542439 Can you help me with finding out what is wrong with this solution? It works with 5b's, and I don't see anything that would make it not work with 300 b's.

your code is probably printing 301 characters somewhere.

Thanks, I figured it out, it was because if there was 300 a's or b's, my code would continue after getting a query of 0.

Amazing system testing speed. Like

In problem C, I created 2 sets one to store hard problems mandatory time and the other to store easy problems mandatory time. Every time I check first problem in Easy problem + a and first problem in Hard problem + b and i take the one which Solved eailer. then I check if any problem should be solve in this time and I add it I only update the answer if the time at the end <= the total time of exam

Why this idea is wrong ? 67550974

Checker for D is incorrect. This solution https://codeforces.com/contest/1282/submission/67555058 still outputting things after getting 0 as response for the test "b" * 300, but I got incorrect hacking attempt on this one.

Hack is here https://codeforces.com/contest/1282/hacks/603027

In the problem statement it says that on such cases the checker will give an "arbitrary" verdict, which can include Accepted (depending on how the checker is written).

Good evening everyone! Help me please understand what am I doing wrong on the second problem, so for the input (n = 4, p = 9, k = 2) and the numbers { 2, 3, 4, 5 } the expected output is 4, mine is 3. Thanks in advance!

If you buy the 2nd good then it will cost you 3, and you will get the first one for free and you will be left with p = 9-3 = 6. Then just buy a good 4 for 5 and get good 3 for free. Hence finally, you have 4 goods.

Offer can be used more than once. You can pick 3 and 5,you get 2 with 3 and 4 with 5 for free

Yeah, cool!

Can someone tell what's wrong in this solution of D? 67559495

How come the pretests for D didn't include a single string with max length? It seems the longest string in the pretests had only 17 characters.

to add a little bit of suspense, I guess :)

Can not understand why let $$$O(k^2)$$$ solution pass B2 pretest.

how to $$$O(k^2)$$$?

Hello. Please AdvancerMan could you help me understand why 67555899 got WA. The problem is that when I run locally the 5th case it returns the correct spell.

Thanks in advance

This is your outputCheck how you calculate the edit distance.

that is exactly the problem. I am calculating the edit distance in a wrong way.

Thank you so much

still myself need lot of work to put on DP

I didn't submit because i couldn't solve Div2-B1. And i couldn't solve B because I kept thinking offer had to be applied once. I really think the setter should have clearly mentioned that :'( . Looking forward to next contest

can someone explain how to solve C?

I am getting

WAforProblem D.The checker says I printed an empty line (" ") which not acceptable , but my code doesn't print any such line.

Here it it : My Submission

Thanks in advance!

UPDATE : Resolved! :)

> If the number of spells exceeds limit (n+2, where n is the length of the spell s, which is unknown to you), you will get the Wrong Answer verdict.

That could be the reason

Yup I did check for that. My code always prints n+2 strings , no more than that!

AdvancerMan can you please have a look?

Thank you!

UPDATE : Resolved! :)

Your program prints no more than $$$n + 2$$$ strings but it doesn't print the correct answer to the first test as well. Your output for the first test:

CodeJust came online to update this XD

Thanks I messed up edit-distance part!

Thanks for the help! :D :)

Awesome problemset, super fast system testing and rating change -> In a word a nice contest!

This contest is also exiting for me, because I found my mistake in code for problem C last minute and submitted 30 seconds before the contest ends and it got Accepted, and became blue after a long gap.

Thanks for the nice contest!

div2 b is similar to house robber but cannot solve in the contest :(

For a second I thought I can't solve B2 so i went for naive approach in B1. after writing some stupid long worthless code i tried B and solved it much faster and with less lines of code.Should have just sticked to B2.

My solution for D got AC code. But it is wrong, because i write always n + 2.. Ok.. This solution on C++11 got RE code. Then this solution got RE too. Can anyone explain me, how is it working?

Try exiting the program if a == 0 or b == 0 as soon as you get them. I don't know why that would give an out of bounds error, but I had the same problem.

Ok thanks, it is really strange...

I don't understand the WA message

`wrong answer Line [name=s_8] equals to "", doesn't correspond to pattern "[ab]{1,300}"`

on D. I tested my solution locally and I am not printing any empty strings.you can't ask an empty string

No, I am not asking any empty strings.

It seems to me that checker does not handle termination after "-1" properly.

Shoudn't B2 be done this way?

sort the given array. maintain K lists of prefix sum of (i%k) indices only. Then find upper bound of

pin these lists, return the max. of these upper bounds. Also add to these upper bounds, those gifts which still can be bought without any offers, after each upper_bound applied.My submission is failing on 55th TC of 2nd test case. Can someone please help me with that? I am not able to get that particular test case, since it is not being rendered on CF.

It is simple dp, where dp[i] is min money to pay for first i problems. Sort the goods by price.

dp[i]==min(dp[i-1]+a[i], dp[i-k]+a[i])

You can allways buy goods one by one, or choose at any point to buy k goods at once. Anyway, you allways buy the cheapest goods.

What strange problems this contest have. I felt upset from Problem B(1).

Problem DWhy if I do more than N + 2 requests (exactly 1000 times)

"aabba"it passes 1st test? link. I guess that checker counts only unique requests, not the actual number of requests. My solution was making N + 3 requests (while I thought it was N + 2) and I was getting WA 5 the whole contest. I couldn't even think that the problem was with a checker :(after first time you print "aabba" checker stop it 67562780

I think that wasn't mentioned in the problem statement.

Anyone solve B with binary search..

Not sure it would work. In this problem if you can buy x items, there is no guarantee you can also buy x-1 items.

But some are manage to pass by using binary search. Can't understand how.. sol 1 — https://codeforces.com/contest/1282/submission/67533137 sol 2 — https://codeforces.com/contest/1282/submission/67532628 In the second case the user use the binary search twice.. Can u explain the logic behind both the solutin... Thanks..

My submission using binary search: 67564167. Not sure if my idea is the same as those above.

My idea is to sort the goods by their prices, then fix the number of goods that we have to buy separately (obviously, it's in range $$$[0,k-1]$$$), and finally using binary search to find the number of group of k goods that we can buy.

If the numbers of good that we buy separately is

`i`

, it's optimal to buy the first`i`

goods.Overall complexity should be $$$O((n+k)logn)$$$.

thanks, exactly same concept as describe by socketnaut and AngerAndMoney only implementation differ. Thanks.. Can us share any similar problem like this.

If you really want to you can binary search on the number of groups of size K you buy, then binary search on the number of singletons you additionally buy.

Yeah u are correct if your predicate is

`can we buy x items`

but if you consider predicate to be`can we buy at least x items`

then BS can be applied code : 67538774Thanks for replying, can u explain what does second while loop do i.e inside bs.

Can anyone explain that why in this solution https://codeforces.com/contest/1282/submission/67533137 they use midb and the for loop for midb, with using only mid as in normal binary search answer fail on first case on test case 7.. Pls explain why midb is necessary.

For binary search, your function needs to be monotonic, and this is not the case when you just use the "mid" approach. In the seventh case, note that it costs 7 to get three things, but 3 to get four.

This is caused by being forced to buy mid%k items individually. The "midb" approach compensates for this by "rounding up" and checking the answer for the next multiple of k. This works because the cost for all values between mid and midb is greater than or equal to the cost of mid and the cost of all values larger than midb is greater than or equal to the cost of midb (proof left as an exercise).

How would the solution for D be affected if the strings were not binary? Let's say you had 26*(n+2) queries. Would the same technique work? If not, what would change?

Any similar problem like B?

How this test case in 1282C - Petya and Exam is getting the answer as 1. Shouldn't it be 0?

You can solve any of the easy problems and leave the exam at t = 2, which nets you one point.

Thanks, I got it.

No At time t = 2 he can leave the exam after solving 1 easy problem.

WA because of integer overflow hurts again

In Problem C, second Testcase, the 12th test is

Since mandantory times are 2 and 0, and a==3 I would expect the answer to be 0, no problem can be solved in time, since the first solved problem is at t==3, that is after 0 (and 2).

But grader says answer is 2, so both problems should be solvable in time.

What did I get wrong, can somebody explain? submisson

It is not necessary to start solving problem before it's mandatory time.

Ahhh, I understand. There is no need to solve the problems until mandatory time. Only, if one finishes after mandatory time, that problems must have been solved.

Funny, that the whole first test and the 11 ones before the 12th work correct, even after getting the problem so wrong.

Because T = 13, you can solve the two problems and leave at t = 6 (which is < T).

Mandatory doesn't mean it has to be solved before that time, it means that if you don't leave

beforeit becomes mandatory, then you cannot leaveuntilyou solve it (it doesn't matter when you solve it but you have to solve it before leaving), but you still have to do that before you run out of time (t=T).Ok, got it, thanks.

This was one of the worst rounds I've done. I hope none of real coordinators would allow problems ABE in the contest. D was nice, but forbidding to ask queries longer than maximal string is a bit silly. Still, having one nice problem is not enough to make a round out of it. I like when new people are starting in problemsetting, but next time ask for an actual coordinator who is willing to say that your problems are bad.

Just out of curiosity, what was bad in A and B other than the long problem statement?

None of these problems are fresh in any sense.

Cool, makes sense. The problem ideas may seem old especially given your level of experience.

Still according to me both A and B were good problems for beginners.

The first time that I see Nutella's comments are downvoted!

U haven't seen many comments of Um_nik

I would agree on A (probably, suits Div.3 better). B seemed okay, but maybe too complicated statement for little thinking effort. E was nice although seemed too easy for the last problem. But in the end the contest seems to be well-balanced, maybe one more hard problem was missing.

Nah, nice contest :D

E was really nice

I think he forgot to look at... It was Div2 not Div1.

What is the reason for having an upper bound on the size of string query you can ask?

Do stop people from bruteforcing everything.

I'm guessing it's mainly for hacks. It's easy to forget the condition and print a 301 length string

i solved E with topological sort . Is there any other way (for finding the vertices permutation)

Not sure if we can call it topological sort. It's just a simple circular cycle which isn't even directed. Maybe calling it a dfs is enough.

Guess i made it over complicated for me then

can you explain how to use dfs to solve this problem ?

There was a bit of preparation needed before doing the dfs which was the crux of the problem, dfs was simple once you get the idea that —

My code: https://codeforces.com/contest/1282/submission/67581486

thanks.can you explain that idea which led to dfs as solution.I mean can you elaborate a little more.

The main idea was -

How to find those shared edges?

`map[edge_a_b]++`

. Whichever edge has count 2 are the ones where knife went.I got what you are saying .Thanks

I solved it like this: the last piece to be cut must contain a vertex which only appears once. So, find such a piece (let's call it [t,a,b], where t only appears once), remove it, solve recursively for the remaining pieces, then in the linked list obtained by solving recursively, replace edge (a,b) with edges (a,t) and (t,b).

Can some one help me find the mistake in my submission 67570438 for Problem D.

When you think your approach is wrong but after contest you realize it is just -1 which gives causes WA, it hurts.

Master as christmas present!

Hello everyone,

I have tried to make video solution for the first four problems of Codeforces Round 610 Div. 2, hoping to help people understand the problem and what was my approach for the same. Please do like the video and do subscribe for more such content.

Video playlist: Codeforces 610 Div2 Video Solutions Playlist

Separate links are as follows: A B1 B2 C

Happy Coding

Divyanshu Kumar

Using google translate for the editorial makes it super hard to understand :(

VERY VERY GOOD CONTEST

In problem B2, for the following test, why should the output be 1 and not 2?

1

5 2 3

10 1 3 9 2

I am sure I am missing out something trivial. Please help me out.

Can someone help me with my submission for C problem.Getting WA in test2 445 number

My approach is to first find time

`lastgreat<=t`

where it is possible to solve all mandatory problems and then in`timeremaining = lastgreat-a*(number of mandatory easy problems upto lastgreat)-b*(number of mandatory hard problems upto lastgreat)`

. I will add easy problems and hard problems if its possible that remain during the`time`

interval where`t>=time>lastgreat`