SRM 568: Last second

This was hard. The division 1 medium problem was solved by very few people. It seems that problems are becoming harder.

Div1 500: The one with a matrix

A matrix with numbers in it is called nice, if every perfect matching between rows and columns gives the same sum of matched cells. In other words, in a NxN matrix pick N cells such that no two cells share a row and a column, all sets of picked cells possible must yield the same sum of values written in the picked cells.

You are given a NxN matrix , which contains digits from 0 to 9 or -. Count the number of ways to fill each of the - in the matrix with non-negative (possibly greater than 9) integer numbers such that the matrix is nice. It is guaranteed that the number of ways is finite.

... finite. It seems that for the number of ways to be finite, then there should be initially a set of N cells that do not share row/column that do not contain any - character in them. The sum of this set will be the same sum shared by all the sets and can be at most 50*9 = 450. That's about the only progress I could make.

In order for there to be only one possible sum, then the min-cost matching and the max-cost matching of the matrix must be equal. That's it. There are probably many other ideas and the solution is hopefully simple, but I have no idea.

I tried many things during the match. Kept thinking. Opened div1 1000. Eventually I spent my time until the 10 last minutes of the coding phase watching the division summary. It was clear that I was not the only one having difficulty with this problem. Petr was the only coder to have a solution for a looong while. Some blue coders were solving the hard problem, but I doubted those solutions would stay.

Div1 250: The one with colored balls

Less than 10 minutes left. Faithful to my suicidal strategy, I open 250. It seemed like most people would only have a score in this problem, and thus speed would have been quite crucial. From the scores it seemed that taking less than 10 minutes was doable, so I put all my effort.

There are N boxes, each with at least 1 ball and at most 1000000 of each color (red, green or blue). A single step consists of taking a ball from a box and putting it in another box. What is the minimum number of steps needed to make it so no box contains balls of more than one color?

The first idea you can have is to, for each box, pick the color that has the maximum number of balls, and move the other balls to other boxes. The problem is to where?. You can assume that you just move those balls to boxes that will end with that color only, so you can add up, for each box, the number of balls of the colors that are not the maximum in the box. There is an issue with this logic, for example, what happens when all boxes have more red balls than the other colors? Then we cannot move the blue and green balls from each box to somewhere else, because there is no such box.

We can overcome this issue by first fixing three boxes: One that will forcefully have only red balls, another for green balls and another for blue balls. We first need to take the balls with the wrong color from each of these boxes. Then we can continue with the remaining boxes. For each box i, we can take the green balls to the fixed green box, the red balls to the red box, and the blue balls to the blue box . But we can leave one of the groups of balls, the maximum for each box unmoved. This will minimize the number of balls needed. Repeat for every possible combination of 3 balls that are assigned red, blue or green and the minimum possible is the answer.

I finished this when there were 6 minutes left, too bad that there was some mistake in the code stopping me from passing the example cases. I had no idea what it was. Until the timer reached 20 seconds, and I suddenly noticed! In a part I had res += instead of c +=. I corrected the bug and compiled and submitted without testing (20 seconds left!). I was able to submit it almost at the last second!. And it passed.

int minOperations(vector <int> red, vector <int> green, vector <int> blue)
{
    pair<int,int> res = make_pair(2100000000,-1); //std::pair is good like this
    int n = red.size();
    for (int fr = 0; fr < n; fr++) {
        for (int fg = 0; fg < n; fg++) if (fr != fg) {
            for (int fb = 0; fb < n; fb++) if (fb != fg && fb != fr) {
                int moves = 0;
                // fr is a box that is forced to be red
                // fg is a box that is forced to be green
                // fb is a box that is forced to be blue
                
                // Move balls of the wrong color from each of the picked boxes:
                moves += green[fr] + blue[fr];
                moves += green[fb] + red[fb];
                moves += blue[fg] + red[fg];
                // For each other other boxes, leave the maximum color and move
                // the rest to their assigned boxes:
                for (int i=0; i<n; i++) if (i != fr && i != fg && i != fb) {
                    int x = std::max(red[i], std::max(blue[i] , green[i]) );
                    moves += red[i] + blue[i] + green[i] - x;
                }
                
                res = std::min(res, make_pair(moves,moves) );
            }
        }
    }
    return res.second;
}

This is exactly what I wanted to happen ever since I started using that strategy. If I opened the problems in the [Correct] order, I would have probably spent more time in 250 instead of less than 10 seconds (The pressure of the time reaching 0:00 made me wake up and notice the issue), so I would have acquired a far worse score. Then I would not have even had a chance to try the medium problem.

Comments?