Hi Codeforces!

We are glad to invite you to our first Codeforces Round Codeforces Round 551 (Div. 2) which will be held on Apr/13/2019 17:05 (Moscow time). This round will be rated for participants with rating less than 2100. We will be glad to see participants from the first division to join out of competition as well!

In this round, as the best friend of Serval's, you are going to help him to solve the problems he meets.

The problems are prepared by bzh and me. We hope you will enjoy the round. :P

Great thanks to 300iq for coordination of this round, isaf27, vintage_Vlad_Makeev, KAN, mohammedehab2002, Learner99, Aleks5d and Um_nik for testing our rounds, and MikeMirzayanov for the amazing Codeforces and Polygon platforms.

You will be given 6 problems to solve in 2 hours. Scoring distribution will be announced later.

Please pay attention that there will be an interactive problem in this round, so learn more about interactive problems here before the contest.

Good luck & Have fun! :D

**UPD:** Scoring distribution is: 500-1000-1500-1750-2250-2750.

**UPD2:** Thank you for your participation in this round! Congratulations to the winners!

**Div. 2**

- ihdignite
- KassiJulgus
- mmmod_Iqs
- kidddddddddddddddddddddd
- xianhaoming
- __Ressed__
- nikolapesic2802
- xiaowuc1
- ei133333
- Kho0007

**Div. 1 + Div. 2**

**UPD3:** Sorry for the delay. The editorial is available.

I wish after this I wouldn’t be able to participate in Div2

Me too！Fighting for the last 30 points!

Congrats!

So why U dont participate?

I missed it when I got home it was already started and an hour was passed

Another Chinese Round is coming!

But the time is not friendly...

We wanted to hold it earlier but the time was conflicted with Atcoder Beginner Contest. :)

Maybe earlier than Atcoder Beginner Contest?

That's toooo early. If so, this round should be started before 18:00 UTC+8. :(

Cool Now I know I can't solve interactive one xD

Thanks for posting the link to the explanation of interactive problems! Before this I didn't even know what interactive problems are. Learnt a lot :)

Wish to be able to participate in Div1 after this contest.

So why U dont participate?

Well, I really want to participate, but I had something others must be done. QAQ

I wish I'll be able to attend Div.1 after this concert. :)

*contest

Contest once in a week!

Too much pain in one line.

Got -60 twice in div3, will try this one

I got -49 and -41 in two Div.3 rounds when I was a Pupil. Hope you can get rating increasing in Div.2 rounds :)

[deleted] sorry if this annoy somebody :(

ouuan You've improved faster man as per your ratings graph!

i hope get some points in this contest!

Chinese Round, interesting.

hope to be expert this round

Each time I try to submit, it says you should be registered for this contest when I registered 2 minutes before the start of the round. What is happening? Please help someone.

As I know, you can't register in 2 minutes before the round starts, because registration cancels in 5 minutes before, so you may got a bug with a CF and you somehow registered (but no).

In the problem statement, mistakenly I read 'Serval' as 'Several', several times.

I heard of that some contestant(my friends) got

"You have submitted exactly the same code before"when They submit their code of problem A. Can anyone tell me what happened?You get this message iff you make the exact same submission without any code change. This actually prevents making the same submission twice (making the submit button idempotent).

It might be the case that your friend either made the same submission again or it just happened due to some network issue. In either case, at least once the submission should have been submitted.

Maybe it’s because of the network issue.

But the strange thing is that he said that was the first submission in that contest and There’re nothing in

My Submission.I've met the same thing before..

Was Codeforces down for everybody for the period of around thirty minutes or was that just me?

It was working for me. so mostly only you or maybe I did not do any submit in that 30 min mark to even notice it. But if it happened people would complain here I guess

Every other website was working, so I doubt it's me. People probably will be complaining after the round =)

I've seen connection timeout errors for a few weeks. It appears sometimes even when there aren't any contests on codeforces. Did you try to refresh the page several times? It helps me

I've tried refreshing for a few times, only helped after ~30mins

I was using and refreshing Codeforces constantly (to see friend's standings). Didn't even go down once for me.

It was down for me also

During last few seconds, I was not able to submit. But not for 30 minutes for sure.

What approach can be taken to solve Problem D?

Store, for each vertices cnt[v] = number of leaves in subtree rooted at v, and dp[v] = maximum number v can get, if leaves in its subtree are assigned numbers from 1 to cnt[v].

Transitions can be derived by considering relative order.

What do you mean by

relative order? I used a similar dp state, but cannot get it right. Thanks in advance.binary search on the value, for a given x, all values >= x will become 1, otherwise 0. then do a normal dfs to find the minimum needed 1s and if it's less that the 1s you have, then it's true, otherwise false.

For each vertex find number d such that we need d numbers >= x to get value x in this vertex. For leaves it's 1, for min it's sum of this value in children, for max it's min of this value in children. Now answer is number of leaves — this value in root.

What is x?

Arbitrary number — d is the same for any x.

How to solve D?

It's a dp problem on tree. You can see my submission later 52702102

Is Problme F about integrating the formula for each possible $$$k$$$?

Tried to find some "smart observation" all the time and didn't get it...

write the formulas open the formulas and integrate it. no very good observations pure math

can you please explain your solution in detail?

This is how I solved this problem. I couldn't submit it but since all the test cases matched, I'm sure that I am right. Also, this solution may be circuitous. First, we can assume that the length of initial segment is $$$1$$$, and multiply the calculated answer by $$$l$$$ afterwards. Now, instead of choosing arbitrary $$$2n$$$ endpoints of segments, let's randomly chose them from a set consisting of $$$m$$$ points, which is $$$\displaystyle {0, \frac 1{m-1}, \frac 2{m-1}, \cdots, 1}$$$. Then, let $$$p_i$$$ be the probability that the segment $$$\displaystyle s_i = \left[\frac{i-1}{m-1}, \frac{i}{m-1}\right]$$$ is covered by one subsegment. Then the probability that segment $$$s_i$$$ is covered with more than $$$k$$$ segment is \begin{eqnarray} \sum_{j=k}^n {}_n C_j \cdot p_i^j (1-p_i)^{n-j}, \end{eqnarray} and each $$$p_i$$$ can be calculated by \begin{eqnarray} p_i = 2 \frac im \left(1-\frac im \right), \end{eqnarray} so the expected "expected value" for this situation can be calculated by \begin{eqnarray} \sum_{i=1}^{m-1} \frac 1{m-1} \sum_{j=k}^n {}_n C_j \cdot \left( 2 \frac im \left(1-\frac im \right) \right)^j \left(1-\left( 2 \frac im \left(1-\frac im \right) \right)\right)^{n-j}. \end{eqnarray}

Whew, it's hard work to write mathematical equation on the PC. I'll write the rest after I take some rest.

Now, supposing that $$$m$$$ is infinite, the last equation can be calculated as follows. (Here, we apply the well-known fact that $$$\displaystyle \lim_{n\to\infty} \frac 1n \sum_{i=1}^{n} f\left(\frac in\right) = \int_0^1 f(x) dx$$$, but I don't know how this fact is called in English... somebody tell me) \begin{eqnarray} \lim_{m\to\infty} \sum_{i=1}^{m-1} \frac 1{m-1} \sum_{j=k}^n {}_n C_j \cdot \left( 2 \frac im \left(1-\frac im \right) \right)^j \left(1-2 \frac im \left(1-\frac im \right)\right)^{n-j} \end{eqnarray} \begin{eqnarray} = \sum_{j=k}^n {}_n C_j \int_0^1 (2x(1-x))^j (1-2x(1-x))^{n-j} dx \end{eqnarray} \begin{eqnarray} = \sum_{j=k}^n {}_n C_j \int_0^1 (2x(1-x))^j\sum_{l=0}^{n-j} {}_{n-j}C_l (-2x(1-x))^l dx \end{eqnarray} \begin{eqnarray} = \sum_{j=k}^n {}_n C_j \sum_{l=0}^{n-j} {}_{n-j}C_l (-1)^l 2^{j+l} \int_0^1 x^{j+l} (1-x)^{j+l} dx \end{eqnarray}

The last integral is Beta function, and the value is $$$\displaystyle \frac{(j+l)!(j+l)!}{((j+l)+(j+l)+1)!}$$$. Now we can calculate the answer by $$$O(n^2)$$$, which is enough for $$$n \leq 2000$$$.

thenewguy39

I think it is called limit as a sum

Riemann sum. From wikipedia))

The solution of F is DP. Editorial will be out later. :)

Wow. I am looking forward to it.

Makes me wonder, what was that pretest 3 of E?

I think I've come up with a right approach, yet not sure if I made any mistakes :D

Same here probably not couting some flush or idk...

sorry

Hmm I'm talking of E, not C. ;)

I figured my issues and got AC. My submission: 52716310.

(For reference, my WA3 solution: 52711736)

However, I still think Codeforces judge system worked a bit weird.

If my implementation was correct (hopefully I didn't misread anything), any time I read value

`-1`

my code would terminate immediately with a non-zero return code, therefore force-runtime-error my solution. Yet in this case (well too bad I use only 1 exceeded query :"> ), guess the interactor stopped and sent the verdict to the checker immediately before I had my chance to force-RE. :DWeird, but I won't blame anyone. Today I learned. :">

Thanks Codeforces and the setter team for the round. ;)

Amazing round!

Problems were very cool!

What a beautiful contest! thanks for this interesting round and looking forward to your next rounds.

Enjoyed the round, especially D. Time to upvote contest announcement. :P

Can anyone explain their approach for F?

how to solve C ?

try to make '(' from left and ')' from right ....

Firstly odd strings will never work. Secondly you will always need same number of ( and ) in the final string. Thirdly you want to change ? to ( in the beginning of the string and ? to ) in the last part of the string.

Then just do the usual stack code to check if the parenthesis are balanced.

Code

For C my logic was to continuosly maintain (number of opening brackets-number of closing brackets)=1 while traversing till the second last element. I can't understand where it went wrong?

If you have something like (??))), we need to replace the second ? with ( and get balance of 3 instead of 1, or we will not be able to form correct sequence.

Any idea about test case 6 of C?

it's probably something like this

10

(?)?)??(?) which should print (()()()())

found that bug in my solution but hadn't enough time to fix it

maybe 6 ???)??

answer should be ((()))

Oh, nooo! There were 10 seconds left, I tried to submit my solution for E(pressed the "submit" button)

Thisbut the website was slow and just showed "502 Bad Gateway".

Same, I tried hacking but cf was too slow at the end :(

Similar thing happened to me too, but while loading (and eventually getting 502 bad gateway error) there was a notification to browser that said pretests passed

D and E were interesting problems with the ideal difficulty for div 2 contests, hats off to round writers.

It seems that I will never be able to solve an interacive problem :(

How to solve E and F?

Hint for E: Answer for the query == 1 (mod) 2 iff exactly one of ends of snake lies in asked rectangle.

Thanks, but actually, I’ve thought about it before, and I still couldn’t solve it.

upd: Hey, I think I got it. Thanks!

I think D problem is an easy version of this problem 538E. (Used the same solution and passed)

I feel sorry about it but we havn't seen this problem before this comment. :(

Trying to submit the solution is the last 10 seconds, but the submit page didn't load :(

For problem C why my logic will fail?

https://codeforces.com/contest/1153/submission/52703030

EDIT: Above submission is just for explaining my logic

This is my final solution https://codeforces.com/contest/1153/submission/52709706

Here i am checking the string by reversing also.

Even I was doing the same mistake for almost an hour :(

Then suddenly striked a test case

6 ((?)))

Your Output: :( Correct Output: ((()))

I also got the test case.So i also checked by reversing the string. I just put this solution link to explain my logic, in my another submission i checked from both the sides so it should pass.

Try this

8 (??)(??)

Got it thanks

You use a greedy way for parenthesis completion, which fails to form a valid solution in several cases. Try:

8 (????)))

Similarly, when the input is like this,

6???)??after executing your code the string s is

(())??, and according to Line 40(the third of the fivecout<<":(";), print:(, and end. But the correct answer is((())).Isn't

`:(`

correct for`6 (())??`

since`(())`

is a valid bracket sequence prefix?I meant when the input is 6 ???)??, the only correct answer is ((())), but when executing

hiscode, print :(, because the string becomes (())??.I finally solved the very last problem and all the test cases showed right answer. Feeling full of confidence and delight, I opened the submission page, only to find that contest was over five minutes ago... :(

I'm pretty sure I'm gonna WA on E because there is one case where I use 2020 queries instead of 2019. Feels bad.

I felt same, but I got AC.

got WA on pretest 4 on problem A 4 times and raged

skipping problems

finally found out B is simple

solved B at about 01:31

found dumb mistakes of A and got AC

found dumb mistakes of C and got AC

me:rage

(when you participate on time but got the first AC at 01:31)

Can anybody explain how to solve E? if the shake have only the head and the tail and the field consist from 1 million cells, how is it possible to find them having made only 2019 queries?

A bit intuitively, but we can see a few things:

Our solution will be divided into two phases:

Phase 1:Find the columns/rows with the snake's end.Assume that the snake's head and tail stays at different rows, let's denote them as $$$xa$$$ and $$$xb$$$ (since we don't really care about the order of the head and tail, assume that $$$xa < xb$$$). Thus we'll see that: - $$$xa$$$ is the lowest row index $$$x$$$ such as query

`? 1 1 x n`

returns an odd value. - $$$xb$$$ is the lowest row index $$$x$$$ higher than $$$xa$$$ such as query`? 1 1 x n`

returns an even value.If searching for the rows didn't do, we repeat the similar process with the columns.

In theory, this phase takes up $$$2000$$$ queries, but we can shrink it to $$$1998$$$, knowing that querying with the last row/column always results in $$$0$$$.

Phase 2:Find the exact cell in each row/column.This part has a binary search concept.

Assume that we're working with rectangle

`x ya x yb`

(if the rectangle has the form of`xa y xb y`

, we can do similar things).Assume $$$ym = \lfloor \frac{ya+yb}{2} \rfloor$$$. We'll query the rectangle

`x ya x ym`

. If the returning value is odd, continue the binary search with that rectangle, otherwise continue with the rectangle`x (ym+1) x yb`

if such rectangle exists.Repeat the search until the rectangle consists of only one cell. That would be the head/tail we need.

Each binary search process consumes at maximum $$$\lceil \log2(1000) \rceil$$$ queries, or $$$10$$$ queries.

We have two rows/columns to deal with, so the second phase will use up to $$$10 \cdot 2 = 20$$$ queries.

In summary, the process (at its most optimal form) will use $$$2018$$$ queries at most. Pretty close. :D

My solution, for reference: 52716310

Thanks. Very good explanation))

You can also search for single column/rows to find it.

If the result of a query is odd, then exactly one snake end must be in the rectangle.

Query all rows. If both ends are in different rows, we obtain two queries with an odd result and can binary search the cell in both rows.

If all rows return an even result, this means that both ends must be in the same row, therefore both ends can not be in the same column. Query all columns to get the columns of both ends. Then, for the first column binary search one snake end. As both snake ends are in the same row, we are done.

As binary search takes at most 10 queries for $$$n\leq 1000$$$, we have that in the first case we use at most $$$1000 + 2\cdot 10\leq 2019$$$ queries. In the second case, we use at most $$$2\cdot 1000 + 10\leq 2019$$$ queries.

I did not get the case where the ends are in the same row.

Let's say that I know that one of the heads is in Col x and other in Col (x + 1) and both are in the same row. How do I find which row from there?

Got it now, that in the first row iteration, a even number(zero in the above case) meant that the heads might or might not be inside.

But now as I at least have one crossover, an even number(zero in the above case) will definitely mean that the heads are not inside.

Can somebody elaborate how to do D? I can't can't seem to make formula for each dfs.

My approach using some observe:

try it!

https://codeforces.com/contest/1153/submission/52707952

(I traverse with bottom up)

"Ignore all small number"? I don't understand meaning of it. What is "small" and what is "number". Same with minimum, why "sum" and why "number".

Well, I solved D like this:

See https://codeforces.com/contest/1153/submission/52713093 for details.

I understand the code, and see that it works. But I still have no idea why it works. Why use min and/or sum in the two cases, and why is the answer = num_leaves — dp[root]+1 ?

What does dp[node] denote?

Hi phyzzmat , Can you please explain all these 3 steps ? why are you doing so ?

I wish after next contest i will become a master.

Hey teja349 can you explain your code of C ?

I used the same approach.

It's based on the observation that we should give priority to put open brackets first in the sequence. So we just count in the first iteration that how many open brackets we can put more in the string (Remember you cannot put more than n/2 open brackets).

In the next iteration whenever we get a '?' we put open brackets until we have exhausted them all and then put all the closed ones. At each point we check that the balance should not be less than or equal to 0 except at the end of the string where it should be exactly zero.

Why this works? Because in any valid sequence you can always replace a closing bracket with a later open bracket.

Why did you not specify in Problem E whether (1,1) is the top-left or bottom-left or etc.? How do I know that whether you treat as coordinate system or like a matrix?

We feel sorry about forgetting to explain it, but I wish you can get it from the first sample and its illustrations. :)

The problem statement should be complete! The samples are for further explanations, not to complement the problem statement. I didn't look at the samples during the contest. You named cells as (x1, y1) which implies coordinate system.

But how does that make a difference? The grid is square.

I don't have to prove to myself in that rush that it's symmetric and it makes no difference etc. The problem statement should be clear and complete! I'm quite surprised that you guys can't understand this and look for fault in me, but not in the incomplete statement.

Moreover, author himself says "sorry for forgetting that ...", you don't have to act like smart.

`I don't have to prove to myself in that rush that it's symmetric and it makes no difference etc. The problem statement should be clear and complete!`

What? First, you don't look at the samples, now you don't have to make observations about the problem? Less than that even, you claim you're in too much of a rush to realise that a square is symmetric? You might want to reassess how you spend your time then. You could've asked for a clarification mid-contest, that's what it's there for. Or you could've thought about it for yourself. Instead, you decide to blame the author for your own incompetence. The statement isn't incomplete. There is more than enough information to solve the problem, enough for 213 solves in a div2E.

`Moreover, author himself says "sorry for forgetting that ..."`

Yes, the author apologised, because they recognised an area where they could do better. Maybe you should do the same.

What you fail to understand is that no matter how many people solved that problem (maybe all), or whether I look at the samples or not, the problem statement should be clear and complete! If you think the other way, then it's your problem! I appreciated author's apologies and finding room for improvement but not your advocacy for someone's faults.

Nice contest with a good problem difficulty distribution. I really enjoyed it.

Kudos to the writers !!! A balanced round with gradually increasing difficulty in problems.

Really liked it !!!

can anyone tell what fails test case 6 in problem C https://codeforces.com/contest/1153/submission/52718031

Hello, can somebody help me with the interactive problem? My code gets WA 8, telling me that my program asks more than 2019 queries, however I checked multiple times and my program takes either 2*n + 1, 2*n + 9 or 2*n + 18 queries (my binary search throws at most 9 queries each time, although its impossible even those 9. I just don't see how my program could ask more that 2019 queries

52719905

I think that your binary search may take 10 queries. Note that if you start with i = 2^9 it'll be divided 10 times until it reaches 0

It will be divided 10 times, but whats inside the for will be called at most 9 times, since the 10th division will give i = 0 and the for will quit.

Nice round!! Can't wait to see the editorial

Serval is winning ACM ICPC in the future.

Can Someone Share their Approach for Solving E. Thank You.

Cool, I found one above .

Nice problems. And especially cool samples illustrations.

I am stuck on the problem C , I am getting WA on tc-6 , however I have checked all the test-cases given in the comment section and my code passes on all of them. I have used a greedy logic where the first opening brackets should be closed by the last bracket to ensure no prefix is a valid bracket sequence, now for the remaining brackets I am maintaining a cnt if there is a ? then if cnt > 0 replace it with ")" else replace it with "(" if at any time the cnt < 0 then I try to change ")" to "(" to increase count. Please anyone help me , what is the error I am not able to get it, after spending hours on the question Submission link

You need to iterate the string "from both sides", or twice. First time counting the opening, and closing brackets. Second time replacing the question-marks. Replace them by open brackets from the left, and closing ondes from the right, make sure number of open and close is same. Check if the resulting string is correct. If yes, then all prefixes of it are not correct.

you can iterate the string from left to right and replace "?" with "(" as many as you can,you can see that other position must be replace with ")".when you replace all "?" with "(" or ")",just check the string to ensure that the string is correct and any prefixes is not correct.hope that can help you and sorry my English is poor,hope you can understand...

Hello! Can anyone help me with last problem F?) Will the analysis be posted?

Japari is here.jpg

wish i can be "expert" in next context :)

Really nice contest, thanks for the problems!

It's a great Chinese round I think.

Problem A

why

`min{ ((a-t)%b+b)%b }`

is wrong?If I understand your formula correctly, $$$a$$$ is the time of first bus arrival and $$$b$$$ is the period of buses arriving.

You calculate answer as minimum of some values by modulo of each $$$b$$$, so answer will never exceed $$$min(b)$$$. Consider test cases like this: $$$n = 1, t = 1, a_1 = 1234, b_1 = 1$$$. There will be no buses until $$$1234$$$ time moment but your solution will give $$$0$$$ as answer.

Is it possible that the guy at first place had his tasks done by someone else ? Is it allowed on Codeforces?

It's not allowed, but I did everything on my own so don't worry.

Please upload the editorial for problem D.

That's already published: D