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 (Igor_Kudryashov) 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
I will participate.
THANK YOU! We are delighted to hear that.
will the scoring system be static or dynamic?
It will be determined soon)
deleted.
So?
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!
Next Round is on Sunday. Awesome!!!
The worst round I've ever performed. Sad... T_T
Does anyone know what B — test case 6 is about?
People say, that your programm could fall down because of different count of bones on both bags.
try this
9
1 2 2 2 3 4 4 4 5 6 6 6 7 8 8 8 9 10
Try this: 4 99 89 88 98 89 88 89 88 This should give 9 as answer
Well:
9
2 2 1 1 1 2 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 ).
I struggle if you mean (x + a)(x + b) & that expression increases as |a - b| decreases.
Yeah, that's what I meant. I wrote it in a hurry, so typos are inevitable :D
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?
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.
Yeah, now I see. Thank you very much! :-)
consider:
1 2 2 2 3 4 4 4
you'll get
8
1 2 1 2 1 2 1 2
while correct answer is
9
1 1 2 2 2 2 1 1
Thank you!
special judge
That is the 6th system test, which falls down my prog till now:
50
49 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
thanks for this great contest .......!!
What is the intended solution for E?
It was fastest system testing i've ever faced on Codeforces.
Whole system testing phase just took 8 minutes. Codeforces Rocks!
May the rating changes take just as long next time :D
very good and fast system testing today! :)
First time I solved 4 problems during a contest on codeforces :-D
I'm happy although it's unrated for me :-) Thank you for preparing this contest!
I joined late , problem C is very interested .. isn't it guys ?
Yeah, well the whole round was interesting. I like D most, though.
How solve the problem B??
You can solve B with greedy assignment of the blocks.
My solution: 4730199
Idea:
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 :-)
It's very clear, thank you
Lot's of DP problems. Love that contest though i miss A for some silly mistake. :( (Y)
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)
Any ideas of around when the tutorial will be published?
Awesome round. It is always a surprise when scoring goes dynamic. #Enjoyed. Looking forward for more matches of this kind.
it was a awful contest!!!
It is 70 minutes after the contest now and ratings are not published yet...
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.
maybe checks all solutions to find cheaters .
dynamic scoring system and dynamic problems ! thank you
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).
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.