Tuesday, May 29, 2012

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.

7 comments :

stubbscroll said...

It is possible to have 201 voters in the "easy" problem: percentages {0,0,99} and number of voters {1,1,199}.

vexorian said...

Yes, I just mis-copied what writer said about the upper bound. But it seems 201 is the limit.

dave said...

very disappointed about myself this round. I am kind of jealous your achievement today (just kidding ^^).

I keep practicing but it seems that I havent make any progress. Maybe my practice method is bad. So disappointing T__T

vexorian said...

The thing about practice is that results are never instantaneous.

I might even say it takes 6 months before you'll notice the real effect of whatever method you use.

This_poet said...

Could you please tell me how to solve the div1 900 problem?I am confused about that……

vexorian said...

I wish I could. I gave it a try during the match and was confused.

Solutions seem to first precalculate the first few steps, but I am not very good at reading them.

It is too lame that the forum of 544 is not working, we could ask there.

vexorian said...

Ok, I got it.

It is a linear recurrence problem (Read this tutorial: http://community.topcoder.com/tc?module=Static&d1=features&d2=010408 )

There are two solutions using that approach, one uses a 4x4 matrix (4 linear functions) and the other a 13x13 matrix.

Let f(n) be the total x*y sum after n steps. (Thus f(0) = 0).

Can you write f(n) in terms of f(n-1) (Using the help of other 13 or 3 functions that are also linear).

Try finding 4 functions like this:

f(n) = a * f(n-1) + b * A(n-1) + c * B(n - 1) + d * C(n-1)
A(n) = e * f(n-1) + f * A(n-1) + g * B(n - 1) + h * C(n-1)
B(n) = i * f(n-1) + j * A(n-1) + k * B(n - 1) + l * C(n-1)
C(n) = m * f(n-1) + o * A(n-1) + p * B(n - 1) + q * C(n-1)

( The coefficients in some places might be 0).

For n=0:

( f(0) A(0) B(0) C(0) ) = ( 0 ? ? ? ) (The ? are the initial values of those functions).

With such a recurrence, you can calculate the solution in O( log(n) * 4^3), because:


( f(i) A(i) B(i) C(i) ) x (Some 4x4 matrix) = ( f(i+1) A(i+1) B(i+1) C(i+1) )

More details in the official editorial, which I am writing.

Spoilers:
A(n) is the sum of the x coordinate of each fox after n steps.
B(n) is the sum of the y coordinate of each fox after n steps.
C(n) is the total number of foxes after n steps.

As far as linear recurrence problems go, this is, to me, the hardest of those problems I have solved in years.