### Igor_Kudryashov's blog

By Igor_Kudryashov, 7 years ago, translation,

Hi to all!)

Regular round Codeforces #205 for participants from 2 division will take place today. Traditional, participants from 1 division can take part out of the competition.

The problems were prepared by Igor Kudryashov (KudryashovIA) and Gerald Agapov (Gerald). Also thanks to Michael Mirzayanov (MikeMirzayanov) for very cool system Codeforces and Mary Belova (Delinur) for translating the problems into english.

We wish everyone good luck, high rating and excellent mood)

UPD: It is decided to use dynamic scoring system.

UPD 2: The contest is over, thanks to all participants.

Congratulations to the winners:

UPD 3: you can find the tutorial here

• +107

 » 7 years ago, # |   -37 I will participate.
•  » » 7 years ago, # ^ |   +54 THANK YOU! We are delighted to hear that.
 » 7 years ago, # |   -11 will the scoring system be static or dynamic?
•  » » 7 years ago, # ^ |   0 It will be determined soon)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -24 deleted.
•  » » » 7 years ago, # ^ |   +4 So?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 there are only 5 minutes left for the round to start, please publish the scoring system asap!UPD: it is now published, and it is dynamic system!
 » 7 years ago, # |   +13 Next Round is on Sunday. Awesome!!!
•  » » 7 years ago, # ^ |   -6 Do you now turkish lenguage ? ? ?
 » 7 years ago, # | ← Rev. 2 →   -8 The worst round I've ever performed. Sad... T_T
 » 7 years ago, # |   0 Does anyone know what B — test case 6 is about?
•  » » 7 years ago, # ^ |   0 People say, that your programm could fall down because of different count of bones on both bags.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 try this91 2 2 2 3 4 4 4 5 6 6 6 7 8 8 8 9 10
•  » » 7 years ago, # ^ |   0 Try this: 4 99 89 88 98 89 88 89 88 This should give 9 as answer
•  » » » 7 years ago, # ^ |   0 Well:92 2 1 1 1 2 2 1
•  » » » » 5 years ago, # ^ |   0 sol of B used by judge is wrng People say, that your programm could fall down because of different count of bones on both bags.Yeah what u said is true.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 There's one apparent reason that contributed to B being as hard as it was: the answer is (number of different numbers in first half)*(in second half); if there's a number occuring at least 2 times in the input, we should choose one copy of it to each half, and for the remaining numbers (occuring once), we could put them into both halves in any way (then, we complete the halves by putting the remaining copies of the numbers occuring at least thrice, and it doesn't matter how we do that). But since we want the answer to be as large as possible, we need to put half of those once occuring numbers to one half ad the other half to the other — the answer is (x + a)(x + b), when there are x numbers occuring at least twice in the input and a + b occuring once, and that expression increases as |a - b| decreases. Proof by taking the zero of the derivative (when we allow ).
•  » » » 7 years ago, # ^ |   0 I struggle if you mean (x + a)(x + b) & that expression increases as |a - b| decreases.
•  » » » » 7 years ago, # ^ |   0 Yeah, that's what I meant. I wrote it in a hurry, so typos are inevitable :D
•  » » » » » 7 years ago, # ^ |   0 Excuse me, does that mean that if we just sort the numbers and then in a sorted array will put all the odd indexed elements in one heap and all even indexed in another and just count the number of different pairs, since n is not big, we have a correct solution?
•  » » » » » » 7 years ago, # ^ |   0 No. It fails on the array "1 2 2 2 3 4 4 4" — you put 1 and 3 in the same heap (answer=8), but you should put 1 in one heap and 3 in the other (answer=9).But if you try this approach separately on once occuring elements and separately on multiple times occuring ones, it works.
•  » » » » » » » 7 years ago, # ^ |   +8 Yeah, now I see. Thank you very much! :-)
•  » » » » » » 7 years ago, # ^ |   0 consider:1 2 2 2 3 4 4 4you'll get81 2 1 2 1 2 1 2while correct answer is 91 1 2 2 2 2 1 1
•  » » » » » » » 7 years ago, # ^ |   0 Thank you!
•  » » » » » » » 7 years ago, # ^ |   0 special judge
•  » » 7 years ago, # ^ |   0 That is the 6th system test, which falls down my prog till now:5049 13 81 20 73 62 19 49 65 95 32 84 24 96 51 57 53 83 40 44 26 65 78 80 92 87 87 95 56 46 22 44 69 80 41 61 97 92 58 53 42 78 53 19 47 36 25 77 65 81 14 61 38 99 27 58 67 37 67 80 77 51 32 43 31 48 19 79 31 91 46 97 91 71 27 63 22 84 73 73 89 44 34 84 70 23 45 31 56 73 83 38 68 45 99 33 83 86 87 80
 » 7 years ago, # |   0 thanks for this great contest .......!!
 » 7 years ago, # |   +2 What is the intended solution for E?
 » 7 years ago, # |   +14 It was fastest system testing i've ever faced on Codeforces.Whole system testing phase just took 8 minutes. Codeforces Rocks!
•  » » 7 years ago, # ^ |   +2 May the rating changes take just as long next time :D
 » 7 years ago, # |   0 very good and fast system testing today! :)
 » 7 years ago, # |   -8 First time I solved 4 problems during a contest on codeforces :-DI'm happy although it's unrated for me :-) Thank you for preparing this contest!
 » 7 years ago, # |   0 i am a freeman i want to know if we have the solution after every round ?
 » 7 years ago, # |   -9 I joined late , problem C is very interested .. isn't it guys ?
•  » » 7 years ago, # ^ |   0 Yeah, well the whole round was interesting. I like D most, though.
 » 7 years ago, # |   0 How solve the problem B??
•  » » 7 years ago, # ^ |   +3 You can solve B with greedy assignment of the blocks.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 My solution: 4730199Idea:To solve problem B, you should put the number in balance (n numbers to heap 1 and n numbers to heap 2), to make the number of distinct 4 digit number maximum, if there are same number, say there are i number x (i>1, if i=1 it considered unique number that will be processed later), you should put (i div 2) number x into heap 1 and (i div 2) to heap 2, and if there are remainder (i is odd), save to heap 3 temporaryly (will be processed later).After that process the rest unique number (i=1) into heap 1 and heap 2 equaly, if there are j unique number, put (j div 2) to heap 1 and j-(j div 2) to the heap 2. And then the rest (heap 3) will fill heap 1 and heap 2 until full (have n numbers each, the order isn't important)Finally count the distinct number in heap 1, save to variable a and heap 2 to variable b, and the total distinct 4 digit number is a*b. and then just print the output.If there are more simple solution I would like to know :-)
•  » » » 7 years ago, # ^ |   +3 It's very clear, thank you
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 This comment was my mistake. Deleted.
 » 7 years ago, # |   0 Lot's of DP problems. Love that contest though i miss A for some silly mistake. :( (Y)
•  » » 7 years ago, # ^ | ← Rev. 3 →   +13 Actually any of this the problems may be solved without DP (except, maybe D, where solution could be called DP, but I wouldn't call it so)
 » 7 years ago, # |   0 Any ideas of around when the tutorial will be published?
 » 7 years ago, # | ← Rev. 2 →   0 Awesome round. It is always a surprise when scoring goes dynamic. #Enjoyed. Looking forward for more matches of this kind.
 » 7 years ago, # | ← Rev. 2 →   -17 it was a awful contest!!!
 » 7 years ago, # |   +5 It is 70 minutes after the contest now and ratings are not published yet...
 » 7 years ago, # |   +4 how the system testing is so fast and the rating is so slow? Isn't harder to judge than to update the rating? Maybe I'm wrong, but it would be nice to know.
•  » » 7 years ago, # ^ |   +8 maybe checks all solutions to find cheaters .
 » 7 years ago, # |   0 dynamic scoring system and dynamic problems ! thank you
 » 4 years ago, # | ← Rev. 3 →   0 Update: The original comment is my mistake.(353B - Two Heaps, test 6) I think Problem B judgement is wrong (the checker issues false negatives for some valid solutions).
•  » » 4 years ago, # ^ |   0 In the problem statement there is a phrase:"He arbitrarily chooses n cubes and puts them in the first heap. "So it IS necessary that the heaps have the same size.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Oh, indeed! Thank you.I think I was misled by this: The other question is: how to split  into two heaps so that this number (the number of distinct fourdigit integers Valera can get) will be as large as possible? I mean that the absence of something like "...in two n-sized heaps...", together with "other question" wording did this to me :)I relied too much on the wording of the last paragraph of the problem statement. My bad.