SRM 531: "challenging"

What a match to fail the SRM, I am not even sure my 300 is going to survive.

Div1 500: The one with the matrix product
There is initially one bunny of type 1. Every day all the bunnies die, but when a bunny of a certain type dies, a group of bunnies of different types is created. There are at most 50 types.

According to the statement, two outcomes are possible: Even the number of bunnies will eventually become constant and not change, or the number will grow infinitely. It is impossible to ever have less bunnies.

So, if the number grows infinitely, return -1. Else return the constant number modulo 1000000007.
-----
The easy part is to know that you can simulate the creation of bunnies in logarithmic time by using a linear recurrence. Make sure to read bmerry's article: linear recurrences.

IF you use a high enough number as the number of days to wait before calculating the total number of bunnies, you will be able to get the result.

The problem is how to detect cases that grow infinitely. A lot of 'clever' tricks like the ones I tried during the match (Take some random high exponents and compare). Will fail easily if the challenger is smart enough to make a case in which the result is a multiple of 1000000007. I thought of this during the match, but thought that it was going to be very hard to do it. I guess not. Kudos to ainu7.

I resubmitted once after I found an easy way to break my initial 'clever' try. Still, I failed for the aforementioned multiple of 1000..7 issue...

Div1 300: The one about songs and play lists
A music player generates a playlist of P songs. There are N songs available. A condition: Each of the N songs must play at least once. The number of songs between two equal instances of the same song must be M.

It seems dynamic programming is a clean approach here. The complication is how to deal with M. Well, imagine that you just played a song. You will have to wait M+1 turns to be able to play that song again, right?

Keep in mind, a variable called extra and a variable called mustPlay. At some point of the play list, you have extra songs that have already been played but can be played again and mustPlay songs that haven't been played yet. Let's say you are deciding what song to play at position x. Well, if x is high enough, then it is possible that the song you played M+1 turns ago is now available again (increase extra).

Then it becomes easy: Either play an extra song or a mustPlay song.

A base case for our recurrence is when x is P , which means that we have already decided all positions of the play list. If there are still mustPlay songs, then it is not possible to make a valid play list, else the play list is already valid.

Code:

const int MOD = 1000000007; 
struct NoRepeatPlaylist 
{ 
    int P, M; 
    long long mem[101][101][101]; 
    long long mem2[101][101][101]; 
    bool doit; 
    long long rec(int mustPlay, int x, int extra) 
    { 
        long long & res = mem[mustPlay][x][extra]; 
        if (res == -1) { 
            res = 0; 
            if (x == P) { 
                // No more slots to decide! 
                if (mustPlay == 0) { 
                    // Already valid 
                    res = 1; 
                } else {  
                    // Can't be valid. 
                    res = 0; 
                } 
            } else { 
                // If enough songs were played before, increase extra. 
                // (We can play again the song we played M+1 positions ago). 
                if (x >= M+1) { 
                    extra++; 
                } 
                //use an extra song or a mustPlay song. 
                if (mustPlay > 0) { 
                    // There are mustPlay options to choose from 
                    res += ( mustPlay * rec(mustPlay-1, x+1, extra) ) % MOD; 
                } 
                if (extra > 0) { 
                    // There are extra options to choose from 
                    res += (extra * rec(mustPlay, x+1, extra-1) ) % MOD; 
                } 
                // During the match, I forgot to do this: 
                res %= MOD; 
                // But I didn't resubmit because I did a test for all possible 
                // inputs, and it doesn't affect it. 
                // (Right as I am writing this comment, I figured it out. 
                // extra is always 0 in the first called instance of the recurrence. 
                // So this won't matter. 
            } 
 
             
        } 
        return res; 
    } 
    int numPlaylists(int N, int M, int P) 
    { 
        this->P = P; 
        this->M = M; 
        memset(mem, -1, sizeof(mem)); 
        return rec( N, 0, 0); 
    } 
}; 

Update: Good news everyone, at least one person during the match did a solution for div1 500 that doesn't rely on tricks and actually correctly predicts if the graph will grow infinitely. Take a look to bmerry's solution.

TCO 2012 algorithm, marathon and google announced

The relevant part of the TopCoder Open has been announced. I think it is worth blogging this time because it really needs to be pointed out that the contest structure is drastically different this time. see this thread for more info. In short, the post-qualification rounds will no longer instantly take you out of the tournament after a bad day. There are three round 2s and two round 3s, if you fail one or can't participate, you can do the next.

I was planning to problem set this year like last year. The decision I made last year was very good for me money-wise. However, these changes are making me rethink that position.

For example, getting a t-shirt this year sounds very viable. I think that as long as you get 116-th in one of the three round 2s, you will be very likely to get a t-shirt. In fact, it may happen that you can get a t-shirt with a higher rank if there are many coders who get positions between 1 and 111 in more than one round.

Even qualification to round 3 seems possible. You "only" need position 50 in one round 2. I think that it is possible for me to get such position depending of how lucky I am.

Of course, qualifying to the on site is a much less viable possibility. Top 12 in a TC match still sounds insanely high. Speaking of insanely hard objectives, let's talk about the new marathon rules. They are a lot more extreme than SRM rules. There are three rounds, no qualification and if you get 4 place in any of the rounds, you advance.

That's quite a twist. I think a good thing about this is that this greatly reduces the chances of qualification to on site depending solely on one very annoying problem. It used to be a case that the third marathon round is always a very boring problem that is a torture to solve so only coders with enough patience can participate in it. But now, since each Marathon has to host all coders, at least one round will have to be a fun enough round to make it worth it to work in it with the objective of reaching top 4.

Finally, Google (GOOG) will be sponsoring the TCO. This does not seem to have any effect on the prizes but it probably means on site advancers will have chances to get interviews.

TopCoder SRM 529: Interesting

I really have not much to say about this match right now. I haven't solved the div1 600, even though I have plenty of ideas. And the 250 is really an implementation problem.

Div1 600: The one with the bags

I spent most of the match being confused about the code. I even asked the admins to verify if it is correct. It turns out I was missing the move marbles from bag[2] to bag[0] line.

The code is long and complicated you will need to analyze a lot of it. I have found some things that are most likely the key to solve this problem.
* bag[1]'s contents will stay the same between the beginning of the deepmost while loop and its end (contents restored when moving from bag[3] back to it).
* bag[0]'s contents will stay the same between the second-inner most loop (same, when moving from bag[2] back to it).

In fact, bag[0] will be always be N at the beginning of that loop. More so, bag[1] is a counter that begins at 2.

More so: The loop will end once (N % bag[1] = 0) !.

Thus I can estimate the number of 'steps' needed to end the loop: The minimum divisor of N minus 1. It is easy to find that divisor.

I think that once you know that divisor, we can count the number of moves using matrix multiplication. I didn't have much time to explore this.

Div1 250: The one with the roman numbers

It has been a while since the last 100% implementation problem as a division 1 250.

I am actually a little mad at this, because I thought of this very problem one time (but using movies instead of King names). Guess it was actually a good idea for a SRM (although I meant for it to be a div2 250...).

Nothing to say here. However, I really have to mention that std::pair is VERY useful. In fact, it is sorting problems like this that make me really wonder how terrible would Java coders feel for not having something as useful as std::pair.

A minor complication is converting the Roman numeral to a integer. However, note that the Roman numeral will be at most 50, you can just use a table of the 50 first Roman numbers. Or, better yet, generate it using the table of the 10 first and the 5 prefixes.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) 
struct KingSort 
 
{ 
    // Convert Roman literal to int. 
    int toint(string n) 
    { 
        const char* romanu[10] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; 
        const char* romand[6] =  {"", "X", "XX", "XXX", "XL", "L"}; 
        for (int i=1; i<=50; i++) { 
            string s = string(romand[i/10]) + string(romanu[i%10]); 
            if (s==n) { 
                return s; 
            } 
        } 
        return -1; 
    } 
    vector <string> getSortedList(vector <string> kings) 
    { 
        int n = kings.size(); 
        // Will sort the vector non-decreasingly by order of names, and if 
        // they are equal by the order of the numeral value of the Roman numeral. 
        vector< pair<string, pair<int, string> > > vec; 
        for_each(q, kings) { 
            istringstream st(*q); 
            // Split by space , name holds the King's name and numb his Roman. 
            string name, numb; 
            st >> name >> numb; 
            vec.push_back( make_pair(name, make_pair( toint(numb), numb) ) ); 
        } 
        // Let it sort it for us: 
        sort(vec.begin(), vec.end()); 
        vector<string> res; 
        for_each(q, vec) { 
            res.push_back( q->first + string(" ") + q->second.second ); 
        } 
        return res; 
    } 
}; 

Let's see how it goes.

Codeforces round #102 div2

This was a good problem set imho. I began the match 4 minutes late. I think I did ok. Probably I will return to division 1 unless I made a stupid mistake (which could happen).

Problem A - Help Vasilisa the Wise 2
The numbers to write in the 4 boxes are limited to 1-9 . There definitely less than 9*9*9*9 combinations to try. In fact, lower than that if we cut cases with repeated numbers. Then for each combination, just verify that the line pairs give the sums c1, c2, r2, r2, d1 and d2, respectively.

int r1 , r2; 
int c1,  c2; 
int d1, d2; 
 
void solve() 
{ 
    for (int a=1; a<=9; a++) { 
        for (int b=1; b<=9; b++) if (a!=b) { 
            for (int c=1; c<=9; c++) if (c!=b && c!=a) { 
                for (int d=1; d<=9; d++) if (c!=d && b!=d && a!=d) { 
                    if (   (a + d == d1) 
                         &&(b + c == d2) 
                         &&(b + d == c2) 
                         &&(a + c == c1) 
                         &&(a + b == r1) 
                         &&(c + d == r2) 
                         ) { 
                               cout << a << " " << b<<endl; 
                               cout << c << " " << d<<endl; 
                               return; 
                    } 
                     
                } 
 
            } 
 
        } 
 
    } 
    cout << "-1" << endl; 
} 

Update: Of course, with a little further thought you can find that if you just brute force for one of the boxes, the rest of the boxes can be found through simple equations like: (b = c1 - a). This faster solution wasn't needed though.

Problem C - Help Farmer
After submitting A, I noticed some fast submissions for problem C. So I gave it a try before B.

We have n = (A - 1)*(B- 2)*(C-2). We want to minimize/maximize A*B*C - n. We can try all possibilities for (A-1), note that it must be a divisor of n, hence there are O(sqrt(n)) possibilities for A. (Need to know how to iterate a number's divisors in O(sqrt(n)) time.). Second, (B-2) should be a divisor of n/(A-1), so we can also iterate through these divisors. The total complexity is sublinear (less than O(n)). It may be hard to find the actual formula. But it will work in time for n=1000000000.

In theory, A*B*C may overflow 64 bits integers. I am not sure if that is possible. But you can get rid of the triple product by just expanding A*B*C - (A-2)*(B-1)*(C-1) . If you expand that formula you will find something without A*B*C.

typedef long long int64; 
#define long int64 
void solve(long n) 
{ 
    long A, B, C; 
     
    // Look for A-1 
    // A-1 is a divisor of n 
    long A1, B2, C2; 
    long minres = numeric_limits<long>::max(); 
    long maxres = numeric_limits<long>::min(); 
    for (A1 = 1; A1 <= n/A1; A1++) {   //O(sqrt(n) 
        if (n % A1 == 0) { 
            long a1[2] = {A1, n / A1} ; 
            for (int i=0; i<2; i++) { 
                long n1 = n / (a1[i]); 
                A = a1[i] + 1; 
                //Given (A-1), can we find (B-2)*(C-2) ? 
                for (B2 = 1; B2 <= n1/B2; B2++) { 
                    //B and C are symmetric, no need to try all ways 
                    if (n1 % B2 == 0) { 
                        B = B2 + 2; 
                        C = (n1 / B2) + 2; 
                        long dif = 2*A*B + 2*A*C - 4*A + B*C - 2*B - 2*C + 4; 
                        minres = std::min(minres, dif); 
                        maxres = std::max(maxres, dif); 
                         
                    } 
                } 
                 
            } 
        } 
    } 
     
    cout << minres << " "<<maxres<<endl; 
     
} 
#undef long 

Problem B - Help Kingdom of Far Far Away 2
This is really just a implementation problem. Due to the factors stated in the problem statement, we should really try not to parse the original number as a float. We can just use it as a string, this should avoid any incidental rounding if it can actually happen. Then it is all about parsing the original string following the problem's instructions.

My code looks awful:

string solve(string s) 
{ 
    bool neg = (s[0] == '-'); 
    if (neg) { 
        s = s.substr(1); 
    } 
    int point = 0; 
    while ( (s[point] != '.') ) { 
        point ++; 
        if (point == s.length()) { 
            s = s + "."; 
            break; 
        } 
    } 
    string dec = s.substr(point+1, 2); 
    int j = point; 
    stack<string> parts; 
    while (j >= 3) { 
        string p =s.substr(j-3, 3); 
        parts.push(p); 
        j -= 3; 
    } 
    string result = "$"; 
    bool first = true; 
    if (j > 0) { 
        first = false; 
        result += s.substr(0, j); 
    } 
    while (! parts.empty() ) { 
        if (first) { 
            first = false; 
        } else { 
            result +=  ","; 
        } 
        result +=  parts.top(); 
        parts.pop(); 
    } 
    result += string(".") + dec; 
    if (dec.length() < 2) { 
        result += string(2 - dec.length(), '0'); 
    } 
     
    if (neg) { 
        result = string("(") + result + string(")"); 
    } 
    return result; 
} 

Problem D - Help General
The first step is to notice that saying the squared distance to be 5 in a grid , is the same as saying that there is a Knight (Chess piece) move between the cells. Or rather for two cells, the difference in one coordinate must be 1 and the difference in the other coordinate 2.

Thus we can read the problem as maximizing the number of knights we can place in a n x m without them attacking each other.

My tip: Try some cases in paper. You will note that for large boards, we can place Knights in cells that are adjacent diagonally.

For example, for 5x5:

xyxyx
yxyxy
xyxyx
yxyxy
xyxyx

We can place knights in either all x cells or all y cells.

However, that is only true for large boards. When minimum(n,m) is 1, then we can place knights in all cells. When minimum(n,m) is 2, then we can follow this pattern:

xx..xx..xx..x
xx..xx..xx..x ...

Update: Another easy way to solve when the minimum is 2 is to fill one of the sides with soldiers/knights, the result is the same.

You will see that once the minimum(n,m) is 3 the above property is true.

int solve(int n , int m) 
{ 
    if (n > m) { 
        return solve(m, n); 
    } 
    // {n <= m} 
     
    if (n == 1) { 
        //Every one! 
        return n*m; 
    } 
    if (n == 2) { 
        int d = (m / 4) * 2; 
        if (m % 4 != 0) { 
            d += min(m % 4, 2); 
        } 
        return d*2; 
    } 
    // {m >= 3 && n >= 3 } 
    if (n*m % 2 == 1) { 
        return (n*m)/2 + 1; 
    } else { 
        return (n*m)/2; 
    } 
     
} 

Problem E - Help Caretaker

I am not very sure about this problem. Maybe optimized bruteforce works. Maybe you need something clever. I had doubts about trying dp as it would lead to some issues when building the final board and 2^18 * 9 * 9 does not seem small enough. I actually thought brute force would work. But at least my brute force solution's speed increases spectacularly between 7x7 and 7x8.

When I finished coding the bruteforce solution, there wasn't a lot of time left. So I tried an optimization such as verifying if the remaining rows are empty, we can reuse the solution for smaller n. Update: Forgot to mention that this solution turned out to still be too slow.

Also, I think that given enough time after reading the statement, it was possible to precalculate the 9*8/2 different boards off line and then just submit a solution that uses the precalculated ones.

Update: Yes, the precalculation idea was indeed a usable one.

I eventually solved the problem without need of precalculation by combining the pseudo dp idea with a way to crop the backtracking space. We intend to maximize the number of shapes we place, and thus we should avoid leaving too many empty spaces in the board as we recurse. Thus we can calculate the density of used squares / visited squares and stop the recursion if the density is too small. This combined with the pseudo-dp solves the problem.

Word on the street is that there is an overcomplicated dynamic programming solution to this. I think it might be the 9*9*2^18 solution I mentioned. But now I think it might be possible to turn it into 9*9*3^9.

SRM 451 - BrickPuzzle - Part 1

Remember that time I said that I would be making editorials for topcoder problems that lack official editorials? Remember how I stopped doing that after the first such time I did that?

Here is another problem I made for TopCoder that does not have an official editorial. It is a div 1 1000 (oooh).

BrickPuzzle
Link to problem statement

So you have infinitely many tetraominoes of the following shapes:


We want to place them in a grid with black and white squares in such a way that all white squares are covered by a tetraomino. Black squares do not necessarily have to be covered but can be covered if you need to. Tetraominoes you place must be aligned to the grid, cannot overlap and must lie completely inside the grid. You cannot rotate the tetraominoes , so they must be placed in the same way as the figure. Use as few tetraominoes as possible.



The maximum dimensions for the grid are 22x22. If it is impossible, return -1.


The backstory
You know what? Writing problems for Topcoder is difficult. Do not get me wrong, I am not saying that it is very hard. I am saying that it is horribly hard and makes your head melt. Right now I am still trying to think of problems that I needed to think of exactly the moment after the last SRM I wrote ended.

Sometimes I think of a problem I find in real life and try to turn it into TopCoder juicem this is the honest way to do it and is rarely useful. The dishonest way is to first think of a cool idea for a solution to a problem and then find some sort of problem that fits that idea of a solution.

What happened here is that I figured, that bitmask dp and similar are based on encoding a number as a bit mask and then using that number as a key. The idea was , why not think of a problem that does the same but instead of bitmasks, uses another number format?

The result was the problem that eventually became FourBlocks. An easy typical dp problem with the twist that the dimensions (22x22) do not allow the typical bitmask dp approach. For some reason I thought that was a good idea for a division 1 medium. When I showed this problem to Ivan Metelsky, he said that I should change the maximum dimension to 10x10 (Yes, really). He predicted (quite correctly) that even with 10x10 it would be a problem difficult enough for division 1 500, because a lot of people would be lame enough to use a greedy solution even though the constraints make it very easy to use dynamic programming.

I still wanted to use my original idea, so I saved it up for later. I figured that if I instead of using it in a typical problem, I used it in a less typical setting and included further implementation complications, it would actually be a div1 hard (Division 1 hards are to me the holy grail of problem setting, because they are impossible to think of, and once you have one, thinking of the rest of the SRM is not very hard, so you can ensure to take 500 dollars home).

Thus in the next SRM, I used BrickPuzzle. It turned out to be very difficult. I mean, nobody solved it. As such it is a failure. Every problem that does not get solved during a match is a failure. It still makes an interesting topic. I really love this problem and consider it a homage to dynamic programming. I also think that if you learn this problem you will finally understand the cons and pros of iterative dynamic programming and recursion + memoization.


This finishes part 1. In the next part I will hopefully write an editorial. I plan that part to be finished tomorrow.

About The 5 most annoying things about sports (To non sports fans)

I am sorry, but I cannot share links easily thanks to google reader and feedly, so I will have to post this one manually. It deserves to be shared.

cracked.com - The 5 Most Annoying Things About Sports (To Non Sports Fans)'

Thank you cracked, for expressing my feelings in the perfect manner once again.

Glad I am not the world's best programmer

Update: The incredibly misleading name "Facebook hacker cup" makes Bolivian newspapers fail: Facebook busca al mejor hacker del planeta

Just read: Are You The World’s Best Programmer? Compete In Facebook’s 2012 Hacker Cup

Last year I found a TopCoder thread about something called a hacker cup. But the link to explanation about its rules was a facebook page. And you know what I get when I try to open a facebook page?



Yeah, I had to register to facebook just to see info about that hacker cup thing last year, so I just didn't give it much importance and continued reading other threads.

Some time later, that thread exploded. Wow it was such an interesting read. Facebook managed to compress all possible horror stories about programming contests in a single qualification round... Generic problems, site glitches, bad test data, difficult to use interface...

The many issues with the so-called hacker cup apparently got quite an echo: Facebook hacker cup: Resounding failure.

Apparently it eventually gained some stability and the cup could continue. Which lead us to the best headline of 2011: Google Employee wins Facebook Hacker Cup. Hah. Later though, google got a taste of their own when the code jam first and second place went to TopCoder admins...

Also hilarious were the many reports of people offering money for help in the hacker cup. Yes, really it happened. Too bad I can't find the relevant links right now.

I won't participate in the hacker round. The prizes:

Of course! $5,000 USD and title as world champion to the top hacker, $2,000 for second place, $1,000 for third, and $100 for fourth through 25th. Awesome t-shirts for the top 100 hackers coming out of the second online round.

Are quite underwhelming and to me not out-weight the cons of creating a facebook account. I just look forward to what fun events will happen this year in relation to it. I am just glad I am not the world's best programmer.

To anyone who does not know much about programming contests, I would say things like google's code jam are far more relevant as a way to find who is who in the programming contest world. Facebook's little cup is very young as an attempt to gain cred.