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.
UPD 2: Tutorial has been published.
children*
Really Nice contest...
Nice schedule for next two rounds!
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.
No, it doesn't. The hacker cup starts 9 hours after this round ends.
Thanks, I got confused.
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.
thanks, have a nice contest:)
What will be the scoring?
It's dynamic score, thats mean, the problem most solved will have 500 points, etc.
good luck everybody.
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!
me too!
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.
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
As far as I know it doesn't. It's just a hunch for this problem.
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.
Aha I see, this approach depends on M, my approach depended on N that's why it TLE'd. Nice idea!
My idea was to build another array and send it to output with
where array looks like
so, "offset" is maximal count of 1..m types (or colors, I don't remember)
and this method gives output
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
I was trying to solve
with some obvious approach
I tried same logic. Success.
@array = sort {numeric, reverse} @array;
@array = @array x 2;
$multiline .= $array[ $i ]." ".$array[ $i + max_repetition ]."\n" FOR @array
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
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 color
E.g.
111111222333
222333111111
On 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
Code: http://codeforces.net/contest/370/submission/5369409
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 3
The first two children can only wait: 1 1 2 3 3 1 1
Then 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 2
The end.
very terrific system test speed
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.
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)
Actually, what did you implement?
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.
It seems i'm not allowed to see that page... Upload the code to Ideone.
The fastest final test speed I've ever seen!
blazing fast system test :)
ratings, please :)
-28
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 :(
My first solution had WA10, because I did not read this sentence, but I fixed this bug :)
Why is this o/p wrong for pretest 1? 6 1 2 1 2 1 2 1 2 1 3 1 3
http://codeforces.net/blog/entry/9854#comment-153240
ok.But i still dont get it? What am I missing here? :(
You're trying to wear a right mitten on the left hand. It's impossible in this problem.
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).
and it will fail for,
1 1 1 1 2 2 2 3 3 3
Ok, what will be the answer for this one?
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! :)
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.
Nice!
It didn't click me. :| Have to check your code! :)
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 ?
On your example WA solution gives
and AC solution gives
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)
I'm slightly confused. Finally, which combination gave you AC? (max of max, max of min), or (max of max, min of max)?
max of max, min of max.
I don't know, is it OK, or just tests are weak:)
I am unable to think of a reason for a number with larger ID to be included in the optimal solution.
What's wrong with the WA in the case 1 1 1 1 2 2 2 3 3 3? I thought it is correct?
Both my solutions works well on this case. But one of them got WA66, and other one got AC.
Let's wait for the test cases to be put up. Probably we'll have a better idea then.
@LeBron I think I know why, your setting will help to avoid this case 1 2 3 4 5
what's the test 5 for problem C?
why system doesn't show the tests? and also other's code??
Because this contest is now running in Saratov. Soon the system will show everything.
What time can all testcase be shown ?
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 correct
can anyone tell me why it's correct? http://codeforces.net/contest/370/submission/5371522
More info
Hmmm, I registered but didn't take part in the contest... So sad :(
er.I want to know the Pro C -- test58.why my answers is TLE while I get:
http://codeforces.net/contest/370/submission/5379683 , and I get Accepted when I code as:
http://codeforces.net/contest/370/submission/5379655
tutorial link please.
Could there be more contests that are held at 07:00 UTC on Saturdays? I'm a Chinese student. Most contests are held at 11:00 p.m in China, and I hardly have time to take part in the contests.