SRM 536: heh

So, once again another SRM. After the bad streak from previous times, I really had to revert it. I am writing this before the end of the challenge phase and it seems I did all right.

Div1 250: The one with the average
You have a list of from 2 to 50 integers. We want to merge them all. After you merge a group of numbers, they are replaced with a value equal to the average of their values. You have to merge until there is only one number left.

From the examples, it looks like it is better to merge larger numbers last. This is actually true. In fact, always merge 2 numbers starting from the smallest ones.

The proof comes from the solution. If we sort an array containing 4 values: {a,b,c,d}, then the result of merging it using the strategy will be: (((a + b)/2 + c) / 2 + d) / 2 ... This translates to : a/8 + b/8 + c/4 + d/2. This means that the largest value will contribute 50% to the result whilst, the smallest two values only 12.5%.

    double findMaximum(vector  revenues)
    {
         sort(revenues.begin(), revenues.end());
         int n = revenues.size();
         double avg = revenues[0];
         for (int i=1; i<n; i++) {
             avg = (avg + revenues[i]) / 2;
         }
         return avg;
    }

Div1 500: The one that is not (so much) about expected value.

You have many (up to 50) fair dice of 1,2 or up to 1000000000 faces each. Find the most likely outcome of the total sum of the dies. If there are many of them, return the smallest of them.

At first, it really seemed that calculating the expected value will do. At this point I am almost sure that the expected value will indeed be one of the most likely outcomes, but there may be many more sums with a probability equal to that of the expected value. In fact, I am wondering if the variance comes into play . I am almost sure, but maybe there is a case in which the expected value is not even a result, I really need to re-learn statistics.

So, I first coded the expected value thing. I was very doubtful it worked, but I submitted it anyway. Chances are that if I found a solution that didn't use it I would take so long time that the resubmit penalty wouldn't work.

Then I decided to write a bruteforce-dp program to try random sequences until I find a case in which the expected value does not work. I found {2,2,5}, and many others. So I knew my solution was wrong. I tried to spend the rest of the match finding a correct solution. It didn't work.

The bruteforce+dp solution was useful to analyze the problem though. Seeing its output is what makes me think that the expected value is one of the answers (but not always the smallest).

What I usually do once there is no time to fix a solution that I know is wrong is to make a solution that was still wrong but harder to challenge than average (without doing obfuscation). I made a brute-force expected value hybrid, so that it used BF unless the case is too large. I resubmitted but was kind enough to include a comment stating that the solution is wrong.


Challenge
I was able to apply my knowledge of {2,2,5} to gain 50 points. In fact, if I didn't hesitate for a couple of seconds after I opened a second coder's solution, I would have been able to score another successful challenge.

Coders hesitated to challenge my wrong solution for most of the challenge phase. Eventually the top rated coder in my room grabbed the bonus 50 points.

Comments
Perhaps a little too much statistics oriented. But the problems worked.