Saturday, January 22, 2011

Member SRM 494 - Commentary and explanation for div1 250

Second match after my decision to start with the hard problem, then try the medium (when there are 33 minutes left) and then the easy (when there are only 11 minutes left).

Div I Hard: KnightsOut
A very interesting problem. I couldn't think of much, I noticed that cases in which the minimum side is less than 2, can be solved using dp or other simple methods. So you would only need to handle the cases in which both dimensions are greater than 3. It seems Petr had a similar idea, but it is far, far away from what I could do in 44 minutes.

Div I Medium: AlternatingLane
This also seemed like a good problem. I imagined plenty of things. Noticed a dp [100000][2][50] could work as long as I figured out a way to do each state in O(high[i]). I think there is a way to do it by accumulating the results for each [previous][0,1][n] for each n. and then you can use a subtraction to get the sum, and the summation formula to get the sum of differences between the previous value and the new one. But it needs work. Something I noticed is that when the lane is already alternating after picking the heights, you are not allowed to cut down trees, even if that would yield a higher beauty. It seems like such thing would make my dp idea more complicated.

When there were around 14 minutes left to the match, I was still far from thinking of a definite solution for the 500. I was paying attention to the summaries and it seemed like it was a good idea to reserve some more time to it. And it was unlikely I would think of the solution and code it in less than three minutes. So I switched to the easy.

Div I Easy: Painting
A cool problem that was actually coding-based instead of math-based like the previous 60 Div 1 easies were... A nice change. I managed to solve it but...

Blunder: I have made many mistakes while coding the solution for this problem, so even though I started coding it right away, I still needed 12 minutes to finish debugging it. Unfortunately, I made a mistake, once I passed all the example cases, it occurred to me to try doing a timeout test "just in case". But think about it, even if I found out that the solution is too slow, I would not have had enough time to fix it (there were only two minutes left). Also, for some reason I made a lot of mistakes when trying to generate a large case with python. Fortunately, I came back to my senses and decided to compile and submit with some few seconds left for the match. This blunder cost me at least 10 points, which would translate in ~30 positions.

The result was a not-good but not-bad position, I earned 2 rating points (but I lost a lot of points last match).

So, here comes my explanation for the easy problem. I plan and hope to get explanations for the other problems seeing how member SRMs don't have editorials, and the problems seemed fun, but it depends on how much time I can manage to have.

Explaining the Div I Easy: Painting
Problem statement

We want to maximize S, the size of a SxS brush. In maximization problems, it often pays to change the option from "Maximize S" to "Is it possible to do it with a value S?". If we use the latter question, we can actually just iterate from higher values of S and keep decreasing S until it is possible to use such value. For example, try a size 50 brush, if it is possible to do it, return 50, then try a size 49 brush, and so and so until a good size is found or until the brush size becomes 1 (in which case we can be certain that the result is 1, as it is always possible to do it).

Since we now want to know if it is possible to use a SxS brush to paint the painting, how about the following algorithm? For every brush position (i,j) , if there is no white cell in the painting in the SxS area starting at (i,j), then we can paint a SxS black square in that area. If it is possible to paint such a black square, there is no reason not to paint the square, because we are allowed to paint the same cell more than once. So, how about we begin with a completely white board and then iterate through all the (i,j) cells in the board, and if it is possible to paint a SxS in each of the cells, just paint it. If at the end the board is equal to the painting, then it is possible to do it with a SxS brush.

Note that such algorithm will require O(min(W,H)) iterations for S, O(W*H) (i,j) iterations for each cell , and inside those iterations, we need to try SxS squares to check if they contain white cells or not and then to paint them. So, we can estimate the complexity to be O( min(W,H) * W*H * W*H ) . With W,H <= 50, that may appear to be too high for the two seconds limit, but in reality, it is not (In fact, the following code needs 67 ms in the worst case, I think a good complexity analysis should show it is actually very fast and the O() notation is hiding something.)

Sample code:
   1 int isPossible( vector<string> & picture, int s) {
2 int w = picture.size(), h = picture[0].size();
3
4 // An initially-white board:
5 vector<string> board( w, string(h, 'W') );
6
7 for (int i=0; i<w-s+1; i++)
8 for (int j=0; j<h-s+1; j++) {
9 //pick (i,j):
10 bool can = true;
11
12 // is it possible to draw a SxS black square at (i,j) ?
13 for (int x=i; (x<i+s) && can; x++)
14 for (int y=j; (y<j+s) && can; y++) {
15 can = can && (picture[x][y] != 'W' );
16 }
17 if( can ) {
18 //it is possible, paint it:
19 for (int x=i; (x<i+s) && can; x++)
20 for (int y=j; (y<j+s) && can; y++) {
21 board[x][y]='B';
22 }
23 }
24 }
25 // if the board and the picture are equal,
26 // then it was possible to use a SxS brush:
27 return (board == picture);
28 }
29
30 int largestBrush(vector <string> picture)
31 {
32 int w = picture.size(), h = picture[0].size();
33
34 // try all possible values of s, until finding the
35 // largest valid one:
36 for (int s= std::min(w,h); s>1; s--) {
37 if( isPossible(picture, s) ) {
38 return s;
39 }
40 }
41 return 1;
42
43 }


During the match , I was too cautious and didn't trust the O( min(W,H) * W*H * W*H ) solution, I instead used binary search. Note that if it is possible to use a size SxS brush to paint the painting, then all brush sizes smaller than SxS will also make it possible (You can always make a SxS square by combining smaller squares). And the opposite is also true, if it is not possible to use a SxS brush, then larger brushes will also not be usable. This means that there would be a line dividing the possible brush sizes with the impossible ones, therefore, we can use binary search to find the maximum allowed size.

Thursday, January 13, 2011

SRM 493, div1 450 : AmoebaCode

Problem statement

It seems that the key observation and the one I missed during the match is to find an upper bound for the result.

The maximum minimum distance between two equal digits is actually K. I think that intuition is necessary to suspect so and afterwards, you can prove by using the following logic:

We have two indexes i<j, the digits code[i] and code[j] are equal. And we would like to assume that there are no other equal digits between them, so the distance is j-i, and we would like to say that j-i is also the minimum distance. To ensure this, all the digits between them must be unique. That is because if two of the digits between i and j were equal, let us say two indexes a,b such that i < a < b < j and code[a]=code[b], then the minimum distance would actually be b-a , because b-a < j-i .

So, assume that the minimum distance in a code is K+1 . Then we would have two digits code[i],code[j] that are equal such that j-i = K+1 .This implies there are K digits between them. We know that the digits must be unique, and that the digits must be different to code[i]. Then we have K-1 available digits that must be put in K slots, one of the slots would forcefully have to use a repeated digit. For higher values of the minimum distance, K+2, K+3, etc, it is even harder because there are even more slots to fill. But if we tried exactly K, then there would be exactly K-1 slots to fill with K-1 which is possible. We can conclude that the maximum possible minimum distance for a given K is equal to K.

If we know that the result is at most K, then for each digit in the code, we only need to check the previous K-1 digits and the next K-1 digits. If none of those digits is equal to the digit we are checking, then we can conclude that either the distance between the digit and a duplicate is at least K, or maybe the digit has no duplicates. However, due to the previous demonstration, at least one pair of digits will have a distance of K or less. So, we can just ignore digits that do not have a pair with K-1 digits of distance.

Now, imagine we are putting digits in the code in order from 0 to n-1. When thinking of what digit to place in an index i, we do not need the list of all the digits we put before i, we only need the previous K-1 digits. This list of K-1 digits, is much smaller than one of potentially n-1 digits, with K<=7, the total of such lists would be 77-1=117649 (for each of the K-1 slots, pick a number between 1 and K).

So, consider the following recursion: We have a list of K-1 digits that come before our current index p. Say we pick a digit D. If D is in position x of the list of K-1 digits, then the current minimum distance that we know of is dist=K-1-x. If the digit is not in the list, we can assume the distance is dist=K, if the distance was higher than K, it would not matter, this distance will be canceled by a smaller distance anyway (we only care about the minimum). We have to generate a new list of digits that includes D and disposes of the first digit of the list. We can call the recursion again with (newlist, p+1) , the result of this recursion will be the maximum minimum distance for the remaining indexes. The minimum between (dist, the called recursion's result) is the maximum distance we can get by using digit D in position p. If we try all possible digits D, and pick the maximum distance that can be acquired by any of the digits, we have the result.

If we are out of indexes, we can just return K, again, in case K is not the minimum distance, it will be canceled later.

Since there are only at most 117649 lists, at most 50 positions and in each step of the recursion we may need to try K possible digits, we can use dynamic programming or memoization to implement this recursion and it should take O(KK-1* n * K) or O(KK* n). This is fast enough to run in C++ but not that fast. I think there should be improvements available or a faster solution.

Implementation details such as how to make the list as an argument remain. I just encoded the list in a number from 0 to KK-1 , so it is basically a base K number. To quickly access its indexes I use a powK array that contains all the necessary powers of K.

Some C++ code:
using namespace std;
int mem[51][117649];

struct AmoebaCode
{
string code;
int k;
int powk[10];
int rec(int last, int p) {
int&res=mem[p][last];
if(res==-1) {
if(p==code.size() ) {
//The end, return K, if the result is smaller, it will
//be cancelled in a top call.
res = k;
} else {
//find the distances between digits and the values in
//the list, if the digit is not in the list, assume
//the distance is K.
int dis[k];
fill(dis,dis+k, k);
for (int i= std::max(p-(k-1),0); i<p; i++) {
int x = (last/powk[i-p+k-1])%k;
dis[x] = p-i;
}
//Try all values i for a digit, keep the maximum minimum distance
res = 0;
for (int i=0; i<k; i++) {
if( (code[p]=='0') || (code[p]-'1'==i) ) {
int nlast = last/k + i*powk[k-2];
res = std::max( res, std::min(dis[i], rec( nlast, p+1) ) );
}
}
}
}
return res;
}
int find(string code, int K)
{
if(K==1) {
return 1;
}
//initiallize arrays and variables.
memset(mem,-1, sizeof(mem));
powk[0] = 1;
for (int i=1; i<10; i++) {
powk[i] = K*powk[i-1];
}
this->code = code;
this->k = K;

//call the recursion.
return rec(0,0);
}
};




This turned out to be a interesting problem. I think the reason it was so difficult during the match and turned out harder than the admins expected is that it is not actually as easy to see the K boundary for the result. I could not notice it during the 22 minutes I gave to this problem during the match, and it did not occur to me until today in the afternoon.

Wednesday, January 12, 2011

SRM 493 - comments

The decision
Before starting this SRM I had made a decision, it was based on many reasons, some of which I can list:
* I have stayed in the 1800->2050 topcoder rating spectrum for years. It has become repetitive and one cannot help but feel stuck in this status quo. Matches that you win 100 points, followed by matches in which you lose points and eventually it all evens out and you notice you are still in the same area as three years ago...
* mishastassen moved to opening the hard problem first. It at first destroyed his rating and moved him to gray territory. But when he came back, he became able to solve some of the hard problems.
* TopCoder problem sets recently... Have become very annoying. "Easy" problems that steal all your match's time leaving me little to no time to solve the Medium problem and zero time to even open the Hard problem. I am tired of all matches being about "Can you solve 250 in time?" and nothing else. Specially because the recent Easy problems are mostly math oriented and turn out to be boring once you understand them. All while you are missing the cool dp/graph theory Medium pointer fun...


So, I have made a decision, starting SRM 493 I will open the Hard problem first, the Medium problem next and finally, the Easy problem.

I know that this will kill my rating but that is not the point, the point is to actually improve and get better. I think that if I deal with harder problems more usually, I will start becoming able to solve them during the match. Also, if I stop relying on having the whole 75 minutes available to solve the Easy problem, I will stop being so slow when solving it.

Anyway, I don't want the situation to reverse and end up only dealing with the hard problem. I want to open all three problems during a match and give them appropriate time. Since Topcoder problem scores are supposedly based on the time it takes to solve them. Then I can assign time to the problems by using an equation: x+2x+4x = 75 . Where x is the amount of time to spend in the 250, 2x the time to spend in the 500 and 4x the time to spend in the 1000. It is not an exact division but I decided to assign 11 minutes to the "Easy" problem, 22 minutes to the "Medium" problem and 42 minutes to the hard. So, the "strategy" is :
* Open the Hard problem when the match begins.
* Open the Medium problem when there are 33 minutes of coding phase left. (Or once the Hard problem has been solved, whatever happens first).
* Open the Easy problem when there are 11 minutes of coding phase left. (Or once the Medium problem has been solved, whatever happens first).

The SRM
Before the coding phase, I could take a look to the scores, 300,450,1000. My conclusion was that 1000 was going to be unsolvable or solvable only by Petr. But 450 was probably going to be simpler than 300. Nevertheless, I would only have 22 minutes to solve 450, which seemed unlikely. Because I am not that fast. And a 300 would make the dream of solving it in less than 11 minutes impossible. While trying to solve the 1000 pointer, I noticed that only one coder took less than 11 minutes to solve the 300... Everything was a bad omen. This SRM was not the right one for this strategy.


1000 pointer - AmoebaDivOne
Hey, maybe I would get lucky "and 1000 is actually solvable", I thought to myself. Well, it was a interesting problem. I eventually thought of a O(N⁴) dynamic programming solution. The idea is that, if you consider that the previous row has the cells between a and b taken by an amoeba, then the next row can have cells between other variables, na and nb. na and nb can change, but I thought to myself, that in order to keep the amoeba convex, The lower limit cannot decrease after it was increased at least once and upper limit cannot increase after it was increased. So, you could use a recursion of sorts.


Well, while I was coding that solution to find out if it actually works, I noticed that the problem was basically forcing a special kind of input to have a constraint of 100x100 instead of the usual 50x50. That was suspicious. Once I ended up coding my initial idea, it didn't work correctly in the examples that had "matter" cells, and when I gave it a 100x100 case, it timed out. So, the idea was lacking something. But by then, the time was out, I moved to the medium problem.

450 pointer - AmoebaCode
A simple problem statement. Out of a number with more than K digits, you need to replace the 0 digits to a digit between 1 and K, such that the minimum distance between two equal digits is as large as possible. Very classic.

I noticed that K is at most 7. So, the low value of K was probably necessary. For some reason, the only dp variation I could think of was to keep a list of O(K) integers which say the position of the last digit equal to i placed (for each i between 1 and K). That would definitely time out.

The strangest idea I had was to try a binary search. If we had a way to check if the result is lower than X. The only idea for this check I had was to use something related to graph coloring (If we want the minimum distance to be K, then each cell has K-1 cells to the right and to the left that must have a different number (color). We can call the cells edges and the link that means they should have a different color, edges). But I don't think there was an easy way to verify the coloring. The time eventually ended.

Word on the streets is that the intended solution for this problem was a form of dynamic programming. That's embarrassing, I usually see the dp solutions rather quickly, specially for a 450. hmnn...


Div1 300 - StonesGame
Ok... 1000000 stones , that seemed complicated. After a while, I started to experiment with the idea that if Player 1 cannot win in a single move, he won't win, and that the same happens to Player 2. If neither can win in his first move it is a tie.

After the match, I imagined of ways to prove the assertion. Imagine that Player 1 can only win after his first step, Player 2 can just revert his first step and make him unable to win. Something similar can be done about Player 2.

Anyway, by the time I decided to try implementing that idea, I had around 2 minutes left. But I still didn't think of how to deal with the way that moves work in this problem. It was only around intermission time that each move consists on moving the white stone to a position K-1, K-3, K-5, ... K-1-2*n.

The outcome
A loss of 97 rating points!. It was not too much. A lot of people had zero scores today. Well, the objective with this experiment is not short-term rating but a long-term improvement. It is too early to see if it works.