Hello codeforces community!
We're glad to announce the 4th edition of Code Mélange, a 5hr algorithmic contest to be hosted on Codechef.
The contest starts on 9PM IST, 4th April, 2018, and goes on till 2AM IST, 5th April, 2018. Check out the timings in your timezone here
The contest is ACM styled, will consist of around 10 problems of varying difficulty, and will be rated for both div 1 and div 2 participants.
Link to contest
The problem setters and testers for the round are usaxena95 vntshh 7dan Vicennial killer_bee rohitranjan017 dc99 and myself.
Net prize to be won in the contest is ₹30K. Oh! and there's 300 codechef laddus for top 5 Global and Indian participants as well :D
See you on the leaderboard!!
[UPD] the contest starts in under 10 minutes. Get ready, everyone :D
nice problems.
Can you please release an editorial ?
Yes, we'll be posting the editorial in a day or two. Also, the problems have been moved to the practice section.
I’m interested in asking you about the question where you have to choose X elements out of N such that the weighted mean is maximized. This appears to be very difficult. Can you rate it with CF difficulty ? Also, I don’t know why the AC solutions are working. Kindly explain it with the perquisites knowledge required.
Say the weighted mean is atleast A and you pick a subset T of size atleast X.
Then
So
So checking if some T exists can be done in O(NlogN)
and just binary search on A.
Can you explain why that inequality holds ?
binary search checks if there is some subset T whose weighted average is atleast A.
Thanks for adding the word at least. It helps :)
How to get the value of A, and the subset T ?
You binary search on A , fill the vector with (arr[i] * i — A * i) , sort it in decreasing order , just check if some subset has sum >= 0 by greedily picking the largest element each time.
This problem is fractional programming
For these problems，there is a common solution called Dinkelbach Algorithm.
I did not know this ! Thanks a lot. Is this very advanced stuff ?
As far as I am concerned, the number of the problems about this algorithm may be less than 10.
I can only list three classical problems about this algorithm.
0-1 fractional programming
Minimal ratio spanning trees
Minimum ratio cycle