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.