Wednesday, October 26, 2011

SRM 522: Double meh

Slow day.

Div1 450 - CorrectMultiplication
(Link to statement)
I opened it, and it first seemed like I saw the problem before. After trying to remember it I used google in topcoder, and found a problem in SRM 190 that was about correcting digits. I still find it hard to believe this problem didn't appear before. Anyway...

So, I first tried to find an upper bound for the result. If positive values are allowed for A,B and C, then we can always try A=1, B=1 and C=1. 1*1=1. This means that the result cannot be larger than (a-1)+(b-1)+(c-1) (cost to transform them into ones). Later I thought of a lower bound: If a is set to 1, then b and c must be equal and the cost to make them equal is always abs(b-c). It follows that a possible bound is : (a - 1) + abs(b - c). And another is (b - 1) + abs(a - c). If we take the lowest possible of all those three choices, I think the maximum result ever will be close to 15000000000, ergo 64 bits result was not necessary.

Knowing an upper bound is only half the battle. We need to find values A,B,C that give the result. In these cases , it may be a good idea to first fix one of the values. But with an upper bound as large as 15000000000, it means that A can be at most a + 15000000000, that gives us quite a search space.

The trick here is to notice that A*B = C. If you think about it, Either A will be less than or equal to the square root of C, or B will be. So, since C is at most (c + UPPER), we can try numbers from 1 to squareroot(c + UPPER) as either A or B. The square root of 2500000000 is a large number but small enough to use in a loop.

Then we have to solve this sub-problem: Given a fixed A (or B), find the best pair (B (or A), C) such that: (A * B = C). We are doing it inside a O(SquareRoot(UPPER_BOUND)) loop, so this should be fast. This is the part of the problem in which I got stuck.

I tried some optimizations that weren't very good, I actually passed example tests, but giving it some combinations of high and low values I failed those cases. This may me notice that it was easy to get the problem wrong. So I was expecting many solutions to fail. The large amount of submissions I could see confirmed it.

Div1 250 - RowAndCoins
(Link to statement)

After trying and trying I decided to switch to the 250 when there were less than 15 minutes left for the match.

This is a case in which a lower constraint can actually make the problem harder. If the constraint was 50, many coders would have suspected of the easy solution instead of losing time implementing the uber-messy memoized recursion solution. I was one of those who mechanically did memoization.

Bitmask dp? It sounds complicated, but really it is not that much complicated. First, let me introduce you to a friend called vector dp.

So, instead of using bitmasks, the recursion will have the state (vec, player). vec is a vector of booleans - vec[i] is true if the i-th cell is not empty. Player is 0 if it is Alice's turn or 1 if it is Bob's turn. The result is true if the player whose turn it is will win the game given those values (and assuming both players play optimally).

Now we are using a vector as part of our recursion state. It does not matter. We can use all sorts of data structures as part of our state. What really (REALLY) matters when solving dp/memoization problems is that the recurrence is not cyclic.

Using a vector as key, means that we cannot use a normal array to store the values. That is not a big problem, we have to use the language's associative arrays. In c++, that means std::map, in Java, HashSet or TreeSet or whatever. In python, use dict().

Base case: If there is only one empty cell left in the row (use the vector), then one of the players won. If the remaining empty cell is 'A', then Alice won, else Bob. Note that if player the winner must be Alice to return true, and if it is 1 Bob.

The rest: There are more than 1 empty cell in the vector. The player should pick a group of contiguous cells, we can just try all possible combinations of starting and finishing cells such that they do not overlap with non-empty cells in the vector and such that at least one empty cell is left after that.

In this case, we have to update the vector for each possible move. The new vector will be vector2. In the next turn, the player changes, so the new player is !player (the negation) . We have vector2 and player2. We can call the recurrence (vector2, player2). If the other player will lose in this new instance of the recurrence, then it is a good idea for the current player to use that move, as it will guarantee him a victory.


Bitmasks?
The idea with bitmasks, is really to use a mask to represent the vec variable. Instead of a vector of booleans, each i-th bit in the mask represents whether the i-th cell is empty or not. Since the key is now a bitmask, we can represent it as a single integer, and we can use a normal array to store the values. That makes it easier to implement (and probably faster) than using that vector of boolean values.

The problem is that using bit masks is a guaranteed way to make the code hard to read. This tutorial by bmerry is really helpful and it taught me all about using bits to represent sets (arrays of booleans)..


Outcome
I was able to finish the 250 very fast (for me, considering it is a messy bitmask dp). I was not very sure if it would pass (A random bug is always a possibility). I had 5 minutes left so I kept trying the 450 but I couldn't do much.

For the challenge phase, I knew there were going to be many failed 450s in the room and I also knew that I had to get a successful challenge if I wanted to avoid a terrible score. So I was ready to hammer.

I am very slow when challenging and I'd rather read the code before challenging, so what I do is pick the coder with the median rating in the room. The aggressive challengers generally pick the lowest rating coders to read first. I read a code for a while and at first it seemed like it would time out. I wasn't sure but I eventually decided to challenge it. Got some lucky 50 points.


At the end those points were very helpful, I ended at position 141st. Which is not very good but at least good enough to win 8 rating points.

Div1 250 again
After the challenge phase, I wanted to see what could possibly explain the large scores in 250. It turns out there is a very easy to code solution. If there is an A in any of the extremes of the string, Alice can win in one turn. What is cooler is that this is not only a sufficient condition but also a necessary condition. If both extremes contain a B, there is nothing Alice can do to win.

If Alice covers one of the Bs in the extremes, then she will either leave only the other B empty, which means Bob wins. Or she will leave the B and some extra space contiguous to it which Bob can cover and still win.

So, Alice has to pick a space in the middle of the row to cover. After she does this, all Bob ever needs to do in any turn is to cover as many contiguous As as he can until he consumes them all. Alice will try to cover contiguous Bs, but there are more groups of contiguous Bs than As.

Commented code for division 1 250:
   1 struct RowAndCoins
2 {
3 string cells;
4 int t;
5
6 int mem[1<<14][2];
7
8
9 // Will player #player win in this situation?
10 // the i-th cell is non-empty if and only if the i-th cell in mask is 1
11 bool rec(int mask, int player)
12 {
13 int & res = mem[mask][player];
14 if ( res == -1) {
15 // Has the game ended? We need to count the number of empty cells
16 // and find the type of the only empty cell if that's the case.
17 int ec = 0;
18 char fc = '?';
19 for (int i=0; i<t; i++) {
20 if ( !(mask & (1<<i) ) ) {
21 ec ++;
22 fc = cells[i];
23 }
24 }
25
26 if (ec == 1) {
27 // only one empty cell.
28 // If it is Alice turn's she wins if and only if the empty cell is 'A'
29 // If it is Bob turn's she wins if and only if the empty cell is 'B'
30 res = ( (player==0) == (fc=='A') );
31 } else {
32 res = 0;
33 // Try all possible moves.
34 for (int i=0; i<t; i++) { //i is the starting cell
35 int taken = 0;
36 for (int j=i; j<t; j++) { // j is the last cell of the group.
37 if ( !(mask & (1<<j) ) ) { // all the cells in the group
38 // must be empty
39 taken++;
40 if ( ec - taken >= 1) { //one empty cell must be left.
41
42 // The new mask.
43 // update all the cells between i and j, inclusive
44 // with 1 bits.
45 int nmask = ( mask | ( (( 1<<taken )-1) ) << i );
46
47 // If the next player loses with the new match,
48 // the current player has found a winning move.
49 res |= ( ! (rec(nmask, !player) ) );
50 }
51 } else {
52 break;
53 }
54 }
55 }
56
57 }
58 }
59 return res;
60 }
61
62 string getWinner(string cells)
63 {
64 t = cells.size();
65 this->cells = cells;
66 // Initialize the table
67 memset(mem,-1,sizeof(mem));
68
69 // If Alice wins when the board is empty, then return "Alice".
70 return rec(0, 0) ? "Alice" : "Bob";
71 }
72 };



Div1 450 - revisited
Once you have a fixed A, you can see that there is an equation A*B = C, or actually C = A*B. Smaller values of B will yield smaller values of C. It turns out you can just assume that C will have to be close to c. You can do k = c/A, and then just know that B will be either k-1, k or k+1. Or you can also note that there are four equations, (c + cost_c) = A * (b + cost_b), (c - cost_c) = A * (b + cost_b), (c + cost_c) = A * (b - cost_b) and (c - cost_c) = A * (b - cost_b), you can try finding the lowest cost_b, cost_c for each equation.

Friday, October 14, 2011

So, about that CF contest today

I tried a division 1 CF contest today. I'll keep trying them but it seems things haven't improved that much. The first two levels were trivial. The middle one easy but a pain to implement. The rest harder than I could solve. It is the same sandwich feeling I got in my last CF contest last year :/

Problem A
I had terrible luck with this one. I rushed to implement it, but a bug in the implementation made my computer freeze because of using too much RAM. I need to implement measures on my CF testing thing such that things with too much RAM will be killed. 10 minutes later after surviving the freeze and fixing the mistake I am already quite behind in the standings.

Problem B
I thought I solved it, but apparently there is something tricky with this problem that not even the problem setter could see before this contest.

Problem C
At first it was very hard to read this problem. After decoding it a little, I could see it was a very obfuscated dp problem. But otherwise a simple one at that.

You can define your state with three values : (t, x, o) . t is the number of subjects you have already picked. x is the id of the last one. and o is equal to (picked number of tasks) - a[x], for that last subject. Note that b[x] - a[x] will be at most 100, so o can be at most 100. Also, x as parameter works because you have to pick the subjects in strictly ascending order of complexity, so you just need to worry about the other subjects that have a larger complexity. This makes the recurrence acyclic and actually simple.

After defining the state, you can see the problem as maximizing two variables : a) The best number of subjects you can pick following the conditions and b) The best number of tasks you can get by using that previous argument. Of course, a) must be equal to n, else the assignment is impossible. Then you just pick the assignment with the best b). Building the assignment using the data from the recurrence requires you to recall the recurrence again.

Once I debugged this solution and passed pretests, I received the announcement that the round will be canceled. I decided to use my time on an assignment to write a Pacman clone for school instead of the contest. Aided because I read problem D and it seemed complicated.

Turns out I failed problem C, it is likely a small issue. I am right now not sure about what the problem with B is, but it is likely that I was affected by the same bug that made the judge's solution fail.

I am sort of glad it got canceled, because at the end my position depended solely on my speed in A, and that one was 8 minutes higher than it should be due to bad luck.

Thursday, October 13, 2011

SRM 521: Meh

So, after the disaster from SRM 520, I tried to recover rating. Wanted 2000 back. I think I was really close but I made a terribly bad mistake.

Div1 500
Didn't like this match mostly because of this problem. At first it was hard to understand and it had an ambiguity in the statement. Later it turned out that I still didn't understand it correctly even after the intermission phase.

Div1 250
When there were 14 minutes left I opened the 250. I knew I should be able to solve it in under that time. I saw very high scores for this problem. In fact, hundreds of it.

It was a very easy problem. Too easy, to be honest. Worse, it seems it appeared in Codeforces last year: http://codeforces.com/contest/26/problem/B

I solved it but I was failing examples. After a couple of seconds debugging I find the mistake, and get 246 score. That was bad, because with 246 you get position 200+, but with 248 you get 100+.

Challenge
At first, I got lucky because I found a wrong solution for the 250. Someone was checking for the sign of the number of open parenthesis before changing it instead of after. So a simple ) was enough to challenge it.

Later I really screwed up. With the 296 score I had a very good place, and 50 points wouldn't improve that position. -25 points would really break the position though, so there was really no good reason to try any more challenges. Yet I did, and I did it because I misread a min() as a max() function. Without this mistake I would have returned to 2000+ rating.

To make matters worse, it seems that the 1000 was easier than the 500 and had many successful solutions.

And here is an explanation for the div1 250
The problem asks for you to fix a sequence of parenthesis: (())()( so that it becomes correct adding the minimum number of parenthesis.

We will go from left to right and for each open parenthesis, increase a counter and for each closed parenthesis decrease it.

If the count becomes negative, then we have too many closed parenthesis. It is best to add an open parenthesis right before the newest closed parenthesis we found. Then we have to set the count back to 0.

At the end, the count may be non-zero, this means there are too many open parenthesis, it is best to add just as many closed parenthesis.

Friday, October 07, 2011

Codeforces round #89

I have been meaning to participate in Codeforces again since a couple of months ago. But CF has the habit of always picking the worst possible schedules for me. Today was not going to be the exception, but thanks to social unrest, I didn't have class today so I tried CF again.

C - Fancy Number
Problem statement
I opened this first. In reality I think that in these division 2 contests I should open D first. What's done is done. I had a little disruption while solving it, went to eat something. Anyway.

At first I really didn't understand exactly what the statement meant by repeated digits. For example, 00001122 has 8 repeated digits. At the end I concluded that it means that at least one digit must be repeated at least K times.

So, there are only 10 available digits. Let us try the minimum cost to have one of those digits repeat at least K times AND the lex-first string that has such cost. Then we pick the best result among all digits.

Given a digit ch, build the minimum cost, lex-first string that contains that digit at least k times. We just need to pick the best k positions in which we will place ch. Of all positions, let's find the cost to turn that position into ch. Note that we should always pick the k minimum costs. Not doing that will yield a higher total cost to convert the string. However, sometimes there will be more than k positions we could use for the same cost. Then we need a tie-breaker to ensure that the first string is the lexicographically-first.

So, how about this, if two positions would yield the same cost to turn into ch, we need to pick the one that would yield the lexicographically-first string.

* If one of the positions had a digit larger than ch and the other didn't, pick the former.
* If both positions had a digit larger than ch, pick the earliest one. Because the first position has priority when doing lexicographical comparisons.
* If If both positions had a digit smaller than ch. Pick the latest position.

This is somewhere in which std::pair is helpful.

So, here is the solution:
int n, k;
string digits;

pair<int,string> make_best(char ch)
{

set< pair<int, pair<int, int> > > pos;
// Rate all the positions in the string
for (int i=0; i<n; i++) {
int low = 0;
int ni = i;
if (ch == digits[i] ) {
low = 1;
} else if (ch > digits[i]) {
ni = -i;
low = 2;
}
int c = abs( ch - digits[i] );

pos.insert( make_pair( c, make_pair(low, ni) ) );
}
//pick the k best positions to put a ch there.
string nw = digits;
int sum = 0;
for (int i=0; i<k; i++) {
set< pair<int, pair<int, int> > >::iterator q = pos.begin();
int c = q->first;
int ni = abs(q->second.second);
nw[ni] = ch;
sum += c;
pos.erase(q);
}
return make_pair(sum, nw);
}

void solve()
{
pair<int, string> best = make_pair(1000000, string("ERROR") );
for (char ch='0'; ch<='9'; ch++) {
best = std::min(best, make_best(ch) );
}
cout<<best.first<<endl;
cout<<best.second<<endl;
}



A - B
There is really nothing to say about these problems. They are just about implementation. So , you better know your language. I failed A twice because I didn't expect Y to be considered a vowel and because I really didn't notice that you were supposed to convert upper case consonants to lower case. Need to pay more attention.


D - Caesar's Legions
Link to statement.
I think this problem was easier than C, to be honest. K1 and K2 were very low (<= 10) . I am not sure why. But there is a dp solution.

Let us say that we have r1 footmen and r2 horsemen left to place. The previous lastn positions, contain footmen or horsemen depending of the value of a variable lasttype, if lasttype = 1, then the previous lastn positions contain horsemen. So, we in fact remember the contents of the previous positions, we just have to make sure that lastn does not ever exceed k1 or k2 depending on whether they are footmen or horsemen.

Let f(r1,r2,lasttype, lastn) the total number of ways to solve that sub-problem. The final result will be f(n1,n2, 0,0) (There are n1 footmen to place, n2 horsemen, and we can pretend that there are 0 footmen in the previous positions). So, let us think of transitions:

* At each position, we can place a footman, or a horseman. Depending on what we do, we increase lastn or set (lastype = 1, lastn = 1) in case we placed a different type of unit than the previous one.


That yields the following dp solution:
const int MOD = 100000000;
int n1, n2, k1, k2;

int mem[101][101][2][11];

int count(int r1, int r2, int lasttype, int lastn) {
int & c = mem[r1][r2][lasttype][lastn];

if (c == -1) {
c = 0;
// place r1
if (r1 > 0) {
if (lasttype == 1) {
c += count(r1-1,r2,0,1);
} else if (lastn < k1) {
c += count(r1-1,r2,0,lastn+1);
}
}
//place r2
if (r2 > 0) {
if (lasttype == 0) {
c += count(r1,r2-1,1,1);
} else if (lastn < k2) {
c += count(r1,r2-1,1,lastn+1);
}
c %= MOD;
}

if (r1 == 0 && r2 == 0) {
//all done!
c = 1;
}

}
return c;
}

int solve()
{
memset(mem,-1,sizeof(mem));

return count(n1, n2, 0,0);
}


Problem E
Problem statement
Thank you CF, apparently I needed to be reminded that graph theory is not my strength.

Things that I tried and failed:
a) Assumed that for there to be a solution, there needs to be a Hamiltonian cycle in the solution. Then the solution is to build that cycle. At first, for some reason I was finding and building Eulerian cycles instead, and that's wrong. Once I tried to do Hamiltonian cycles instead, I noticed that the idea is probably wrong. Building such cycles is NP-hard :/.

Update: So the idea about cycles was close. All vertices must belong to the same cycle = They should belong to the same strongly connected component.

Hacks
Apparently CF thought that the best thing they could copy from TC was the randomness from the challenge phase. Unfortunately, you need flash to look at the solutions. Why? Really, why? You have this web-based contest system that is very portable and easy to setup, and you ruin it with flash? I mean , gosh.




Conclusion
Quite honestly, CF's problem sets seems to have gotten less annoying and better than back when I stopped it. Though this is only the div2 contest, I am not sure how div1 is now. Hacks however, really need to stop requiring flash.

I will participate in more CF contests, provided the schedule works for me.

Tuesday, October 04, 2011

SRM 520: Bad day

Yeah, 0 points. And what's worse is that it is not because of not being able to solve the problems. I just made mistakes and couldn't debug them in time.

I started with the 500 and intended to switch to the 250 15 minutes before the end of the coding phase if necessary. The time I used to allocate to 250 "just in case" used to be 30. Today's match kind of shows why it was a good idea to use 30. Or does it? In my case, solving the 250 after 30 would have meant 150-ish of score and that is almost as bad as 0 score-wise for my rating. Yet, I think that it was very possible I could have solved the 500 with those extra 15 minutes. Also, this is probably going to make me forcefully get faster on solving the 250. I am actually considering to start switching when there are 10 minutes left. That will probably make me go through more bad matches like today's. But now that my rating is going to be kicked way fa from its close-to-red glory, I no longer have to care about that, and I can begin experimenting.

SRMIntermissionPhase
This problem was not so hard to solve algorithmically, but I found it very complicated in implementation.

The main idea is this: Imagine you had an array ways[i][j] that would tell you the total number of ways to have coder #i score j as total score. (Using combinations of its solved problems). Then the problem becomes a rather simple dynamic programming idea. The recurrence is a follows:

f( i, j) = f(i, j-1) + ways[i][j] * f(i-1, j-1).

Where f( coder_number, coder_score ) is the total number of ways the scoreboard can have a score less than or equal to coder_score for coder # coder_number.

Then we just need to calculate ways[i][j]. It is another simple recurrence. This time for each coder, you decide the number of ways to score X using the K last problems (where K is 0, 1, 2, or 3). Then you can get the value for K=0 easily (It is 1 iif X=0). The remaining values can be found with the recurrence:

G(X, K) = sum( G(X-r, K-1) ) , where r is a possible amount to score in problem (K-1) .

The recurrences are dead simple. But they take plenty of memory and are slow. The first work around is that:

G(X, K) = sum( G(X-r, K-1) )

Can be calculated if you somehow have the accumulated values for G(X,K-1). That took me 30 minutes to implement correctly beyond segmentation faults, and perhaps that is where my mistake is.

Then, you have to worry about memory. The idea is that in G's recurrence, you only need to know the results for K-1. Also, you only need to know the ways[] table for one coder at once. Finally, F(i,j), also depends only on the last value of i.

But it was very hard to implement for me. I passed all example cases except 1). That includes the last case which was the most complicated. I am right now not sure what happens with 1) , but it is probably something small and evil.

I spent a lot of time trying to debug it. Eventually, I reached the 15 minutes mark and switched to the 250.

250 SRMCodingPhase
I decided to use dynamic programming to solve this problem. There are certainly other ways, I just thought dp would be simplest. In part, when I found my mistake , it was because implementing my dp way too mechanically.

First of all, the order in which you solve the problems does not matter, provided that their sum does not exceed 75 minutes. So you just have to decide which problems to solve. Then you also need to decide what to do with all your luck points.

My dp recurrence F( l, t, k) : The best score using k problems, l lucky points and with t total minutes available.

When k is 0, the result is 0, we just don't have any problem we can solve.

If k is not 0, we have to pick an amount x of luck points to reduce from skills[k-1]. Then we subtract from l and also make sure t does not go negative (else we wouldn't have time left to solve this problem). The recurrence step is then:

F(l, t, k) = max( F(l - x , t - nt, k - 1) ) + points[k-1] - (2 , 4, or 8) * nt.

Where nt is the amount of time needed to solve the (k-1)-th problem using x skill points.

int countScore(vector <int> points, vector <int> skills, int luck)
{
int dp[luck+1][76][4];
memset(dp,0, sizeof(dp));
for (int i=1; i<=3; i++) {
for (int l=0; l<=luck; l++) {
for (int t=0; t<=75; t++) {
// do not solve:
dp[l][t][i] = dp[l][t][i-1];

// solve using x luck points
for (int x=0; x<=l && x < skills[i-1]; x++) {
int nt = skills[i-1] - x;
if (nt <= t) {
dp[l][t][i] = max(dp[l][t][i], dp[l-x][t - nt][i-1] + points[i-1] - (1<<i)*nt );
}
}
}
}
}

return dp[luck][75][3];
}


I unfortunately, couldn't find a mistake I had in my code in time. If you are curious, the mistake was that I was doing: dp[..][..][..] += other stuff. Instead of : dp[..][..][..] = max(dp[..], otherstuff).

Update
I finally found the error in my code for div1 500.

Glance at this bit:

if (j > 0) {
assert(ways[j][1] >= 0);
assert(dp[j-1][ni] >= 0);
dp[j][ri] += (ways[j][1] * dp[j-1][ni]) % MOD;
assert(dp[j][ri] >= 0);
} else if (i == n-1) {
dp[j][ri] ++;
}


The mistake is very simple. I did that if, so that I would handle the case in which the new j becomes negative. If it is the last coder, then this is always possible. However, I forgot about the number of ways to have j as result for the coder (what I do in the first branch of the if then else. Thus the fix is just to:

if (j > 0) {
assert(ways[j][1] >= 0);
assert(dp[j-1][ni] >= 0);
dp[j][ri] += (ways[j][1] * dp[j-1][ni]) % MOD;
assert(dp[j][ri] >= 0);
} else if (i == n-1) {
dp[j][ri] += (ways[j][1]);
}


And yep, it passes system tests.

If it wasn't for me taking at least 15 fruitless minutes to find this mistake, I would have had more time (and less nervousness) to solve the 250 and possibly find the other silly mistake. This mistake was really the difference between position 50 and 0 points for me.

It took me hours to finally find this mistake. At the end, this is what worked: I noticed that in example one, all coders only have one problem, so the number of ways for each coder to have a score was not the problem, this helped me focus on the bottom part of the code.

I have taken a decision for future SRMs. Although using variable names like dp is very cool, I think it would have really helped me to use more a descriptive variable name like maxScore[][][] . Then it would have been very hard for me to unconsciously add the results up instead of max.