Saturday, May 28, 2011

Thoughts after SRM 507

I had a lot of pressure during this match, it was a long time ago since I had rating >= 2000. I really had to avoid losing it and go back to 1900+ (Which is a horrible place). Also, I knew that If I did well I would be able to surpass 2100. Unfortunately, that could not happen.

Div1 500 CubePacking
The second I opened this one, I knew I was not going to have a good match. It is that kind of problem that for me doesn't work too well. I spent a lot of time trying to do a solution that first picked dimensions of a prism in which to put all the LxLxL cubes and then to grow it to fit the 1x1x1. It seems that solution was completely wrong and clueless. Seeing at how things went, it seems this problem was way easier than that, but I just cannot think of something yet.

When I noticed that there were less than 30 minutes left, I decided to switch to 250.

Div1 250 CubeStickers
Link to problem statement
This one was painful. The first thing I did was to notice that you can sometimes use the same color in two faces. And in fact, that is the most times you can use the same color - Because if two faces are not on opposite sides of the cube, they will always be adjacent. Yet for some reason I couldn't think very fast of a way of actually verifying it.

That is right. In a cube, there are three pairs of faces that are opposites of each other. The only way to place two stickers of the same color is to place them in opposite faces. So, for each unique color in the list: If there are two or more instances of the color, "consume" two faces of the cube. If there is only one instance of the color, consume 1 face. If all 6 faces are 'consumed' everything is right and the result is "YES". If after using all colors, there are still faces that you cannot use , return "NO".

This is where the STL and thinking well of things works best. A good STL solution uses map<string, int> to first save the number of times each color appears. Then you can iterate through the elements of the map, and for each color that appears twice or more, use exactly 2 faces. And 1 face otherwise. Another way to see it is that you can use each unique color at most twice.

#include <vector>
#include <map>

using namespace std;

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct CubeStickers
{
string isPossible(vector <string> sticker)
{
map<string, int> colorTimes;
// Fill the map with the counts of each sticker color
for(int i=0; i<sticker.size(); i++) {
colorTimes[sticker[i]] ++;
}
int available = 0;
for_each(q, colorTimes) {
// We can use at most 2 stickers of each color.
available += std::min(2, q->second);
}

return (available >= 6) ? "YES": "NO";
}
};


I wanted to use for_each at some second during the match then I noticed that I had to type it all, so I gave up and did some incredibly dumb stuff with a vector for absolutely no reason. This is the moment I decided to add for_each to KawigiEdit's snippets

Div1 900 CubeBuilding
Link to problem statement
There were only 20 minutes left, but I knew two things: a) I was clueless about 500. and b) The hard one was worth 900 points, which is quite a suggestion that it is easier than 500. In a way this problem was easier than 500 , at least for me.

The first impression I had about the problem is that it was a dynamic programming problem in which you had to remove dimensions as much as possible. This impression turned out to be true. However, I made plenty of mistakes while thinking of the logic for the problem and when coding the memoization. Of course 20 minutes was too little time for me to debug and rethink things. I solved this problem only after the match.

The initial idea was as follows:
a) You can split the main problem into three variations: a) All the visible cubes must be red. b) Visible cubes must be green. and c) Visible cubes must be blue.

When we want to count the number of ways to make all visible cubes red. Then we have R cubes of the correct color and G+B cubes of the wrong color. When counting cases in which all visible cubes are blue, there are B correct cubes and G+R wrong cubes. Same happens with the other case. So, what I did is generalize. F( good , bad, N) returns the number of ways to place good+bad cubes in a NxN board such that only the good ones are visible.

That division was mostly correct, but I eventually noticed that there was a vital mistake. The bad cubes actually may have two different colors. However, solving F(good,bad1,bad2, N ) may be too heavy so we need the optimization. The fix is to, once you have F( good , bad1 + bad2, N), then you can get Combinations( bad1 + bad2, bad1) as the total number of ways to to pick the colors of the bad cubes. And just multiplying F( good , bad1 + bad2, N) with Combinations(, bad1 + bad2, bad1) will give the total number of ways to do it for each color.

On to solve F(good, bad, N), we can split the board in N rows. For each row, we will place some cubes (good and bad) in a way that only the good ones are visible. Then we can proceed to the following row but the number of good and bad cubes may have been reduced. So, what if you could have a function G(good, bad) that would return the total number of ways to put good correct-color and bad wrong-color cubes in a single row? Since this function has a limited number of argument combinations, we could calculate the results for funtion G() before calculating F() which will remove some complexity from F().

So, for each row, pick a pair u, v of good and bad color cubes to place in the row , then proceed to the next row with a possibly-reduced number of good and bad cubes. Then the number of ways to have good correct cubes and bad wrong cubes in a NxN board by using (u,v ) cubes in the first row is: F(good,bad, N) = G(u, v) * F(good - u, bad - v, N-1).

This allows a simple recursion that can also be memoized.

We just need to solve G. Note that after we add some good cubes in the front cell of the row, then the rows behind the good cubes can have any color. The idea in here is to have a variable front which will be the number of cubes on the front of the current cell. For the first cell, there are no cubes on the front of it. If there are front cells on the front, then we can place bad cubes as long as their height positions are less than or equal to front. We can also place good cubes in a height position less than or equal to front AND also add new ones which will increase the front value for the next cells. This was something I have overlooked during the match. Also , for the cubes that are covered by the stacks from the previous cells, we can pick any order, which is important when there are good and bad cubes bellow the front margin.

From the last paragraph: If the previous cells on front of the current one have a stack of size front and we decided to pick v bad cubes and u good cubes to place in the current cell. Then v cannot exceed front, else a bad cube would be visible. The number of ways to place the cubes in this cell is Combinations( min(front, u + v ), v ) , because you can only pick locations smaller than or equal to front for the bad cubes. Then the number of good and bad cubes decreases whilst front may increase to u + v if it is larger (a new size of the stack). All of this is helpful when making a second recursion which is also memoization-friendly.

The total complexity is around O(A5*N) where A is the sum of R+G+B. It barely gets 1.8 seconds in c++, so I am not sure if there is a better solution.


typedef long long int64;
const int MOD = 1000000007;
struct CubeBuilding
{
int N;
int64 mem[26][51][26];
int64 mem2[26][51][107][26];

int64 C[101][101];

int64 G(int a, int b, int front, int n) {
// Returns the number of ways to place a+b cubes in
// n cells if the largest stack in a cell on front of
// them has size front. Such that only the a cubes
// are visible.
//

int64 & res = mem2[a][b][front][n];
if ( res == -1) {
res = 0;
if (n==0) {
if ( a==0 && b==0) {
res = 1;
}
} else {
for (int v = 0; v <= front && v <= b; v++) {
for (int u = 0; u <= a ; u++) {
int64 y = C[std::min(front,u+v)][v];
res += (y *G(a - u, b - v, std::max(front, v+u), n-1 ) ) % MOD;
}
}
res %= MOD;
}
}
return res;
}


int64 F(int good, int bad, int p) {
// Returns the number of ways to place good+bad cubes in
// all rows >= p of a NxN board such that only the good
// cubes are visible
//
int64 & res = mem[good][bad][p];
if ( res == -1) {
res = 0;

if(p == N) {
if ( good == 0 && bad == 0) {
res = 1;
} else {
res = 0;
}
} else {
res = 0;
// place cubes..
for (int u = 0; u<=good; u++) {
for (int v = 0; v<=bad; v++) {
int64 tot = G(u,v ,0,N) * F(good - u, bad - v, p+1);
res = (res + tot ) % MOD;
}
}
res %= MOD;
}
}
return res;

}
int getCount(int R, int G, int B, int N)
{
// Prepare combinations table using Pascal's triangle
memset(C, 0, sizeof(C));
for (int n = 0; n<=100; n++) {
C[n][0] = 1;
for (int k=1; k<=n; k++) {
C[n][k] = C[n-1][k-1] + C[n-1][k];
while(C[n][k] >= MOD) {
C [n][k] -= MOD;
}
}
}

memset(mem, -1, sizeof(mem));
memset(mem2, -1, sizeof(mem2));

this->N = N;
int64 res = 0 ;

//Red on front:
res += F(R, G+B, 0) * C[G+B][G];
//Blue on front:
res += F(B, G+R, 0) * C[G+R][G];
//Green on front:
res += F(G, R+B, 0) * C[R+B][R];

return (int)(res % MOD);
}
};


Challenge phase
What saved me was a lucky challenge. I found a person that in his 250 solution had something like: if ( number of unique colors >= 4 ) return "YES". At first I thought it was all right, but then I noticed a case with 3 repetitions of the same color and other 3 different colors. There are 4 distinct colors in total, but it is still impossible to do it.

The end result was a increment of 11 rating points, which is fine. But I need to return back to getting steady increases in the next match , if I want to defeat my maximum rating.

Monday, May 23, 2011

Thoughts after GCJ 2011 round 1

It is freaking google code jam. I'd say perhaps the most important tournament we have in regards to algorithm contests. Much larger than Topcoder. Not broken like ACM. It has an actually-well thought score / tie break system which is I guess inspired on IPSC and has problems that are usually at least half as interesting. Allows all free languages. Etc. Used to have a great number of advancers and rewards, but not anymore. It is kind of poor in those regards. Oh well.

Round 1A
I usually try not to advance during the first of the three round 1s. Because at the end you don't earn an advancer spot, you lose the chance to participate in other two matches. I also try not to fail round 1B though, because relying only on 1C is too risky. This year was different. I figured that this year it would have been very convenient to advance in round 1A. Because I had a important lunch on Saturday so I would not have been able to attend to 1B, and the schedule for 1C was... very inconvenient for me. 5:00 AM. I really intended to advance in 1A. It did not happen.

1A-A Freecell statistics
I initially tried many things related to doing fancy magic using modular stuff. Started off trying to solve the easy version. It had a small value of N so you could iterate from 1 to N for the number of rounds played that day. From then you would be able to guess if PD is possible. For a while, I tried to calculate the number of total rounds necessary to match everything once you had N, and (N*PD)/100. Using binary search and plenty of things. It was failing even the second example.

I noticed that the second example was pretty trivial (100% total rounds and non-100% rounds last day is impossible). Sometime during the implementation of the complicated, non-working solution it started to occur to me (what if there is always possible to have an appropriate total number of rounds provided that N*PD is divisible by 100?) It turned that it was almost true, you also needed to avoid mistakes when PG=0% or 100%. So, I gave it a try.

bool solve(int N, int pd, int pg) {
if ( pg == 100 && pd != 100 ) {
return false;
}
if ( pg == 0 && pd != 0 ) {
return false;
}

//D <= N
// (D*pd) % 100 = 0
for (int D = 1; D<=N; D++) {
if ( (D * pd)%100 == 0) {
return true;
}
}
return false;
}


It worked, so then I noticed that all that matters about number N is for there to exist an D <= N such that (N*D) is divisible by 100. If we use D=100, it will always be divisible by 100. So, we only need to try all Ds until 100. It solves even the ultra large cases. So, I modified my code and submitted the large version.

At the end of the match, I was very unpleasantly surprised to see the solution fail. I had already proven it so it made no sense. Then after some debugging using the practice inputs, I learned that I had made the most noobish mistake in the book. N can exceed 32 bits integers.

It led me to rethink many things. The error should have been very easy for me to find if I did something as simple as reading the output file before submitting it (All the results in that output were "possible"). I took some measures like making sure my upload script (see bellow) would show me the file before I decide to upload it.

Today I thought that I needed more protection. In retrospect this was a very silly mistake, because the overflow was in the input itself.

Template
If you were reading source codes from the contest, you will see that a lot of people solve the problem right away and the input/output part of the program is not separate from the program itself. In part this may be because it is much easier to code that way. The resulting code turns very small which gives it certain level of glamour when people new to contests read it.

On the other hand, I cannot stand doing it. I don't like having I/O mixed with program logic, so I split the two. The solver is usually a function the I/O part calls after doing all the reads. So I keep the skeleton of the code in a template.

    init();
int TestCases;
cin>>TestCases;

for (int _i=1;_i<=TestCases;_i++)
{
/* read input goes here */

if( (mode==0) || ( (mode!=2)== (_i*2<=TestCases) ) )
{
cerr<<"["<<_i<<" / "<<TestCases<<"]"<<endl;
/* program call goes here */
cout<<solve()<<endl;
/* output result goes here */
cout<<"Case #"<<_i<<": ";
}
else if(mode!=2) break;

assert(cin);
}


One of the advantages is that keeping the algorithm in a separate function makes it slightly easier to replace the algorithm without modifying the I/O stuff. Then there is the other advantage and it is that my template is dual-core capable. That is where the if( (mode==0) || ( (mode!=2)== (_i*2<=TestCases) ) ) stuff comes from. When I need to use both cores (when the solution is slower than 8 minutes but not slower than 14 minutes). It is easy to split the
test cases in two using the template and then run both copies at the same time.

What I just did was add this line to my template after a test case is processed: assert(cin);. It actually detects the overflow when you have a lame mistake like the one I had during 1A. Using cin as a boolean is overloaded in a way that makes it return true if everything was ok when reading it so far or false otherwise. So, if at some point in the file you have cin>>x. x is a 32 bits integer and the x in the file is a large number 2729290020282, cin will consider it a mistake and the next time you do assert(cin) the program will fail.

1A - B - The Killer Word
It seemed easy to do B-small through just simulation, and in a way it was, but I had a failed submission. It took me a long time to notice the bug in my code. It was that when the guessed letter is wrong, all the words with that letter have to be ignored from then on. Then the other mistake was that when you guess 's' and get "s__s_s", you also need to ignore words like "sussus" because the s don't fully match the positions. It was a long time to debug B. But the scores were such that I was very confident I was going to qualify thanks to finally solving B-small. Of course, I didn't count on failing A-large...

To me it was clear that B-small was harder than A-small and A-large combined, so 10 points seemed small in comparison to A's total 20.

1A - B - (large)
I think my mistake was to stick with C-small even though I didn't have any actual idea about it, yet B-large seemed to have some important ideas behind. I was trying to find an algorithm that would calculate the wanted words for all the alphabets simultaneously. Whereas the solution was actually to do it for all the words simultaneously. It is a very clever solution. Even though the contest analysis is kind of vague, it eventually just works.

The idea is as follows:
* Solve B-small by simply repeating this for every alphabet:
** For every word, calculate the score the other player would get. To do it, just keep a list of all the dictionary words, and simulate the game, at every step remove all the words that do not match the resulting pattern. (Do not forget to remove words with letters that failed in your guesses, also consider removing words that are inconsistent with the pattern : For example, the "sussus" case I mentioned above.
* Pick the word with the best score.
To solve B-large. We do the process for all words at the same time. For example, if you started with words "xxxx" or "yyey", then the first pattern would be "_ _ _ _". This means that before the first turn, you cannot differentiate one of the words from the other.

As you proceed with the game, we will eventually ask if there is an e in the word. Then for xxxx, the pattern will not change and you will get a penalty, but for "yyey", the pattern will change to "_ _ e _". This means a bifurcation. Suddenly, the words do not belong to the same class anymore.

The same happens for example with "aaa", "bab", "dddd", "dddx". At first, there are two classes: "_ _ _" and "_ _ _ _". Let us say the alphabet begins with character "a". For class "_ _ _", it makes sense to ask for letter a. Then if the word was "aaa", the pattern will become "a a a", and you won, but else the pattern will become "_ a _". For class "_ _ _ _", there is no need to ask for "a", because none of the words that begin to that class contain a.

The advantage of this is that for every letter in the alphabet. You will need to process each word in the list exactly twice. Once, to verify if the word has the letter and another time to calculate its new pattern. In total the complexity become O(N * |L|). Which is great.

#define for_each(q,s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
using namespace std;

//=========================================================
// program:
//
int N, M;
string dictionary[10000];
string list[100];
string result[100];

map<string,int> dictpos;

//A group/class of words. All the words that match a given pattern. They
// all share the same score.
struct words {
int score;
string pattern;
vector<string> dic;

words( string p, int sc) {
score = sc;
dic.resize(0);
pattern = p;
}
words() {}
};

//Should we use letter ch as a guess for a certain pattern if it contains word?
bool shouldUse(char ch, const string& pattern, const string& word) {
for (int i=0; i<word.size(); i++) {
if ( (word[i] == ch) && (pattern[i] == '?') ) {
return true
}
}
return false;
}

map<pair<int, string>, int> patternIndex;

// Adds a word to an appropriate element of vec matching (pattern,score)
void addWordPattern( const string& pat, int score, const string& word, vector<words> & vec ) {
int x = 0;
pair<int,string> key = make_pair(score, pat);
if (patternIndex.find(key) == patternIndex.end() ) {
x = vec.size();
vec.push_back(words(pat, score));
patternIndex[key] = x;
} else {
x = patternIndex[key];
}
vec[x].dic.push_back( word );
}

// Updates the pattern after a guess ch when the word is "word".
string simulateStep(char ch, const string & word, string pattern)
{
for (int i = 0; i < word.size(); i++) {
if ( word[i] == ch ) {
//The guess was correct, update
pattern[i] = ch;
}
}
return pattern;
}


string solve(const string & L) {
//The patternIndex map just remembers the correct index for a given
// (pattern,score) pair.
// wordPartitions is a vector that holds all our word classes, we need
// patternIndex to know the correct positions in the vector. We only
// use two indexes of it at any time to save memory (probably not necessary).
// wordPartitions[i%2] holds the classes before L[i] is processed.

patternIndex.clear();
vector<words> wordPartitions[2];
//init
for (int i=0; i<N; i++) {
string pat( dictionary[i].length(), '?');
addWordPattern(pat, 0, dictionary[i], wordPartitions[0]);
}
for (int i=0; i<26; i++) {
int cur = i%2, nxt = (i+1)%2;
wordPartitions[nxt].resize(0);
patternIndex.clear();

for_each(q, wordPartitions[cur]) {
//should L[i] be used?
bool use = false;
for_each(s, q->dic ) {
use |= shouldUse(L[i], q->pattern, *s);
}
if ( use ) { //test it.
for_each(s, q->dic ) {
string newpattern = simulateStep(L[i], *s, q->pattern);
int score = q->score;
if (newpattern == q->pattern ) {
// The guess was not correct
score --;
}
addWordPattern(newpattern, score, *s, wordPartitions[nxt]);
}
} else {
// Do nothing
for_each(s, q->dic ) {
addWordPattern(q->pattern, q->score, *s, wordPartitions[nxt]);
}
}
}
}
//After all the letters in the alphabet are used,
//each class will match a word in the dictionary..
// Use the dictpos map to remember the position of the word in the dictionary
// (for tie breaking).
pair<int, int> best = make_pair(1,0);
for_each(q, wordPartitions[0]) {
best = std::min(best, make_pair(q->score, dictpos[q->pattern]) );
}
string res = dictionary[best.second];
return res;

}

void solve() {
dictpos.clear();
for (int i=0; i<N; i++) {
dictpos[ dictionary[i] ] = i;
}

for (int i=0; i<M; i++) {
result[i] = solve(list[i]);
}
}




Round 1B
So, all my plans trembled after the failure in 1A. I didn't have enough time to go through all of Round 1B. Only the first half of its scheduled time. I decided to try it anyway, because the 5:00 AM match involved plenty of risk. In theory, all that is necessary to advance is A-small, A-large and B-small, and I thought it was perfectly doable to do them in 75 minutes.

1B - Problem A
This problem was very easy actually. You just need to implement the formulas as they say. There is a catch in that naively implementing them will probably end up calculating the same value plenty of times. You can do memoization or something to avoid doing such calculations. But I think even without optimizations, it passes.

It surprisingly took me 18 minutes to implement. I am not sure how it happened. I did take around 4 minutes triple checking everything before doing A-large, I was not going to make the same mistake as round 1A.

1B - Problem B
This was harder. Even B-small seemed non-trivial at first. Anyway, I began noticing that although the result is a double, you will at most always need only multiples of 0.5. Multiplying every number by 2, calculating using only integer for target positions and finally dividing the cost by 2.0 solves the problem.

I came up with a dp that takes advantage that the total length of the street is not actually very long and there are only at most 100 vendors. For any meter x in the street, you can decide to place a vendor, or you may not. If you place a vendor, you have to skip to x+D because you cannot put any vendor between that space.

Calculating the total extra street size necessary required me to do some guesses. Like you need at most D*N meters to the left and to the right of the extreme initial points of the vendors.

I passed, and it was still 1:04, I was happy. Because that was all that I needed - A-small, A-large and B-large. Plus I knew A-large was correct. My prediction was correct, If I left the match at that moment, with only A-small/large and B-small I would have gotten position 794. But ... I made the mistake of actually reading C out of curiosity. It seemed very complicated at first, with geometry and a complex problem. Then I noticed that the constraints for C-small were very small.

* * * DARN * * *
The solution for C-small came to me : All I needed was a way to recognize the small closed polygons. And then a bruteforce algorithm to assign the colors so that each polygon has one of the colors and I find the combination that works best. With N=8 all of that was pretty possible.

For some reason, I thought that it should be possible to implement those things on time. Perhaps I would get delayed by a couple of minutes, but it was doable.

It was not. I ended up taking 30 minutes on it. So I was late to the launch by about 20 minutes. While coding I knew it was late and it forced me to rush which forced me to add new mistakes. Once I debugged my code and I was ready to submit, I thought to myself "ok, if this is not correct, we leave anyway" (I talk in first person plural when talking to myself). Fortunately, it passed.

The bright side was that with the addition of C-small to the equation I was VERY sure I would advance. So I was able to be calmer at the lunch.

How did I find the polygons in 1C?

It was easy. N<=8 gives you plenty of freedom. You can just do a bruteforce for all the subsets of corners. If there is a path that connects them with exactly T edges (such that T is the number of elements in the subset), they form a polygon. If the subset contains a smaller subset that is also a polygon, ignore it, because you are only interested in the rooms, which are minimal polygons.

I actually did it differently, I counted all the walls that connected vertices in the subset. They have to be EXACTLY T. And it works too.


The GCJ command line tool
The command line tool is probably the best improvement to the Google code jam experience since.. 2008? I implemented it and practiced with it a little before round 1. And it was a time after 1B that I noticed why it really is a good thing. It is not because of the time you save dealing with firefox, telling it where to save your input files and where to get your output files from.

The real advantage is that it makes you unable to upload the wrong source code or the wrong output. (As long as you don't mess the names of your files, I guess).

It does have some issues, like very large file names for its scripts. But it is just easy to make shortcuts. I made a single gcj.sh script which takes parameters like "init 24553" , "down A small 0" or "up B large 1" and does all the magic. I also adapted the source code of the tool so that it uses ANSI colors when telling me things like "Correct" or "Incorrect", makes life easier.