Friday, April 26, 2013

Google codejam round 1A: Nice

That was nice, rank 29-th is most likely my best rank ever in a GCJ round that is not the qualification one.


Preparation

I improved my multithreaded template. It now has much less overhead and uses proper Unix threads.

Problem A - The one with math

Link to statement

It must be a miracle that one ml of paint is good enough to paint exactly π cm2. This makes it so, the amount of paint needed to paint a black ring of larger radius R and smaller radius r is exactly: R2 - r2.

This problem is a constructive one. Do it step by step.

We want to find the maximum value of x such that: t >= costToPaint(x). Where costToPaint(x) is the cost to paint x black rings. The value of x can be very large, but it does not matter, because we can use binary search.

So the new problem is to find a quick way to calculate costToPaint(x), in order to solve the large input, we need o(x) time (Note that this is small-o notation, not big O). Let us look for a O(1) one...

The first black ring needs ( r + 1 )^2 - r^2, the second one needs ( r + 3 )^2 - (r + 2)^2, the third one (r + 5)^2 - (r + 4)^2 and so and so. We need to find the sum for 1 <= i <= x of :

( r + 2*i - 1 )^2  - ( r + 2*i - 2 )^2

Sounds difficult? Not really. Let us get clever and...

(r + 2*i - 1)^2  - ( (r + 2*i - 1) - 1 )^2
Then...
 = (r + 2*i - 1)^2  - (r + 2*i - 1)^2 + 2*(r + 2*i - 1) - 1
 = 2*r + 4*i - 3
 = (2*r - 3) + 4*i
...

sum(1 <= i <= x, (2*r - 3) + 4*i ) = (2*r - 3)*x + 4*x*(x+1) / 2

So we just need to find (2*r - 3)*x + 2*x*(x+1)

Be careful with overflow... I actually took most of those 40+ minutes being perhaps too careful about it...

long r, t;
// we only need to know if the result of f(x) is greater than t,
// so if we surpass INF, we can just stay there...

long mul(long a, long b)
{
if (a >= INF / b) {
return INF;
}
return a*b;
}
long add(long a, long b)
{
if (a >= INF - b) {
return INF;
}
return a + b;
}
long f(long x)
{
// sum 1 <= i <= x : 2*r + 4*i - 3
// = (2*r - 3)*x + 4*x*(x+1) / 2
// = (2*r - 3)*x + 2*x*(x+1)
// = x * (2*r - 3 + 2*x + 2)
// = x * (2*r - 1 + 2*x) // 2*r is at least 2
return mul(x, add(2*r - 1, 2*x) );
}

long solve()
{
// max x: t >= f(x)
long hi = t + 1, lo = 0;

while (lo + 1 < hi) {
long ha = hi - (hi - lo) / 2;
if ( f(ha) <= t) {
lo = ha;
} else {
hi = ha;
}
}

return lo;
}

Problem C-small the one with guessing

Link to statement

Is GCJ jumping the shark? They seem to be trying unusual stuff too much lately. Ok, it is fun though. It reminds me of IPSC, and IPSC is just the best yearly contest ever.

My approach was to find every possible combination of cards (order does not matter), and find the probability that such setting happens. Then, for each list of products, try each combination of cards and calculate the probability that IF the card combination was picked, the products are those. After doing all that, pick the combination of cards that has the best total probability (Probability to get the combination) * (Probability to get the product). This got correct in the first try.

Problem B - the one with the schedule and energy

Link to statement

I estimated that as long as I solved B-small I would likely advance, so I focused on the easy problem instead of spending time in the large one.

At any point, you have between 0 and E energy, so you can never spend more than E energy in any activity. In the small input, E is at most 5, and the number of activities is at most 10, so brute force for the amount of energy you spend in each activity is good enough. 510 choices in the worst case.

int E, R, N;
int v[10];

int solve()
{
vector<int> spend(N, 0);
int best = 0;
while (true) {
//cout<<"="; for (int i=0; i<N; i++) cout << spend[i]; cout<<endl;
// simulate
int e = E;
int gain = 0;
for (int i = 0; i < N; i++) {
int s = std::min(e, spend[i]);
gain += s * v[i];
// I had min(e, e - s + R) instead of min(E, e - s + R) :(
e = std::min(E, e - s + R);
}
best = std::max(best, gain);

// next choice
int j = N - 1;
while (j>=0) {
spend[j]++;
if (spend[j] > E) {
spend[j] = 0;
j--;
} else {
break;
}
}
if (j < 0) {
break;
}
}
return best;

}

C small 2

After solving that B-small, I wanted to solve more. I could spend my remaining 40+ minutes in B-large, or the harder C-small. C-small-2 has many advantages, it gives more points, and since it is a small input, you will be able to know for sure if you when you got it correct. I also had a sudden idea for C...

It turns out that:

a) My generation of combinations was slow, it is possible to generate the combinations (sorted) directly and then calculate their probabilities.

b) Plenty of combinations are unlikely, you can consider the X combinations with the largest probabilities such that the sum of their probabilities is something large. At first I tried 0.5, but apparently it wasn't large enough. At the end I tried 0.99, ignoring the improbable combinations that add up to 0.01 probability is actually a significant optimization. And this omission will reduce your success rate only by 1%. The success rate has to be about 1/8 in C-small-2.

My first attempt was a time out. It turns out that my approach was not fast enough. I found a way to precalculate the product probabilities for each combination, so that I only needed an O(K) loop per combination per list of products. Second attempt was wrong (0.5 is apparently not good enough). Third attempt: I noticed that 0.99 is good and fast. Correct!

Incidentally, I needed 1.5 minutes to run the final solution. If not for multi threading, I may have needed 5 minutes or more...

int cardProduct[7];

string curr;
double fact[13];
double TOTAL;

set< pair< double, string> > possibility;
set< pair< double, string> > probable;

map<string, map<int, double> > probableProduct;

void rec(int x, char ch)
{
if (x == N) {
// calculate the probability
double p = fact[N];
int i = 0;
while (i < N) {
int j = i;
while ( (j < N) && (curr[j] == curr[i] ) ) {
j++;
}
p /= fact[j - i];
i = j;
}
p /= TOTAL;
possibility.insert( make_pair(p, curr) );
} else {
for (char b = ch; b <= '0' + M; b++) {
curr[x] = b;
rec(x + 1, b);
}
}
}

void init()
{
TOTAL = 1;
for (int i=0; i<N; i++) {
TOTAL *= M - 1;
}
fact[0] = 1;
for (int i=1; i <= 12; i++) {
fact[i] = i * fact[i-1];
}
curr = string(N, '?');
rec(0, '2');
double P = 0.001;
for_each(q, possibility) {
P -= q->first;
if (P < 0) {
probable.insert( make_pair(q->first, q->second));
string x = q->second;
map<int, double> product;
for (int i=0; i<(1<<N); i++) {
int p = 1;
for (int j=0; j<N; j++) {
if (i & (1<<j)) {
p *= x[j] - '0';
}
}
product[p] += p / (double)(1<<N);
}
probableProduct[x] = product;
}
}

}

string solve()
{
pair<double, string> best = make_pair(-1.0, string(N,'2') );
for_each( q, probable) {
string x = q->second; //a combination of cards
double p = q->first; //probability to get those cards
//calculate the probability to get each product
map<int, double> & product = probableProduct[x];
// probability to get all K products
for (int i=0; i<K; i++) {
if ( product.count(cardProduct[i])) {
p *= product[ cardProduct[i] ];
} else {
p = 0;
}

}
best = std::max( best, make_pair(p, x) );

}

return best.second;
}
void read() {

TCO 2B editorial complete, SRM 577

TCO 2B editorial "complete"

You can find it here: http://apps.topcoder.com/forums/?module=Thread&threadID=787652&start=0&mc=1#1723854.

This was a long problem set to solve and explain hence the long time to finish it. I am still going through health scares but I think this one took so long primarily because I needed time to solve it. Specially the medium. Very interesting match, but I wish I would do better in tournaments.

SRM 577 - fail

In SRM 577, I first opened the 500, seemed interesting, but when some coders started to solve the hard problem before there were submissions for 500, I decided to open it. This hard problem really distracted me. I had a very strong feeling there was a flow solution, but I couldn''t put things together.

As usual, when there were 10 minutes before the end of the challenge phase, I opened the 250 points problem. I rushed to code something that was wrong. The bug that distracted me for most of the 10 minutes was that I calculated the expected sum of scores, and not the expected average of scores. When the coding phase finished, I noticed there was still a mistake, I was not handling the possibility that Elly could have a room of different sizes depending on luck.

To solve it, find the probability Elly ends in a room with t or t+1 people (Where t is N/R). For each case, find the average score. Combine results and done.

Thursday, April 25, 2013

TopCoder Open 2013 round 2B, LitPanels editorial

The editorial for the 1000 points problem is in a state that I can pass it around. Everything is a WIP right now, but it should be readable. Find it here: http://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2B#LitPanels

My intention was to finish all the editorial today, and it still is. However, I am going through the oddest, most bizare headache and it is driving me crazy. As opposed to a hurtful headache that lasts a couple of hours, it is the most mild headache I ever had, but it is going on for days. Everything else in my body seems fine, but this thing is very unsettling. It is actually amazing how your mind reacts to things. I was very used to headaches that are very awfully strong, I had them for most of my life and could work and concentrate well while having them, because I know them. This new headache is so strange to me, that even though it is very mild it is really a bother.

About the problem, it seems rng_58 upped his game for the TCO problem sets. This contest was very cool (and difficult to me), this problem is in a way very simple, yet at the same time very interesting and was only solved by two coders during the match.

Tuesday, April 16, 2013

SRM 576 div1 900: CharacterBoard Editorial

It is up: http://apps.topcoder.com/wiki/display/tc/SRM+576#CharacterBoard

As you can see, it is rather short. The problem itself is not so hard once you solve the div2 version. The optimization is quite interesting too. Nice one.

Sunday, April 14, 2013

SRM 576: Editorial for div1 576: TheExperiment

It is up: http://apps.topcoder.com/wiki/display/tc/SRM+576#TheExperiment

The initial plan was to have it finished Yesterday, but the Google Codejam turned out to be a bigger distraction than planned.

To be honest, the stress-caused symptons are still making my life a bit hard. But I seem to be improving. Let us go on to solve that div1 900.

Saturday, April 13, 2013

Google Codejam 2013 Qualification Round

Starting to write this 4 hours before the contest ends, I might be away of the keyboard until the time it ends, so I think this is it, no more solutions from me. I am a bit downed because my C-large 1 will fail because of an overflow bug...

Preparation

I did many things to prepare to this round. The usual ones were to set up the gmp library. It allows c++ to have arbitrary precision, and if you use a "typedef mpz_class big", the bignum support of c++ becomes one of the best you can find. This is a measure to shut any attempts to pull artificial difficulty or to brag about how some problems are not as good to be solved by C++ (lies, just get the right library, C++ always wins for contests, </extremist> ).

Last week, on Saturday I bought a precious CPU/Motherboard/RAM upgrade. I jumped from Core 2 Duo to an Ivy Bridge Core i5. In codejam, your processing power matters. Well, processing power is always useful for programming contests, because it speeds up your local testing. In the case of codejam, it can be a game changer. I quickly learned that the average algorithmic program takes half the time it used to take in my old Core 2 Duo. Also, I now have four Cores instead of two, if I somehow manage to use them all...

I had plenty of reasons to update my codejam template. The old template supported two processes, but it was a very rudimentary support - It split the input file in two, and ran a process on each half. With time I found it was not very effective, because usually one of the halves had a lot more processing needs than the other. Most of the times, I ended with a process finishing its job quickly and the other still taking quite some time. The other issue with the old template is, of course, that it only supported 2 processes, I need 4 processes so that I use all my CPU cores.

From experience out of TopCoder Marathons, I was able to finally make a template that creates three extra processes. Each process has to read the input entirely (This is a flaw that adds overhead, but is sort of needed not to complicate the problem, there are too many different ways a problem could need input/output). For each read case, the process verifies if it is taken by any of the other four processes, if not, starts solving the case. The main process then joins all the results together once they finish.

As I did this (around 2 hours before the contest), I noticed that C++0x has actual thread support, there are hopes I might be able to optimize this in a way that does not need four processes, but four threads, but that's work for another day.

I also had to set up the codejam command line tool. After the first time I failed a small input because I submitted the wrong output file, it became clear I needed to automatize things.

Problem A - Tic-Tac-Toe-Tomek

Link to problem statement

So it is a 4x4 tic tac toe variation which begins with a single T (as opposed to X and O, the players' symbols) which acts as a wild card (It can be part of the winning line).

A pure implementation problem, you just need to be able to detect if anyone won. If no one won, then the game finished in a draw as long as there are no empty cells.

I think I took way too much time to solve this. I tried to be clever and made a function to quickly verify a line. Unfortunately, this cleverness brought a silly bug that leeched away precious time in debugging.

char board[4][4];
int sign(int x) {
return ( (x == 0) ? 0 : (x / abs(x) ) );
}
// Checks if a line has 4 player cells or 3 player cells and one T.
// Coordinates of the cells in the line are:
// (x0,y0), (x0+sx, y0+sy), (x0+2*sx, y0+2*sy), (x0+3*sx, y0+3*sy)
// Where sx = sign(x1 - x0), sy = sign(y1 - y0).
bool lineCheck(int x0, int x1, int y0, int y1, char p) {
map<char, int> c;
int y = y0;
int x = x0;
for (int i=0; i< 4; i++) {
c[ board[x][y] ]++;
x += sign(x1 - x0);
y += sign(y1 - y0);
}
return (c['T'] + c[p]) == 4;
}
string solve() {
// count empty cells:
int e = 0;
for (int i=0; i<4; i++) {
for (int j=0; j<4; j++) {
e += (board[i][j] == '.');
}
}
// Find out if any player wins:
bool wins[2] = {false, false};
string p = "XO"; // for i=0, check X, for i=1 check O
for (int i=0; i<2; i++) {
// diagonal
wins[i] |= lineCheck(0,4, 0,4, p[i]);
// anti diagonal
wins[i] |= lineCheck(3,-1, 0,4, p[i]); //My mistake was 4,0 instead of 3,-1
for (int j=0; j<4; j++) {
//horizontal lines (four of them):
wins[i] |= lineCheck(0,4, j,j, p[i]);
// vertical lines
wins[i] |= lineCheck(j,j, 0,4, p[i]);
}
}
if (wins[0]) {
return "X won";
} else if (wins[1]) {
return "O won";
} else if (e > 0) {
return "Game has not completed";
} else {
return "Draw";
}
}

Problem B - Lawnmower

Link to statement

How about you read the statement so that I don't have to explain it?

Ok... There is one thing to understand. For each row, find the maximum height in that row. We can clearly just run the mower on that row with that maximum height as setting. The heights of all grass squares in that row will either become exactly what the pattern wants them to be, or a larger height (which we can cut by using another mower run).

Then we can do the same about columns, run the mower using a height setting equal to the maximum height in that column.

If we did any different kind of move. If we ever used a setting smaller than the maximum of a row or column, we would definitely have a wrong pattern. Some grass squares (the ones that are supposed to be equal to the maximum height of the column/row) would become smaller than what you wanted.

If after doing these moves for each row/column, the pattern is not equal to what we wanted, it should be impossible to do it.

The solution is then to verify. Each cell must be either equal to the maximum height of the column that contains the cell, or the maximum height of the row that contains the cell. Else it would not be possible to do it.

int N , M;
int a[100][100];
string solve( ) {
int rowMax[N];
int colMax[M];
// Find the maximum for each row:
for (int i=0; i<N;i++) {
int mx = 0;
for (int j=0; j<M; j++) {
mx = std::max(mx, a[i][j] );
}
rowMax[i] = mx;
}
// Find the maximum for each column:
for (int j=0; j<M; j++) {
int mx = 0;
for (int i=0; i<N; i++) {
mx = std::max(mx, a[i][j] );
}
colMax[j] = mx;
}
//Verify:
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if ( (a[i][j] < rowMax[i]) && (a[i][j] < colMax[j]) ) {
return "NO";
}
}
}

return "YES";
}

Problem C - Fair and Square - Small

Link to statement

Since B is at most 1000, we can just do a straight forward check. For each integer between A and B, verify it is palindrome, find its square (if it exists) and verify if the square root is palindrome too.

I decided to skip the large inputs, I noticed that you only need the four small inputs to be correct in order to advance to round 1. So I rushed that objective.

Problem D - Treasure - Small

Link to statement

Ouch. This is a problem I wanted to write since a long time ago. My inspiration for this sort of riddle about Interchangeable Antimatter Keys, comes from Xye. Tutorial 10 has a puzzle about choosing the right order to use the keys, but it was more complicated.

Ok, let us focus on the small input. The number of chests is at most 20. This is too large for us to just try a brute force of the 20! different permutations, but it is not too large for another approach that is also a bit standard...

Let us say you have opened a set of chests. Once you opened the chests, the order in which you opened the sets does not matter, only which of the chests you opened. From a single bitmask from 0 to 220-1, you can find out which chests were opened and calculate the number of keys of each type that you currently have (Sum between initial keys and the keys inside the chests you opened minus the keys needed to open all of the chests). When you know which keys you have, you know which of the chests you can open.

Let us just use dynamic programming. Make a function f(mask) that returns the lexicographically smallest order of the chests that are inside the mask, assuming that we have already opened the other sets.

f(0) is an empty vector, we have already opened all the chests, so the remaining chests are an empty set. This is the base case.

In any other case, calculate the number of remaining keys of each type. Then for each chest that can be opened, find out what would happen if we open it. For chest j, the solution of the remaining chests after opening j will be f(mask - (1<<j), if this solution exists, then we can append j to the front of the solution, and we now have a possible solution for f(mask), pick the lexicographically smallest one.

Overall result is: f(111111...1) (base 2, as many 1s as bits).

int N, K;

int initialKeys[40];
int chests[20][40];
int chestKeys[20];
int chestType[20];

vector<int> mem[1<<20];

void solve( ostream& cout ) {
// base case:
mem[0] = vector<int>(0);
const int INF = N*(N + 1);
// Try each of them:
for (int mask=1; mask <(1<<N); mask++) {
// A single element containing infinite is our way to mark a state
// as having no possible solution.
mem[mask] = vector<int>(1, INF);

// Count the number of keys of each type:
map<int, int> keys;
for (int i = 0; i < K; i++) {
keys[ initialKeys[i] ]++;
}

for (int j=0; j < N; j++) {
if ( !( (1<<j) & mask ) ) {
keys[ chestType[j] ]--;
for (int k = 0; k < chestKeys[j]; k++) {
keys[ chests[j][k] ]++;
}
}
}
// don't worry, if any number of keys is negative, this state will
// never be reached from an upper state, so its result would not matter
for (int j=0; j < N; j++) {
if ( (1<<j) & mask ) {
if (keys[ chestType[j] ] > 0) { // We can open chest j.
// Find out what happens if we open chest j:
vector<int> other = mem[ mask - (1<<j) ];
// If there is a solution, append j:
if ( (other.size() == 0) || (other[0] != INF) ) {
vector<int> nw( other.size() + 1);
nw[0] = j+1;
for (int i=1; i<nw.size(); i++) {
nw[i] = other[i-1];
}
// Remember the best solution so far.
mem[mask] = std::min( mem[mask], nw) ;
}
}
}
}
}
// Result is f( (1<<N) - 1):
vector<int> &res = mem[ (1<<N) - 1];

if (res[0] != INF) {
cout << res[0];
for (int i = 1; i < N; i++) {
cout << " "<<res[i];
}
} else {
cout << "IMPOSSIBLE";
}
cout << endl;
}

This is when the preparations I made started to fall down. The command line tool does not work for problems above the small input of problem C, because of the unusual way problem C works (two large inputs).

C - large 1

So I advanced, but I have a reputation to maintain and I cannot afford having a low score...

This is when I noticed that 1014 is not so large. The square root of the numbers between 1 and B will be at most 107, since the numbers must be perfect squares, we only need to iterate through the possible square roots. For each number between 1 and 107, find if it is palindrome, then square it, if the square is palindrome and the square is between A and B, then you got a solution.

So I downloaded the first large input. My processes, even with 4 cores were taking too long to solve it. I didn't notice that although Large 2 has 1000 input cases, large 1 has 10000 input cases... That is too much. I shut down the execution after 2 minutes. I had 6 minutes to make a faster solution and to submit it. It was difficult , but I was able to do it.

You only need a run from 1 to 10000000, to find out all of the "Fair and Square" numbers from 1 to 1014, there are actually just a few of them, 39 (if I remember correctly), so you can just keep them in an array and then, when requested the result for A and B, look through the array and count the numbers between bounds

C - large 2

I tried to think of ways to adapt the previous idea to numbers of 100 digits.

For example, since the square root must be a palindrome, then you can also brute force for the first half of the palindrome number. There are about 1025 ways to find the first half of the palindrome square root. It is still too large.

Hours later, it finally occurred me a way to fix this issue. Clearly, from what I could see from the 1014 solution, there are very few fair and square numbers. Why is it?

I then did something clever, I made the program show not only the fair and square numbers, but also their square roots. I noticed something interesting. Besides of 3, all of the other square roots were composed only of digits 0, 1 and 2.

If this rule is true, then the solution just became faster. There are about 325 different ways to make the first half of the square root.

This solution was still a bit slow to run, even if I managed to split the work load in 4.

The question is, why should the digits be only 0,1 and 2? Well, imagine that you have a palindrome number, and you square it. That the square is palindrome as well would be quite strange... For the initial symmetry not to get lost, there would have to be no carriage in the multiplication. Whenever there is a 3 digit or higher (except when there is only one) there must be a carriage operation (Because as it is a product between a palindrome and itself, all combinations of digits will be used).

Most importantly, if a half of a string causes a carriage operation , then any other half of a string that adds any digits to it will also have a carriage operation. We can crop the search.

After cropping the search, even for B=10100, the search takes little time to run. So we can solve the problem.

I wonder if there is any mistake in this analysis, I might find out later when it turns out that my solution is wrong.

// I told you c++ can do big nums:
// http://gmplib.org/
#include "gmpxx.h"
#define big mpz_class
struct solver
{

big A, B;

char x[100];
char y[100];

bool palindrome(string s)
{
int i = 0, j = s.length() - 1;
while (i < j) {
if (s[i] != s[j]) {
return false;
}
i++; j--;
}
return true;
}
int theCount, lim;

void find(int len, ostream& cout) {
// We try each string of 1,2 and 0 digits as the first half of the
// palindrome.
// Make them, and then raise that result to square. If the result
// is a p
bool good = ( len == 0 ) ;
if (len > 0) for (int k = 0; k < 2; k++) {
//There are two palindromes that have this first half.
// For example, for 12 : 1221 and 121.
// So each value of k tries one of them.
int l2;
if (k == 0) {
l2 = len*2 - 1;
} else {
l2 = len*2;
}
for (int i=0; i < len; i++) {
y[i] = x[i];
y[l2 - i - 1] = x[i];
}
y[l2] = 0;
// The square of the palindrome, if it is within limits:
if ( 2 * l2 - 1 <= lim) {
big z(y, 10);
big w = z * z;
// w must be also within limits.
if (w <= B) {
if ( palindrome(w.get_str()) ) {
// We should only continue if at least one of the palindromes
// has no carriage in its square.
good = true;
if( A <= w) {
// within range, count it.
theCount++;
}
}
}
}
}
if(! good) return;
// Only add 0 after the first digit.
if (len != 0) {
x[len] = '0';
find(len + 1, cout);
}
x[len] = '1';
find(len + 1, cout);
x[len] = '2';
find(len + 1, cout);
}

int solve(ostream & cout)
{
lim = B.get_str().length();
// Special case, 9 is the only one with a square root that contains
// 3 as a digit:
theCount = (A <= 9 && 9 <= B);
find(0, cout);

return theCount;
}

After I implemented this, I had a big issue, my results for C-large1 with this new solution were not correct against the previous C-large1 solution. So maybe there was a mistake in the analysis? After a lot of dribbling, I found out the sad truth, my first C large solution had a very silly overflow bug. I cared about using 64 bits integers in most of the problem, but I forgot them in the set<> structure that saves the precalculated results, making everything else worthless.

GMP was very useful indeed.

D - large

Sorry, I couldn't do it.

I tried a max flow idea, but it was wrong, it has nothing that prevents cycles.

At the end, what we want is to make a forest out of all the keys. Each key can have the keys of at most one chest as its children. The initial keys have to be the roots. Can we make such a forest? No, really, can we? I have no idea how.

I am finishing this write up at 17:10, the post shall appear automatically at 20:00. Let us see if there are any surprises, I know I fail the first C-large because of overflow, but I might fail the other larges too :/-