SRM 544: Heh

As I write this, the challenge phase has ended and my 275 seems alive. Then again, no one in my room was an aggressive challenger. Let us see what happens.

Div1 275: The one with vote fraud.

You are given an array of integer percentages from 0 to 100. Like {0, 1, 100}. The real percentages have all been rounded to the closest integer. If there was no fraud, the non-rounded percentages will sum up to 100.0 (important). If there was fraud, they would not. So, given the rounded percentages, is there a non-fraudulent scenario that yields those percentages? If so, return the minimum number of voters. Else return -1.

Oh well, it was 7:00 AM and my brain was slower than usual. I could not do much for the first minutes. The persistent idea was to iterate through many possible values for the total sum of voters. Once we find a correct one, return it. We need an upper bound after which we stop testing and return -1. And we also need to know how to test if a voter bound is possible.

How to test if a sum is correct? Let us say that a rounded percentage is p and the real percentage is x. Then we have: floor( ( x*100 + floor(sum/2) ) / sum ) = x. (Try it, this is the same as rounding the percentage).

Let us say that *somehow* with that formula, for each p we can find the minimum value of x and the maximum value of x. Then the sum of all the minimums will be minim and the sum of all maximums will be maxim. If sum is between minim and maxim, inclusive, then the sum is valid.

In order to find those minimums and maximums, you will need to do some magic with the formula. I just used binary search (e.g.: Find the minimum x such that: p<=floor( ( x*100 + floor(sum/2) ) / sum )), because, my brain was not cooperating... The good thing about binary search is that I am quite certain it will give correct results. The bad thing is that it makes the deal slower and thus my upper bound for the number of voters had to be small in order to avoid time out.

const long MAX = 25000; 
struct ElectionFraudDiv1 
{ 
    int minPossible(long sum, long p) 
    { 
        // min(x) : (x*100 + sum/2)/sum >= p 
         
        long lo = -1; 
        long hi = MAX+1; 
        while ( lo + 1 < hi) { 
            long ha = (lo + hi)/2; 
            if ( (ha*100 + sum/2) / sum >= p) { 
                hi = ha; 
            } else { 
                lo = ha; 
            } 
        } 
        return (int)hi; 
    } 
    int maxPossible(long sum, long p) 
    { 
        // max(x) : (x*100 + sum/2)/sum <= p 
        long lo = 0; 
        long hi = MAX+1; 
        while ( lo + 1 < hi) { 
            long ha = (lo + hi)/2; 
            if ( (ha*100 + sum/2) / sum <= p) { 
                lo = ha; 
            } else { 
                hi = ha; 
            } 
        } 
        return (int)lo; 
    } 
     
    int MinimumVoters(vector <int> percentages) 
    { 
        int n = percentages.size(); 
 
        for (int sum = 1; sum <= MAX; sum++) { 
            int minim = 0; 
            int maxim = 0; 
            bool invalid = false; 
            for (int i=0; i<n; i++) { 
                int a = minPossible(sum, percentages[i]); 
                int b = maxPossible(sum, percentages[i]); 
                if (a > b) { 
                    invalid = true; 
                } 
                minim += a; 
                maxim += b; 
            } 
            if ( (!invalid) && ( minim <= sum && sum <= maxim) ) { 
                return sum; 
            } 
        } 
        return -1; 
         
    } 
}; 

It turns out the largest valid number of voters is 200. I do not have a clue how to show it. Empirical testing made me choose 250000 for the limit, I just manually tested with a large array until it did not time out... Spent most of the match concerned about the possibility that this constraint was not enough.

Results for the first room are up, and it seems that people making mistakes in this problem is a very likely setting. I would not be shocked at all if my 275 fails.

Div1 500: The one with the binary matrix

Let us say you have a binary matrix

101010101
010101010
101011010
111001101

You want to make it full of zeros. In each step, you pick the first few cells in each row, but making sure that you pick at least as many cells in row i as you pick in row (i-1). This is the simplification of the problem statement about paths.

The statement says that it is always possible to make a matrix full of 0s with finite steps. Of course it is!. Just think about the first row in the input that contains a 1. You will eventually have to set the right-most 1 to 0. This means picking all the cells until that rightmost 1. If we have to do this move, let us do it. Let say that the number of cells we toggle in this row is (req)

Now, let us say that in a later row, the rightmost 1 does not exist or appears in a cell with a lower value than (req), but we have no choice, we still have to toggle (req) cells in this row. We should not toggle more cells, because it would only add unnecessary 1s that we would have to toggle later...

In the next row to it, the right-most 1 is at a position greater than req. It makes no sense to toggle fewer cells than that. Let us update req to the new value.

Repeat for each row. And repeat this process until the matrix is full of 0s. This approach will always find the minimum number of moves, because we never actually have a decision to make, all the moves we do are forced into us. Also, for each row, you will need at most (Row length) steps. Thus the number of steps is at most O(w*h), and for each step, you need at most O(w*h) steps. O(w*h*w*h) in total.

int minOperations(vector <string> board) 
{ 
    int steps = 0; 
    int w = board.size(); 
    int h= board[0].size(); 
    while(true) { // O(n^2) 
        int j = 0; 
        int req = -1; 
        while (j < w) { //O(n^3) 
            int k = h-1; 
            while ( (k >= 0) && (board[j][k] == '0')) { //O(n^4) 
               k--; 
            } 
            req = max(k, req); 
            // toggle req cells in this row: 
            for (int r=0; r<=req; r++) {  //O(n^4) 
                board[j][r] = '0'+!(board[j][r]-'0'); 
            } 
            j++; 
        } 
        if (req == -1) { // All 0s, stop it. 
            break; 
        } 
        steps++; 
    } 
    return steps; 
} 

Outcome

yay, it turns out that 275 was very tricky and a lot of people had a wrong submission. My binary search, may take a lot of time and code but it made me very certain that the code was correct (assuming the upper bound was large enough). So I had a good position and a room win.