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.