kr_abhinav's blog

Invitation to Code Mélange IV
By kr_abhinav, 7 years ago, In English

Hello codeforces community!
We're glad to announce the 4th edition of Code Mélange, a 5hr algorithmic contest to be hosted on Codechef.

Code Melange banner

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!!

  • Vote: I like it
  • +45
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

[UPD] the contest starts in under 10 minutes. Get ready, everyone :D

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

nice problems.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please release an editorial ?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, we'll be posting the editorial in a day or two. Also, the problems have been moved to the practice section.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you explain why that inequality holds ?

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            binary search checks if there is some subset T whose weighted average is atleast A.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks for adding the word at least. It helps :)

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              How to get the value of A, and the subset T ?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            This problem is fractional programming

            For these problems，there is a common solution called Dinkelbach Algorithm.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I did not know this ! Thanks a lot. Is this very advanced stuff ?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                ← Rev. 5   Vote: I like it 0 Vote: I do not like it

                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

                → Reply