### MikeMirzayanov's blog

By MikeMirzayanov, 5 years ago, translation, ,

Please take a notice that recently the schedule has been changed. Twice.

Greetings to the Codeforces community!

I'm glad to announce that we again decided to introduce a round based on one of the programming olympiads for schoolchildren in Saratov. This time it is a round for participants from Division II. Round will start at unusual time for Codeforces: Dec. 7, 07:00 UTC.

The problems were prepared by employees and students of Programming Competitions Training Center of Saratov State U.

Members of the first division can participate out of competition, as usual.

Currently we are planning to use dynamic scoring system.

UPD: Moved from 09:00 to 07:00 because of Kotlin Challenge.

•
• +52
•

 » 5 years ago, # |   -7 children*
•  » » 5 years ago, # ^ |   0 Really Nice contest...
 » 5 years ago, # |   +11 Nice schedule for next two rounds!
 » 5 years ago, # |   -33 Can you move it to 06:00?
 » 5 years ago, # | ← Rev. 2 →   -19 Could you please move 1 or 2 hours earlier? It overlaps 1 hour with Facebook Hacker Cup. Thanks.EDIT: Sorry, I confused the times. They don't overlap.
•  » » 5 years ago, # ^ |   -8 No, it doesn't. The hacker cup starts 9 hours after this round ends.
•  » » » 5 years ago, # ^ |   0 Thanks, I got confused.
•  » » 5 years ago, # ^ |   +8 Round 1 lasts for 24 hours and time penalties don't matter for advancing to the next round, feel free to participate at whatever time you like -- there's no advantage to doing the problems right at the start of the round.
 » 5 years ago, # |   -8 thanks, have a nice contest:)
 » 5 years ago, # |   -13 What will be the scoring?
•  » » 5 years ago, # ^ |   0 It's dynamic score, thats mean, the problem most solved will have 500 points, etc.
 » 5 years ago, # |   +3 good luck everybody.
 » 5 years ago, # | ← Rev. 2 →   +1 What's the intended solution for problem C? I tried many different greedy approaches, yet they all fail in test 10. And maximum cardinality bipartite matching TLE's in test 12!
•  » » 5 years ago, # ^ |   +5 me too!
•  » » 5 years ago, # ^ |   0 Sort all the numbers in array a, then reverse them in array b. Then the pairs with the same numbers can form only a single subsegment. Then try to swap some numbers from b in this subsegment with some numbers from b either at the start or the end. One can prove this is optimal.
•  » » » 5 years ago, # ^ |   0 Does this rely on a well-known greedy algorithm? something like load-balancing I mean? I always have a very hard time with problems that have greedy solutions :D
•  » » » » 5 years ago, # ^ |   +3 As far as I know it doesn't. It's just a hunch for this problem.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +10 bipartite matching works, build the graph with color of mittens as the vertex and the number of each mittens as capacity of the vertex from super-source to each color and each color to super-sink, it works in O(m^3) which is enough to pass the time limit.
•  » » » 5 years ago, # ^ |   +3 Aha I see, this approach depends on M, my approach depended on N that's why it TLE'd. Nice idea!
•  » » 5 years ago, # ^ |   +2 My idea was to build another array and send it to output with res[i] + " " + res[ (i+offset)%size ] ; // i = 1..n where array looks like 1 1 1 2 2 3 for 1 2 2 1 3 1 // (I've just found that I simply need to sort it, xd) so, "offset" is maximal count of 1..m types (or colors, I don't remember)and this method gives output 1 2 1 2 1 3 2 1 2 1 3 1 
•  » » » 5 years ago, # ^ |   0 How did you think of such a solution? :D. The only thing I could think of was to match the two colors with the maximum frequency in each step
•  » » » » 5 years ago, # ^ |   +3 I was trying to solve 5 5 1 2 3 4 5 with some obvious approach
•  » » » 5 years ago, # ^ |   0 I tried same logic. Success.@array = sort {numeric, reverse} @array;@array = @array x 2;$multiline .=$array[ $i ]." ".$array[ \$i + max_repetition ]."\n" FOR @array
•  » » 5 years ago, # ^ |   +3 There was a stupid solution: sort left mittens, sort right mittens. shift right mittens cyclically by n/2. P.S. almost the same problem was in one russian contest last year: https://zaoch.olympiads.ru/zaoch/2012-13/final/problems.shtml
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 Here is a solution that seems intuitive to me: First sort the colors with descending number of occurrences We note that if the majority color is <= size / 2, we can get everything to be distinct by simply shifting the majority color to the guy who is at the start of the second majority colorE.g.111111222333222333111111On the other hand, if the #majority color is > size /2, our best choice is still to do the above assignment, because the number of matches is at least 2*#major — size
•  » » 5 years ago, # ^ |   0 Sort all children by colors, and then iteratively check.At the i-th child, check if it is possible to find someone before with unchanged mittens, then swap one mitten with him/her. If everybody before has got changed mittens, then find someone before with mittens share two differenct color with the i-th child, then swap. If there's nobody satisfying these two conditions, then just wait and see.i.e. Initial distribution: 1 1 2 3 3The first two children can only wait: 1 1 2 3 3 1 1Then 2 can swap with the first one: 1 1 2 3 3 2 1 1 Then 3 insert to the second place to 'save' that child: 1 1 2 3 3 2 3 1 1 The Last one swap with the first one: 1 1 2 3 3 3 3 1 1 2The end.
 » 5 years ago, # |   +11 very terrific system test speed
 » 5 years ago, # |   +5 Did you use the Hopcroft-Karp algorithm? I also tried a greedy aproach but realised it fails even on the first example. I didn't manage to finish the maximum matching afterwards.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Well I thought about implementing it during the contest but I thought that it wouldn't pass, the time limit is so strict (1 second)
•  » » » 5 years ago, # ^ |   0 Actually, what did you implement?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 You can see the code here...this algorithm exhausts all augmenting paths in the graph till there is none remaining, this only happens when the matching is maximal.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 It seems i'm not allowed to see that page... Upload the code to Ideone.
•  » » » » » » 5 years ago, # ^ |   0 The comment removed because of Codeforces rules violation
 » 5 years ago, # |   0 The fastest final test speed I've ever seen!
 » 5 years ago, # |   0 blazing fast system test :)
 » 5 years ago, # |   0 ratings, please :)
•  » » 5 years ago, # ^ |   0 -28
 » 5 years ago, # | ← Rev. 2 →   0 Prob-C (Div2): Missed the statement "Note that the left and right mittens are different: each child must end up with one left and one right mitten." ... Paid for my carelessness :(
•  » » 5 years ago, # ^ |   0 My first solution had WA10, because I did not read this sentence, but I fixed this bug :)
 » 5 years ago, # |   0 Why is this o/p wrong for pretest 1? 6 1 2 1 2 1 2 1 2 1 3 1 3
•  » » 5 years ago, # ^ |   +1
•  » » » 5 years ago, # ^ |   0 ok.But i still dont get it? What am I missing here? :(
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 On the i-th of these lines print two space-separated integers: the color of the left and the color of the right mitten the i-th child will get. Note that the left and right mittens are different: each child must end up with one left and one right mitten. You're trying to wear a right mitten on the left hand. It's impossible in this problem.
 » 5 years ago, # |   +5 For C, I thought of the following: 1. Find frequency of each color. 2. Sort the list as per frequency. 3. Pair color with highest freq with color with lowest freq and then decrement frequencies of both colors by 1. 4. Continue till we cant create any more pairs.for example, 1 1 2 1 2 3 would give {1: 3, 2: 2, 3: 1}.i. Make pair (1,3). List now becomes {1: 2, 2: 2} ii. Make pair (1,2). List now becomes {1: 1, 2: 1} iii. Make pair (1,2). End. The answer will be 2*(no. of pairs we make).
•  » » 5 years ago, # ^ |   +4 and it will fail for,1 1 1 1 2 2 2 3 3 3
•  » » » 5 years ago, # ^ |   0 Ok, what will be the answer for this one?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 Hmm.. Many possible answers. But in any case we can pair each one if we do it optimally.e.q. 1 2 1 2 1 3 1 3 2 3 and the reverse! :)
•  » » » 5 years ago, # ^ |   +1 My solution passed systests with such logic, and it also works well on your test.It depends on what color to choose in a case of tie. Choosing max of max, min of min gives WA66, choosing max of max, max of min gives AC.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Nice! It didn't click me. :| Have to check your code! :)
•  » » » » 5 years ago, # ^ |   +1 What do you exactly mean by max of max and max of min here? Can you explain for the above example, 1 1 1 1 2 2 2 3 3 3 ?
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 On your example WA solution gives 10 1 3 3 1 2 1 1 2 3 2 2 3 1 3 3 1 2 1 1 2 and AC solution gives 10 1 2 3 1 2 1 1 3 3 1 2 3 1 2 3 1 2 3 1 2 max of max — from all colors with max number of items i'm choosing one with largest id. Max of min — from all colors with min number of items i'm choosing one with largest id (or with second largest, if at this moment min=max).UPD. I found a bug) Actually my first solution was max of max + max of max, and second one is max of max + min of max)
•  » » » » » » 5 years ago, # ^ |   0 I'm slightly confused. Finally, which combination gave you AC? (max of max, max of min), or (max of max, min of max)?
•  » » » » » » » 5 years ago, # ^ |   0 max of max, min of max.I don't know, is it OK, or just tests are weak:)
•  » » » » » » » » 5 years ago, # ^ |   0 I am unable to think of a reason for a number with larger ID to be included in the optimal solution.
•  » » » » » » 5 years ago, # ^ |   0 What's wrong with the WA in the case 1 1 1 1 2 2 2 3 3 3? I thought it is correct?
•  » » » » » » » 5 years ago, # ^ |   0 Both my solutions works well on this case. But one of them got WA66, and other one got AC.
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Let's wait for the test cases to be put up. Probably we'll have a better idea then.
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 @LeBron I think I know why, your setting will help to avoid this case 1 2 3 4 5
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 me getting wa on 66 case.
 » 5 years ago, # |   -8 what's the test 5 for problem C?
•  » » 5 years ago, # ^ |   0 why system doesn't show the tests? and also other's code??
•  » » » 5 years ago, # ^ |   0 Because this contest is now running in Saratov. Soon the system will show everything.
•  » » » » 5 years ago, # ^ |   0 What time can all testcase be shown ?
 » 5 years ago, # |   0 I'm curious for the solution for problem C……My solution doesn't depend on m……it's just O(n^2),and get accepted,but in fact,i can't prove it's correctcan anyone tell me why it's correct? http://codeforces.com/contest/370/submission/5371522
 » 5 years ago, # |   +32  | | Sent | Accepted | | A | 1094 | 781 | | B | 820 | 654 | | C | 449 | 151 | | D | 130 | 17 | | E | 11 | 2 |  More info
 » 5 years ago, # |   -6 Hmmm, I registered but didn't take part in the contest... So sad :(
 » 5 years ago, # |   0 er.I want to know the Pro C -- test58.why my answers is TLE while I get: for(i=1;i<=n;++i) for(j=i+1;j<=n;++j) if(color[i]!=color[j]) { add_edge(i,j); add_edge(j,i); } http://codeforces.com/contest/370/submission/5379683 , and I get Accepted when I code as: for(i=1;i<=n;++i) for(j=1;j<=n;++j) if(color[i]!=color[j]) { add_edge(i,j); //add_edge(j,i); } http://codeforces.com/contest/370/submission/5379655