I would like to invite you to participate in the rated Codeforces Round #518. Date and time of the round: Wednesday, October 24, 2018 at 18:05. The round was postponed from October 23 to October 24 because of the ICPC Indian Online Qualifier.

This is the first competition I proposed. I hope you will enjoy it.

The round will have 6 tasks for the second division and 5 tasks for first (3 problems are common). The contest will last for 2 hours.

Tasks for you were prepared by Alexey kristevalex Kristev and Alexey Um_nik Danilyuk. Also thanks for:

Nikolay KAN Kalinin and Ildar 300iq Gainullin for help in preparing the problems; Ivan isaf27 Safonov и Oleg Merkurev Merkurev for testing the round; Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon platforms.

I would like to express a special gratitude to Um_nik for the help throughout the process of preparing the round and also for patience for my stupid questions.

**slight lyrical digression**

This round is a thanks-round for support from Mail.Ru during the 8-year campaign!

Scoring distribution will be announced later. I wish you a high rating and looking forward to see you at the competition!

I'll be on the community Discord server shortly after the contest to discuss the problems.

UPD: scoring distribution div1: 500 1000 1750 2250 2500 div2: 500 1250 1500 2250 2750 3500

UPD2: edtorial.

Codeforces is the best platform :) We are proud to work together!

I've noticed that 300iq is still unchanged to his real form. The legend will be mad.

If Um_nik didn't told you to stop creating problems, then I guess it will be a great round.

SpoilerNice joke, don't know why it is not heavily upvoted.

Participate and find out for yourself :)

I think that kristevalex really is a talented problemsetter. Of course he need more experience both in preparing and solving problems but his ideas are sometimes brilliant. Or maybe that was one time and will never happen again. Who knows.

Dude that doesn't even have anything to do with this round's setter, seems your so salty have to put your issues on random blogposts ._.

First Member of the Codeforces Triumvirate (circa 2018 AD).

Second Member of the Codeforces Triumvirate (circa 2018 AD).

.

Third Member of the Codeforces Triumvirate (circa 2018 AD).

Is it rated?

...

6 consecutive hidden comments, ridiculous.

UPD: 7 comments.Good luck, guys. Proud that you are members of best Programming Forum in CIS

FST forces!

The time page gives 404 error, please fix it.

hhey is it rated or i dont partisipate

Yes, as it written in announcment: 'rated Codeforces Round #518'.

very thancks u

codeforse members mad]=));;;]]]

Why so many downvotes?

even who's downvoting doesn't know why

after yesterday's shit contest indians are frustrated >:( xD

I don't mind my comment to be harmonious with the others (since it doesn't mean that I was wrong to comment).

The time link still gives 404 Error.

I can know when the contest will begin from the timer of Codeforces, but I want to be sure, because the difference between our country's time and previous blogs' time was zero, and now it is one hour and a half.

It starts 16:35 UTC

Thank you very much :D

Seriously, another problem with a bad statement, time to leave.

Totally agree you cannot use a word to define it's self "Let's call the set of rooks ... with rooks from this set" , it like saying a ball is a round-shaped ball, it doesn't make sense.

While I agree that the line (and problem statement as a whole) could have been phrased better, I'd also like to point out that what is being defined here is 'connected', so using 'set of rooks' in the definition isn't leading to circular definitions.

Yeah, I kept on staring this line without any clue for quite some time. Glad that I was not the only one.

Am I the only one who found problem statement of Div.2 A to be tremendously hard to understand?

can anyone please tell the solution for div 2 A

Notice that minimal answer multiplied by M need to have L+K coins. So ans*M=L+K, or ans=(L+K)/M. It can happen that (L+K)%M!=0 and in that case you need to increment ans by 1, or otherwise ans*M will have less than L+K coins. Lastly, if ans*M exceeds N, then answer is impossible (-1), otherwise output ans.

That is what i did but it didnt pass pretest 7:( This is clean. Please see to it http://codeforces.com/contest/1068/submission/44810290

I performed another check. If ans*M > n or L < N-K, the answer is -1.

Kept getting WA.

I think C had good problem statement. Maybe you didn't read it carefully, I don't know.. Maybe I'm one of the lucky ones.

You're not alone, I got pretests cleared after 3 WAs and I'm still not sure I understood it correctly.

This contest is plain garbage.

Contest was really nice. If you found contest easy try D,E,F, if tough then A,B were really easy. I liked 2A. In 2B, we just have to count the number of divisors of b.

nice contest

Excellent explanation. https://www.imageupload.co.uk/image/TAkQ

Problem A Div.1 Sample is useless.

after weak pretest, weak systest, we have weak sample now XD

just joking )

Hack for D1B?

I hacked 1 solution with:

Maybe some solutions could get hacked by changing k from 2 to 3.

what is the answer?

edit: the answer is NO for both k = 2 and k = 3

GreenGrape, your rounds are perfect

oh i feel bad...

E: link. Nice problem!

I used the same :D

So, how to solve it based on this fact? My thought was like consider every edge separately, use something like tree dynamic programming to compute the probability for it to be the matching edge. But I'm not quite sure if this would work.

There is a greedy algorithm to find maximum matching in a tree. So, I have DP[n][2] — vertex and "Would this vertex be already matched in greedy algorithm?". When I consider some unmatched vertex with its unmatched child — I must match them (like I would do in greedy algorithm). Each DP[v][i] is a pair of integers — how many subsets of edges in this subtree would lead to this state and what is the sum of results in these situations.

Aha!Got it,thx. Just a slightly change of the algorithm of finding the maximum matching in a tree.

You can use standard dp.

dp_{v, 0}is max matching in subtree if we didn't takev,dp_{v, 1}is max matching if we tookv. Every time we connectvanduwhich were not taken, we should add edge (v,u) to matching.Tree DP is right. Count the number of max. matchings and the sum of their sizes, where the top of a subtree can be unmatched / has to be matched. When processing a vertex's sons, you can use an intermediate state "has this vertex been matched with some son?". There are some annoying long formulas, but that's basically it.

I alone do not understand this part of the condition of problem C: "Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set. Assume that rooks can jump over other rooks, in other words a rook can go to any cell which shares vertical and to any cell which shares horizontal."? After all, this means that the rook can make a move only in the next cell, where there is another rook (which does not correspond to test 1). Or how then to understand it?

Thought I had something for C, but I guess I was wrong! Kept getting WA pretest 3. Anyone want to share solution?

How to solve A?

i change long long to double long and i get ac

My solution is dp[i][number on position i][is a[i — 1] >= a[i]], to calculate it use prefix sums.

I think for Div2C, you have to construct a zig-zag like pattern. Messed up my implementation though!

let

dp_{i, j, 0 / 1}denote for the firstielements, with the last valuej, and the last dimension stands for is it needed that the next element is greater than/equal to the last element. Naively doing it would result inO(200^{2}×n), With prefix sum optimization, it can be reduced toO(200 ×n).nice , i think we can do it without the third state.

Div1A/Div2D is DP[10^5][200][2] , but I can't implement it ).

Same here

Div2A statement is bad :(

Very bad.

Very Very bad.

extremely bad

When Um_nik criticize misof for TCO and then, interestingly, leads a contest which consists of extremely bad statements... Just saying...

Really activates my almonds.

hahaha what does that even

wait wtf is a homemade coconut? I never knew food science was advanced enough that we were doing this

lmao dude have you even used a crafting table before?

I see what you did there. You are trying to paint me as a man of no culture (because I don't play minecraft)

Unfortunately, I'm always munching on cultured vegetables. Goes well with my alkalized water.

Can you really talk about culture when you aren't drinking 1000 liters of milk in 3 gulps though

Dairy is bad. Instead I drink coconut kefir (from my own lab grown coconut) with some activated almonds

Pete Evans describes "activating almonds" as putting them in water for 12 hours.

I guess normal almonds haven't even achieved their final form

I'd say "extremely bad" are a kind words for it.

90% of questions we get were caused by participants not able to read statements and understand basic mathematical constructions.

Instead, it would be better for a legend to reconsider his self-esteem.

It would be good, but not instead. I can't really do anything about people who either don't know mathematical notation or don't spend time reading statements.

Um_nik Hope you already know that, reading statements and understanding them are not same. And I think it's not you who will decide whether the statements were good or bad to understand. It's us, the contestants will do.

Do you think contestants complain about problems in every contest? No. If something really went wrong, they complain about it.

And only then you should say "I can't really do anything", when you know people hates you, so they started complaining about problems.

Problem A had poor statement as well as weak pretests. :(

Yeahh, right, maybe not able to guess what you hid in there. GUESSINGFORCES it was, how you like it ??

No matter the quality of problems, I agree with Um_nik that there are so many stupid questions asked. It happens every contest, even if people don't complain later in the comments.

but was that round rated?

How to solve div2E?

I didn't solve it, but here is my idea

Cut all the vertexes with degree 1, repeat it until one is left : the root Then simply check if all vertex's child degree is not less than 3

*Is it right?

This is what passed pretests for me:

A

k-hedgehog has ≥ 3^{k}leaves. Sincen≤ 10^{5}this boundskby 11 or so.Now, perform

ksteps. At each step, remove all leaves from the graph, and decrease the degree of their parent by 1. Make sure that any non-leaf node either sees no change in degree, or their degree changes by >= 3. After this, update the graph so that you get a new set of leaf nodes, and do this again. Afterksteps, you should be left with exactly 1 node at the end. Any other case is a "No".Div1C solution is just a cross:

After contest, I solved it after drawing some examples on paper and noticing the symmetry the hedgehog type of tree has, which turned out to be solution 2 from editorial.

My solution:

The natural solution I saw to the problem was to identify the "center" of the tree (which, must exist if it is a hedgehog) and then, from there do DFS/BFS to check if the given tree satisfies the properties given in the statement. The problem is, we need to identify the center quickly. How do we do that? If the tree is a hedgehog, every longest path

mustpass through the center node, which is number k, zero indexed (one can notice this by carefully reading how the hedgehog type of tree is created). So we find a longest path, and check if the length of it is > k. If it is not, then it is not a hedgehog. Else, we take the center node of the path and run BFS/DFS to check the properties, which are:If all these are satisfied, we print "Yes", else, the given tree is not a hedgehog.

Does having two rows of white squares (0, 0), (2, 0), (4, 0), etc and then (0, 3), (2, 3), (4, 3), etc work???

Shit. I just found an asymptotically sufficient assignment for div1C:

Also, Um_nik, if div1E reduces to div1A-B after an easy to find observation, it shouldn't be in an online contest!

Easy to find you mean online? I didn't succeed, but I'm not good at googling. I'm sorry for that, you are right about problem being only about this observation.

"adjacency matrix" rank tree: gives SE as the second link, the first answer mentions something 2x size of matching

"adjacency matrix" rank tree matching: gives the answer for a tree directly, generalising this to a forest is easy

Not completely easy to find, but easy enough.

My story: I looked at the scoreboard immediately after submitting B, saw that someone solved it already and decided to work with the assumption that the solution is online. I read the statement, decided that if something is online, then it's the rank of an adjacency matrix, found something (including the first link), read the statement again and realised — I missed that the input is a tree, made the two queries, mentally checked that the first sample fits, so I haven't found something irrelevant, and started thinking about a solution.

The descriptions were not clear at least for me. Didn't like this contest.. AWFUL

Deleted

How did you generalise that? It's just 1 row + 2 knights.

problem C statement was really bad .. ofcourse so many solved it but you should consider not everyone has shakespear english level and give the beginners who hasn't read alot alot of problems a chance to solve it

I was going to try it but i was like if i need so much time to understand it then when I'm going to think how to solve it

Not your fault. I've read Shakespeare in school, it was easier than C.

Any idea why this submission would get WA on test 3 while this one passes pretests?

Edit: found the mistake.

Being in #1 for almost all the time, then got punished by a hack on 2A :D At that moment, I realised the statements were

bad enoughfor me to deny reading them in the 10 last minutes :DBtw, anyone can provide me a hack for 2A? :D

Could be overflow, numbers go up to 10^18

Not with mine. My solution consists of at most 1 addition, and no multiplication, the other operations possible were division only...

My hacked solution: 44781223 (not sure if accessible now)

10 6 3 4

many programmers checked only if m>n or (l+k)>n, then print -1 else printed ans=(l+k)/m + bool((l+k)%m), they never checked if ans*m is exceeding n or not and hence got hacked.

Figured. Thanks! :D

Both statement and pretest for Problem A were too poor. I will also fail system test! :(

Pretest 3 of div1A?

I don’t know what is test 3.

But you can try this one.

3

-1 -1 -1

Answer should be 40000

Thanks, my solution does work for that test though :(

Is kiwikiwi going to have a bad rating change for first time?

maybe he wants to show something after dotorya,

thisblog.How to solve Div2.C ? I'm really confused by the statement, thus cant solve it ://

Same here, examples didn't make sense for me.

for every edge x1-x2 put rook of color x1 to (x1, y) and of color x2 to (x2, y). make 'y' value unique for every edge and check condition that all colors should be on chessboard

There could be n * (n — 1) / 2 edges, which is 100 * 99 / 2 = 4950 for 100 colors. Your solutions places 2 rooks for every edge, resulting in 9900 rooks on the board. This is a violation of: "Total number of rooks must not exceed 5000."

There is accepted solutions with this algorithm. Could anyone please explain where my thoughts are wrong? Are they?

m <=

min(1000,n*(n-1)/2)Thank you, so this was a 'how do I read correctly' kind of problem... |-)

Am I the only one who passed the pretests of problem A Div.1 using a Top Down approach?

deleted

I did, but I had to resubmit at the end of the contest to reduce memory usage :( Recursion uses memory too, so having array size within the limits is not enough.

I tried this test in Custom Invocation and got MLE:

`-1 200 -1 200 ...`

.Does anyone have a correct solution for Div. 2 F/ Div. 1 C? I found something that gave but I couldn't improve it further.

Nigga read the comments.

Sorry, I had missed your comment, thanks!

How to solve Div1C:

How do you generalize the answer from this? It's just 5 guys chilling in a row with 2 in front of them

In one column you have a knight at y=0, in the next one at y=0 and y=3 and that pattern repeats. It seemed quite obvious to me.

EDIT : Didn't see that the editorial is already published.

EDIT: Most probably, it fails because I am assuming the CHT implementation to be min-oriented but it actually is max-oriented.

Idk, seems reasonable to me. But I also observed that the optimal i for each t would be the same, i.e. we just spam some i until one upgrade is available. So no need to use CHT here.

EDIT: Same as jtnydv25 and realized the editorial doesn't do what I did :s

Do you mean for each t > 1? (otherwise the statement is definitely wrong), and how do you prove it even for t > 1 ?

Wow, right when I tried to write my proof I realized it was completely wrong :o

How it was not caught in the pretests is beyond my knowledge though.

Anw there goes my red xD was fun bragging around

Please someone tell me, why do I get TLE in this: http://codeforces.com/contest/1068/submission/44804608 This is Div2B

Please tell me, it won't take a minute for you to read my code.

Integer overflow. Remember,

n≤ 10^{10}.Thanks, figured out :(

i*i becomes a negative value when it overflows, so your for is basically infinite

Div1C

Is this the way to place the knights?

Dear kristevalex and Um_nik, please stop making problems.

What's wrong with vintage_Vlad_Makeev? Was he hacked or just rofl?

maybe he tries to do the same thing as .o.

English statements are not too good, especially problem Div2C. Still, it was a fun competition, thanks for the effort.

The problems were nice, but the contest was bad. Here are the reasons:

All of that are valid points, thanks.

Output of C provides almost no information. I don't think there is any mistake here. Out of 3 people who said "easy to generalize" only 1 guy actually did it.

which observations does B need? it was obvious from the picture how to solve it

div1 B test case "1 1" is not in the pretest...

Why was Div2B given a max score of 1250 instead of the usual 1000? Did you think Div2B was closer to Div2C than Div2A? I read Div2B 4 times because of your decision to give it 1250 points. Guess I should have done that for Div2A instead as it had such a good corner case. I read similar complaints about Div1A and Div1B as well. Points distribution was not good.

After this round, i am demotivated for sure.

code_hard123 bro you are back!

if http://codeforces.com/contest/1068/submission/44797756 is AC. why http://codeforces.com/contest/1068/submission/44800937 is WR?

`Participant's output -501767591`

So it seems that you have overflow. Checking the code you declared

`int bs()`

instead of`ll bs()`

. I didn't test it but it seems that is the problem.Started after 10 minutes, misunderstood B, got WA, then solved A, panicked with B, pretests passed E, panicked with B again then finally understood(felt so stupid at that time), couldn't submit C with 2 seconds in hand! :(

Watched the status board with heart in my mouth whether E will pass the system test or not. It passed :D Submitted C after contest, AC in one go. -_-

Mixed feelings, A very eventful contest indeed!

## Very nice problem !

## And I finally got the Expert Title during this contest!

## I wait for this blue name for a YEAR and I finally got that!

Congrats bro!

Thanks.

And wish you can get the Expert Title in the next competition!

I finally made it! Its feels so good :)

Unfortunately the system tests on today's Div 1 problem D were quite weak. I wrote up an explanation here: https://codeforces.com/blog/entry/62692. Make sure to take a look if you are trying to solve problem D in practice mode (or just interested in the problem).

How to solve div2D?

Could anybody help me why I am getting wrong answer for Div2 C? Solution

Thanks!!