### HolkinPV's blog

By HolkinPV, 7 years ago, translation, ,

Welcome, dear friends)

We are glad to introduce you regular Codeforces round #151 for Div.2 participants. Traditionally the others can take part out of the competition.

Today's problems were prepared by authors: Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

Score distribution will be standard.

We wish everyone good luck, successful hacks and high rating!

UPD: the contest is over, hope you enjoy it)

Congratulations to winners:

1. a58 (he solved all 5 problems)
2. thangpc
3. Minecraft
4. xiaoshua3
5. Nezdeshniy

UPD2: you can find the editorial here

• +98

 » 7 years ago, # |   +46 Can you please fix the registration for Div.1 participants? We can't register out of the competition.
•  » » 7 years ago, # ^ |   +19 I have the same problem.
•  » » 7 years ago, # ^ |   0 It works now, thank you.
 » 7 years ago, # |   +9 lets fun everybody :)))
•  » » 7 years ago, # ^ |   +7 we want to register , watching others writing contest isn't very attractive :))
 » 7 years ago, # |   +9 Div1 people are unable to register for the contest (unrated). Please fix this issue.
 » 7 years ago, # | ← Rev. 3 →   +3 We are very lucky div2 participants. Sorry for you(div1) :D.They will fix it,I am sure. Because many people wants it.
 » 7 years ago, # |   +9 Fix please :D can't not wait until succesful register message appear :))))
 » 7 years ago, # |   +5 all contestmakers are offline :(
•  » » 7 years ago, # ^ |   +3 :D :D hahaha
 » 7 years ago, # |   +68 I guess if Div 1 registration won't be fixed soon, there will be more new users than usual in this contest.
 » 7 years ago, # |   +8 Good Luck everybody!
 » 7 years ago, # | ← Rev. 2 →   +7 Don't worry, some of the contest authors will connect before the contest start because they have to check everything is ok, and they will fix it.
 » 7 years ago, # |   +6 REGISTERED!!!
 » 7 years ago, # |   +1 151 minutes before the start Codeforces Round #**151**,Good Luck everybody!
 » 7 years ago, # |   -6 Thank god! I has just register succesfull :))
 » 7 years ago, # |   +1 Lucky codings and hackings to everybody ;) Just Have Fun!
•  » » 7 years ago, # ^ |   -8 sorry to say,but I don't like when someone says "wish you successful hacks",Simply say that I wish you success,sorry again if I said something bad,This is only my opinion.
•  » » » 7 years ago, # ^ |   +21 "wish you successful hack" it is not bad wish. It means you help someone who coded wrong to know that his/her solution wrong! If he/she didn't locked that problem he/she will resubmit it. Otherwise if he/she already locked that problem wil not wait for that problem while judging.If someone didn't hack your problem while you submitted wrong solution. You will think your solution is acceptableHacker gain 50 more point for their goodness ;)
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +5 Yup! I think soJust imagine that you submit, accept pretest but WA in the main testYou may wish that somebody hack your solution and you will recheck your submission :)
•  » » » » » 7 years ago, # ^ |   +3 you are right,sorry for my comment. so WISH YOU SUCCESSFUL HACKS!!!
 » 7 years ago, # |   +3 gl & hf
•  » » 7 years ago, # ^ |   0 thanks
 » 7 years ago, # |   -6 Waiting for a competitive contest. Also expecting a good problemset.
 » 7 years ago, # |   0 good luck everybody, happy solving! :D
 » 7 years ago, # |   +13 Hope server will stable today.
 » 7 years ago, # |   -13 The comment removed because of Codeforces rules violation
 » 7 years ago, # | ← Rev. 3 →   0 I liked the problems, but they seem much easier than usual div2... Hope I am wrong and my solutions will fail full system test =DEdit: nevermind, just figured out that my E solution is a complete failure. :D Edit2: YEAH! E failed with Time Limit on 60 =D
•  » » 7 years ago, # ^ |   +7 You should not talk about your solutions during the contest: you give a advantage at the coders who are on the same room than you and who came here by saying that your E, if it isn't some bluff, has chance to be hacked.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 that's why I'm not even going to unlock it.. =D Anyway, I didn't say anything clear about it...
 » 7 years ago, # |   -7 Could anyone explain it to me please:Q(k) = {cu :  cu ≠ k and there is vertex v belonging to set V(k) such that nodes v and u are connected by an edge of the graph}.
 » 7 years ago, # |   +3 Nice contest.
 » 7 years ago, # |   +6 Can we give input with leadings zeros when it must be integers? I have seen a scanf("%i") on my room, but didn't know if I can hack him by giving integers like 033 who will be considered like a hexadecimal.
 » 7 years ago, # | ← Rev. 4 →   0 in how much time are the systests completed? EDIT: So, much negative votes just for asking a question!
 » 7 years ago, # |   +10 Wow Amazing system testing speed.
 » 7 years ago, # | ← Rev. 2 →   +9 In question D , the definition of Q(k) was quite mathematical , I could not figure it out correctly so got a lot of wrong answers.
 » 7 years ago, # |   +7 perhaps it was better if problems C and D were swapped, for a more standard score distribution!
 » 7 years ago, # |   -6 this contest was very good, one time it is difficult an one time it is fun :D :)))
 » 7 years ago, # |   +3 will be the rating soon?? i cant wait, am nervious :D :D
•  » » 7 years ago, # ^ |   0 still no rating change...
 » 7 years ago, # |   +4 What is the main idea of problem C? Though I could managed to make it accepted by randomized algorithm(2616018), but I think it's not beautiful...
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 1) n times 1 2) n-1 times 2 (pairs with most beautiful) 3) n-2 times 3 (two most beautiful with others) ... k) n-k+1 times k (k-1 most beautiful with others) ... n) all of them 
•  » » 7 years ago, # ^ |   +3 Sorry, I posted my solution in Russian, but forgot to translate it... First step. Let's print every soldier. Second step. We take the "beautiest" soldier and print him with every differrent soldiers. Third step. We take two "beautiest" soldiers and print them with every differrent soldiers. And so on. Obviously, all these sums are different (because of monotony). And thier number: n+(n-1)+(n-2)+...+2+1=n*(n+1)/2. Example of output: 1 2 3 4 4 1 4 2 4 3 4 3 1 4 3 2 4 3 2 1 Code
•  » » » 7 years ago, # ^ |   0 I was wondering how to make sure that the total beauty is different from other combinations. Now it's clear. Thank you very much!
•  » » » 7 years ago, # ^ |   +3 banging my head on the wall after hearing the solun :(
•  » » » » 7 years ago, # ^ |   +1 Same here(
•  » » 7 years ago, # ^ |   +1 Randomized algorithm, cool =)Notice that k is at most n.(n+1)/2 Solution is to use the following values:(a[0]),(a[1]),...,(a[n-1]), (contains n detachments)(a[0],a[n-1]),(a[1],a[n-1]),...,(a[n-2],a[n-1]), (contains n-1 detachments)(a[0],a[n-1],a[n-2]),(a[1],a[n-1],a[n-2]),...,(a[n-3],a[n-2],a[n-1]), (contains n-2 detachments)...All of these sums are different. Number of available detachments using this method = n + n-1 + n-2 + ... + 1 = n*(n+1)/2 so you will always be able to get k detachments.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +2 The randomized solution is much more beatiful for me :| I didn't implement it well myself though.2619137 — a fixed 50 percent probability was way too slow2621963 — a randomized probability makes the solution quite fast
•  » » 7 years ago, # ^ |   +1 There exists a rather simple deterministic solution which has O ( N * K * ln ( K ) ) complexity. Traverse though the array and try to add current number to any of the possible sums and if you can make a non existing sum add it to the list of existing sums. Use a set to check if a sum exists or not in logarithmic time.Solution : 2616373
 » 7 years ago, # |   0 Problem D:Please note, that you want to find such color, that the graph has at least one vertex with such color.for the sample below3 11 2 2 2 3my output is 1, it passed system test though there is no vertex with color 1. i m still confused. o.O
•  » » 7 years ago, # ^ |   0 1 Vertex color is 1.
•  » » 7 years ago, # ^ |   +1 you are confusing between vertex color and color of those vertices which are connected by edges. vertex 1 is colored by color 1 and hence it counts.
•  » » » 7 years ago, # ^ |   0 vertex 2 and 3 has same color, so they are not "colored" => they have 0 colored neighbours, so as vertex 1 that has color 1. So the answer is 1.
 » 7 years ago, # |   0 Sorry if this seems to be a stupid question, but why is B's solution, n if sum mod n = 0, otherwise n-1?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 It's obvious that we always can make n-1 equal by adding or subtracting 1 from any other sacrifice-lamb element (e.g. n'th). If sum mod n == 0 then we can also do this for that last element, making all of them equal to sum div n.
•  » » 7 years ago, # ^ |   +1 We can make an unlimited number of moves.
•  » » 7 years ago, # ^ |   +4 n-1 is always possible: we can make a[2]..a[n] equal to 10000, decreasing a[1] at every step. If sum % n == 0, we can make all a[i] equal to sum / n. And it's obvious that we cannot make it otherwise.
•  » » 7 years ago, # ^ |   +1 when sum%n==0, we can get n numbers, which will be equal to average. when sum%n>0, we can get n-1 numbers, which will be equal to average, and 1, which will be average+sum%n=)
•  » » 7 years ago, # ^ |   +1 Thanks all of you.
 » 7 years ago, # |   0 it is frustrating to continuously check whether the ratings have changed or not after the end of a great contest...
•  » » 7 years ago, # ^ |   +1 can the admins tell when the ratings will get updated??
•  » » » 7 years ago, # ^ |   0 6 4 11 22 22 44 55 66 1 2 1 3 4 5 4 6 How about this data of problem B,, the right is 44 or not ?? Thank you !
•  » » » » 7 years ago, # ^ |   0 The right answer is 44 or not ?? Thank you ,,
•  » » » 7 years ago, # ^ |   0 Ratings are updated now.
 » 7 years ago, # |   0 plz quiqly :(
 » 7 years ago, # |   +5 Banging my head after solving problem C now :| I was using bit-masking and unordered_set in the contest and got hacked (TLE)! It couldn't pass the test cases though,, by the way,, very nice contest. Loved the problems. Tricky yet pretty simple solutions :)One simple request,, found it bit hard to understand the problem descriptions,, a simple note and easy explanation could help us and save much time of us. Thanks :)Sorry for my bad English.....
•  » » 7 years ago, # ^ |   0 I think there's room for improvement in the English Descriptions. Anyhow, they're always comprehensible.
 » 7 years ago, # |   0 What is the approach for problem E?
•  » » 7 years ago, # ^ |   +6 First, solve the original version. http://codeforces.com/search?query=130&_tta=375
 » 7 years ago, # |   0 For E they said that Print m whitespace-separated integers — the answers to Polycarpus's records. But printed integers on new lines.
•  » » 7 years ago, # ^ |   0 Actually it doesn't matter, depending on the judge used. When we must print numbers, usually the CF system checks your output token-by-token, ingoring whitespaces and new lines.
•  » » » 7 years ago, # ^ |   0 Thanks. I didn't know that.
 » 7 years ago, # |   0 which data structure should we use to find the number of different strings on a segment in problem E?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 http://codeforces.ru/blog/entry/5935It's link to AC solution, which do it in such a way: At first calculate it in linear time. Cache the answer into some map and in future answer to the same query in O(logN) time. P.S. If you would like to read some prove of correctness, look at http://codeforces.ru/blog/entry/5935 :-)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 For arbitrary queries [L, R] your may for each i precalculate next[i] (minimum j > i : a[i] = a[j]), and then answer to query will be number of i in [L, R] such that next[i] > R. In offline it can be calculated in using segment tree with sweeping line.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Does it consists of sorting queries or you can get the answer for arbitrary query in o(logN) time ?
•  » » » » 7 years ago, # ^ |   +3 "In offline" means, if I have m queries, I can get all m answers in time.Let our quries are segments [L..R], and array "next" is already calculated.for i = 1..N cnt[next[i]]++ for all q : R=i increase answer[q] by Sum of cnt on [R+1..n+1] for all q : L=i+1 decrease answer[q] by Sum of cnt on [R+1..n+1]
•  » » » » » 7 years ago, # ^ |   0 This can be done in o(N+M) time. You are always looking for sum on [r+1..n+1] so you can easyly change it in o(1) when you step to next i.Sum will decrease by cnt[i].and you will go to i+1.Looks like you will get LogN for binary search to transform V[i], K[i] into L[i],R[i].
•  » » » » » » 7 years ago, # ^ |   0 I'm sorry. Right version: R[q]. I thougt it's obviously =(