Ubuntu 12.04 upgrade tales

I am in a nothing-to-do month. I am really glad I was selected to problem set SRM 550 in Topcoder , else this would not have been a very productive month.

When you got nothing to do, you try to remember things that you were not able to do back when you were very busy. To me, my ever growing issue was that my ubuntu version in my main computer was ages behind. Until this week, I was using 10.10.

My history with ubuntu begins in 2005!, I installed a 5.something version. In retrospect it was not that good. With time ubuntu has been improving in somethings and getting worse in others.

I actually kept my initial 2005 setup since then, upgrading to newer version every 6 months or 1 year. Direct upgrades without cleaning your hard drive are actually VERY messy stuff to do. Even things like getting a completely different processor and motherboard did not stop me from keeping the old install and configuration. But I feel that with every upgrade, something gets ruined a little. At the end, when I had 10.10 I went through so many upgrade-related issues that I promised myself that the next one would be a clean install of the newer version instead of an upgrade. I guess that is the reason I could not find the will to upgrade for two years.

The problem with keeping an old ubuntu version is that, eventually, you cannot upgrade packages anymore. Your repositories are no longer supported... And these two years were full of exciting things like 600 new firefox versions and the shift from OpenOffice to LibreOffice. So, I figured I needed to upgrade...

The plan

I am the proud owner of a 500GB external hard drive that connects to USB. This is one of the most useful things ever invented. So, I just made a backup of my ubuntu partition and saved it in the hard drive.

THREE HOURS I had to wait copying it. But it has so many benefits. I would not lose any data, and configuration for things that are not system-critial can be restored from my own home, if I just now where to find them and where to place them...

Install

A clean install is so much easier than upgrading. You can even test the ubuntu version from the install CD. A great sign was that things like 3D acceleration , sound, resolution and printer were working completely out of the box in this CD.

Something ominous was the new interface. The new ubuntu version has this thing called unity . Which was casually something they started using just AFTER version 10.10. So I avoided 2 whole years of development towards this unity thing. The change is VERY drastic from the GNOME thing I was used to (which was the default since before I started using ubuntu).

Oops

So, I start installing, it offers me to download updates for packages while installing. That is a novelty and sounds useful (In the past, after installing you would be greeted with the request to download tons of package updates so your install wasn't finished). So I click yes.

Then I find a cute surprise. Apparently the new installer can actually install ubuntu without deleting your data files. Perhaps the whole "copy partition to external hard drive" thing was not needed. I did not use the option though.

Format partition, install it. Then it downloads the packages. And it takes 2 hours to download everything. The good thing about the live CD installer is that you can actually use your computer and browse the web WHILE installing the Operating system. After the 2 hours, it begins installing the new packages and... THE IDIOT CRASHED!. Yes, installer crashed, I panicked, if clean install is messed up, then I would have a messed up install and the same kind of problems I had for upgrading so many times.

I restart, and somehow ubuntu boots just fine without complaining of everything. All hardware seems to be working. But apparently, updates weren't installed. So I have to... download again. But this time I also download all the things I remember are useful: jEdit, valgrind, wine (from its ppa), firefox 14 (from its ppa), jdk, g++, avidemux... I tried to remember everything that to me is vital. New download took ages, but thankfully this time everything installed fine. I found my own game, Xye in the repositories, great.

Unity... sucks

I began to notice this when playing with the live CD. Then I tried to use Unity for a while. Casually, by the time I finished setting the basics up, it was Thursday and I received the shock surprise that I was assigned to work in setting up SRM 550. Suddenly, I needed to use my computer for real, programming work. Yet, my programming environment was not setup, and I had to improvise with Unity.

After about 3 hours of attempting to work using unity. I really got sick of it. Sorry, but this vertical apple clone thing is GREAT at getting in the way. I can't tell if icons in it are launchers or already opened windows or both. When I have multiple windows of the same app, I need to browse whole menus to get the correct ones. Switch desktops? It takes seconds to play animations and double, triple click to enter the desktop.

You cannot do the minimum configuration. Want to change the interface's colors? NO. Want to move the launcher bar horizontally? No.

Maybe users new to computers like this stuff, as they are used to taking ages to do the most basic things. But I do not.

What I liked was the menu that appears when you click the main button. It automatically searches for applications or files or both. And remembers the ones you use the most. But I was fed up with just about everything else. I looked for alternatives.

GNOME 3, classic GNOME, classic GNOME without compiz...

So, the good thing is that I can actually install different interfaces and keep the operating system. Can you say something like this about Winods, OX/S, iHOS or ArDoird, or whatever they are called?

I did it: installed GNOME 3. Turns out GNOME 3 is also very different to the GNOME I was used to. When I tried GNOME 3. It was even MORE obscure than unity. Or perhaps I was just tired of trying funny things that I was not used to?. I really could not get why it shows the name of the active app at the top. Complete mystery.

The good thing is that it allows you to use the CLASSIC gnome too!. So I switched to that option. That was closer to what I use, but still not much. I could not configure the GNOME panels like in the past.

Google around, and it turns out that you cannot anymore right click to edit the panel, so I used the complicated keyboard combination and edited everything.

But even the classical gnome had some difference. There were definitely less options in the panel configuration, and I could not change the interface colors (seems new GTK+ is lacking in this department). Also, those flashy desktop effects and animations that were so annoying in unity are still around. I have been here before, It is because of something called compiz. I tried to like compiz in the past, but it makes everything slower and is too annoying at times. Specially when switching between Desktops. (Sorry, but I do not need animations there, I just want to switch in 0 seconds).

The last tweak was, pick the "Classic GNOME without Effects" option. But now, you do not have cute shadows and you cannot use transparency! Do not worry, you can now Enable metacity compositing.. This does the good things that compiz does. Without doing the childish, annoying things it does.

Some interesting results

• Sun Java does not exist. And Oracle Java cannot be installed from the repositories anymore because those Oracle guys are jerks that want to ruin open source completely. But it turns out OpenJDK from the repositories does all that I need it to do ... I can compile Java stuff, run Java stuff and the Topcoder Arena and MPSQAS work well!
• GCC 4.0 was missing from the repositories for ages. So I used GCC 4.2 to test Topcoder stuff. Now GCC 4.2 is also missing. GCC 4.3 is missing too! So I now have to use GCC 4.4. Which is very different. Topcoder really need to upgrade their GCC version. 4.0 is too antique (and bugged too).
• Classic/fallback gnome is much faster than the stuff I used in 10.10. For some reason. My environment is flying!
• Nautilus removed the emblems feature, now I have a lot of folders that I cannot differentiate from each other.
• LibreOffice is much faster and better than OpenOffice.
• My iPod (Won it at a Google code jam), still cannot be mounted. This is a bug that I started to experience at version 10.10, and thought it was because of the upgrade.
• The lack of customization options are KILLING me.
• I restored EVERYTHING from my old firefox by just replazing the .mozilla folder in the new install with the .mozilla folder from the old one. I mean everything. Semantic bar, addons, addons's settings...(/home/yourusename/.mozilla
• I restored EVERYTHING from my topcoder arena by doing the same with a file called /home/yourusername/ContestApplet.conf.
• The new version of GRUB loads much faster. If you install a program called grub-customizer, you can configure it and it is much easier than before.
• Ubuntu 12.04 boots VERY quickly.
• Say what you will about Ubuntu, and in fact its interface changes are terrible. But hardware support has really improved since the old years. Applications are very competitive now. And ubuntu specifically is great at one thing: packages. There are many things in the repositories, and then they invented ppas. It is very easy to install things on ubuntu. I got so used to the repositories that I cannot try another distribution. I can always change the interface and tweak it, but the packaging is something internal to the Linux distribution.

SRM 550: I regret nothing!

I wrote SRM 550. The editorial is coming soon-ish. I will use this entry not so much to explain the problems (will do in the editorial). But to comment about the match.

I was assigned this match on Thursday. I had something that looked like a match but not a very complete proposal. Was looking more to first confirm something in div1 hard difficulty before getting a match. But I think the admins had difficulty finding something better, and I was the one with the closest thing to a div1 hard (we really thought the problem that was ultimately used as a 850 pointer was not hard enough.

Those two days of development were intense. We replaced many problems with other problems. Most of the difficulty in the 850 pointer comes from nice modifications from rng_58 and mystic_tc.

This 850 pointer turned out to be the big screw up of the match. Just as the contest started, lyrically was already reporting bugs with the statement. Later Petr found out we did not have a constraint that specified that only a,b and c are allowed in the input. And ir5 got confused about something - apparently, the statement was never clear enough to say that each letter is changed one at a time.

Ultimately, it turns out that the 850 points problem was actually normal div1 hard difficulty and not deserving of the low score value. What happened? Maybe the statement was too confusing? Seems not, because we did not receive many complaints about this. Apparently, we tweaked the original version of the problem (only moves a->b, b->a , max cost <= 3, length <= 33) so much that we turned the problem that seemed like a div1 600 at best into a legit div1 hard.

But besides div1 850, I regret nothing!.

Q. Please stop writing problems*

A. No sorry, can't do. This is part of what I do for a living. And it is always fun. The only viable way in which I can stop writing problems is if admins stop accepting them.

If you are interested in traveling to the past and stopping me from writing this match, a good fix would have been to give the admins an alternative to my problem set so that they did not have to use mine for this SRM in the rush of two days missing.

*Actual quote.

Q. Example #5 in div1 300/div2 550 is wrong/ do not get why it is wrong / etc

A. We got this a lot during the match. No, it was not wrong.

We decided to include this example and many others to make sure the success rate stayed high in this problem. So, yes, you should be happy this case was in the examples...

To be honest, I intended this problem as an easy problem for TCO rounds like round 3 or maybe the semifinals. The original version had movements < 1000000000. I had to use this problem for a normal SRM unfortunately, because the previous problem idea I had available fro this slot turned out to be a very tricky problem. That is right, we used this problem because it was the least tricky problem available for div1 easy.

My post there explains it.

Q. Div1 500 is too mathematical!

A. I call humbug!. When I thought of this problem it was because I had an assignment that said "Design a cell automaton to generate Sierpinski's triangle". It turns out this task was rather standard and everybody knows how to do this triangle from top to bottom (Using Pascal's triangle modulo 2). Yet I somehow thought of a solution for the assignment that does it diagonally.

I thought I could capitalize this strange idea - This fractal triangle is a very easy fractal, and I really like this fractal. So I thought of this problem that can be solved by two steps: a) Find out the pattern is a fractal. And b) Use simple recursion to generate the fractal for each requested cell.

So, to me, this has always been a problem that is meant to be solved through programming (recursion). All those guys that used a formula related to combinations and modulo 2, well, you used that formula because YOU are Mathematically-inclined, not because the problem is Mathematically-inclined :). I am more of a programming-inclined guy, so I was not aware of those formulas until the admins told me :)

SRM 549: The hell is an apex?

SRM 549... I had a bad day with a very slow 250 and a 600 that I solved but could not debug fast enough. I think the problem set itself was fine and interesting, albeit perhaps imbalanced (which happens 90% of the time). But the statements were just not clearly explained. Specially, the lack of images or better explanations in 250.

Div1 250: The one with cones

So, what is an apex? Those of us who did not learn basic geometry in English probably have no idea. I had to google apex, it turns out it is just the top vertex of the cone. So in fact, the distance from a cone's base to the apex is giberish for the word "height". It was still pretty hard to understand what the condition for a top cone to match a bottom cone.

Anyway, we have a list of top cones, each with radius and heights, there is a correct way (which is impossible to understand) which defines a condition in which a top cone can be used in combination with a bottom cone to make a wizard hat. What is the maximum number of hats you can make?

The problem is just a maximum bipartite matching problem. There is probably a way to solve the problem without max flow or the Hungarian algorithm. But that requires you to actually understand the rule that determines whether you can match a top cone with a bottom one. But I solved it with max flow. Basically, pasting max flow and preparing the bipartite matching was the easiest part that took me less than a minute. The problem was to then just find what the condition was...

At the end, I guessed it. If you are going to place a cone on top of another, then you can think of the cones as straight triangles. Then when placing a cone on top of another, you are interested in the height at which the width of the top cone intersects the lower cone. It is much, much, much easier with a image:

The trick is to find the line equation that would give us the y-position at which the bottom cone distance from axis to hypotenuse is equal to the top cone's width. Then you can find the position at which the apex (top vertex) of the top cone will end. Compare this position with the bottom cone's height, it must be higher. (Also compare the widths before doing all of this, the top cone's width must be smaller.

bool canDo(int topHeight, int topRadius, int bottomHeight, int bottomRadius) 
{ 
    if (topRadius < bottomRadius) { 
        // The equation is: 
        // y = bottomHeight - (x/bottomRadius) * bottomHeight 
        // then: 
        // bottomHeight - (x/bottomRadius) * bottomHeight + topHeight 
        //  > 
        // bottomHeight 
        // 
        // or: 
        return ( topRadius*bottomHeight < topHeight*bottomRadius ); 
    } 
    return false; 
} 
 

Once I guessed this rule, I implemented it and it passed the examples. I submitted it and it turns out to be fine. Sorry but, I would have rather not spent 95% of the time trying to guess what the problem statement wanted. It is worse because at the end few people solved 600 so the difference between a good rank and a bad one was mostly defined by speed in this problem.

Div1 600: The one with hats in grid

This one had the clarity issue, albeit not as badly as the 250.

You are given a board (at most 13x13) which contains hats (at most 13) in some of the cells. There is a list of coins (less than or equal to the number of hats), that the wizard placed in such a way that each hat has a coin. You can make at most numGuesses guesses which involve picking one hat, one at a time. After you pick a hat but before you get to see its contents, the wizard is allowed to "reshuffle" the coins in the hats. This was the first point of confusion, after asking the admins, it turns out that the "reshuffling" is not random, instead, the wizard will place each coin in whatever hat he wants. However, the reshuffling will not change the contents of hats you have already picked before.

So in fact, whenever you pick a hat, the wizard can do whatever he likes and thus it does not really matter what was inside the hat before you picked it, the wizard will just give you the coin he likes the most or no coin at all. The game would be pointless if it was not for the following condition: At any point in time, for each row, the sum between the number of coins and hats in the row is even. And for each column, the sum between the number of coins and hats is even too.

It was such a coincidence (albeit ultimately not a very happy one, because I still could not solve the problem). That I recently remembered a problem of mine called RobotKing, which was used in a netEase tournament. The problems are similar in the game theory aspect and in having to encode the state in base 3...

Base 3, so imagine we determine the current state of the game as a list of values, one for each hat in the board (there are at most 13 of them). Each value is 0 if we still have not picked the hat. 1 if we picked the hat and it turned out to have a coin and 2 if we picked the hat and it turned not to have a coin. This state is enough to represent the game. Let us say there are correctGuesses 1s in the state, it means that you have already gotten correctGuesses coins. If the wizard decides to give you a coin, there is no reason for the wizard to give you a coin with value higher than the smallest value available. So you can assume that the correctGuesses smallest coins have already been given to you. Let usedGuesses be the number of values in the state that are not 0 (the number of known hats), then you also know you have made only usedGuesses in total.

Thus we have a function f(state), where the state is such an array of values (0,1 or 3) for each of the hats. That returns the number of hats you will get if you and the wizard play optimally - make the best choices possible. The state is currently an array, but you can also represent it as a single number mask. Considering it as a base 3 number, you can extract values (0,1 or 2) from it. So, if the number of used guesses is equal to the guess limit, we got a base case, we cannot win any more coins. Else we can pick one of the hats as a guess. So, let us try each possible choice. This will allow us to implement the recurrence with dynamic programming or memoization.

Let us say we decide to uncover the i-th hat (the value of the hat must be 0, unknown). Then the wizard may have two possible choices. a) To give you no coins at all. b) To give you the smallest coin available. The wizard will pick the decision that will ultimately give you the least number of coins.

The problem is that there are times at which placing a coin in a certain hat is not possible, or not placing a coin at all in the hat is not possible (To follow the condition regarding parity of rows and columns). I basically spent 20 minutes thinking of a way to do this. At the end, I thought it was very silly I did not think of this before. The constraints are still slow - 13. So in fact, we can do this with another dynamic programming function. couldHappen(mask), the mask is in the same format as the state in the other function. It returns if a possible setting (with some hats being unknown, other hats having coins and some definitely not having coins) is possible. The base case is when there all coin positions are known, we calculate the parities and if the parities are correct, then it is possible, else it is not.

The recursion involves, when not all coin positions are known, to decide to place a coin in one of the unknown positions. If any of these possible moves leads us to a correct setting, then the original setting is also correct.

.

struct MagicalHats 
{ 
    int pow3[14]; 
 
    int r, c; 
    int numGuesses; 
    int mem[1594323]; 
    char could[1594323]; 
    vector<int> coins; 
    int n; 
    int x[13]; 
    int y[13]; 
    vector<int> rowpar, colpar;     
     
     
    int couldHappen(int mask) 
    { 
        // Is the state given by the mask possible? 
        char & res = could[mask]; 
        if (res == -1) { 
            res = 0; 
            int known = 0; 
            { 
                vector<int> rp = rowpar; 
                vector<int> cp = colpar; 
                for (int i=0; i<n; i++) { 
                    int ch = (mask / pow3[i]) % 3; 
                    // ch == 0: unknown contents 
                    // ch == 1: coin 
                    // ch == 2: no coin. 
                    if ( ch == 0) { 
                    } else if (ch == 1) { 
                        known++; 
                        rp[ x[i] ] ^= 1; 
                        cp[ y[i] ] ^= 1; 
                    } 
                } 
                // Base case, all coin positions are known, 
                // verify the parities are correct. 
                if (known == coins.size() ) {  
                    res = 1; 
                    for (int i=0; i<r; i++) { 
                        if (rp[i] == 1) { 
                            res = 0; 
                        } 
                    } 
                    for (int i=0; i<c; i++) { 
                        if (cp[i] == 1) { 
                            res = 0; 
                        } 
                    } 
                    return res; 
                } 
            } 
            if ( known < coins.size() ) { 
                // decide to place a coin in an unknown place 
                res = 0; 
                for (int i=0; i<n; i++) { 
                    if ( (mask / pow3[i]) % 3 == 0 ) { 
                        // this updates the mask, the place is 
                        // now known to have a coin: 
                        int nmask = mask + pow3[i]; 
                        if (couldHappen(nmask)) { 
                            res = 1; 
                        } 
                    } 
                } 
            } 
        } 
        return res; 
    } 
     
    // What is the number of coins the player wins after the  
    // state that is given by the mask? 
    int rec(int mask) 
    { 
        int & res = mem[mask]; 
        if (res == -1) { 
            res = 0; // maximize this! 
            int usedGuesses = 0; 
            int correctGuesses = 0; 
            for (int i=0; i<n; i++) {  
                int ch = (mask / pow3[i])%3; 
                if ( ch != 0) { 
                    usedGuesses ++; 
                } 
                if ( ch == 1) { 
                    correctGuesses++; 
                } 
            } 
            if (usedGuesses == numGuesses) {  //no more guesses 
                res = 0; 
            } else { 
                // guess something... 
                for (int i=0; i<n; i++) {                    
                    // what happens if I pick hat i? 
                    if ( (mask / pow3[i])%3 == 0) { 
                        // The wizard actually wants to minimize the result 
                        int wiz = 130000; 
                         
                        // What happens if the wizard places a coin here? 
                        int nmask = mask + pow3[i];                      
                        if ( couldHappen(nmask)) { 
                            // coins[correctGuesses] is the smallest coin available 
                            wiz = std::min(wiz, coins[correctGuesses] + rec(nmask)); 
                        } 
                        // can the wizard place nothing here? 
                        nmask = nmask + pow3[i]; 
                        if ( couldHappen(nmask)) { 
                            wiz = std::min(wiz, rec(nmask)); 
                        } 
                        // the maximum is what we want... 
                        res = std::max(res, wiz); 
                    } 
                } 
            } 
        } 
        return res; 
    } 
 
    int findMaximumReward(vector <string> board, vector <int> coins, int numGuesses) 
    { 
        sort(coins.begin(), coins.end()); 
        this->coins = coins; 
        this->numGuesses = numGuesses; 
 
        //init powers of 3:         
        pow3[0] = 1; 
        for (int i=1; i<=13; i++) { 
            pow3[i] = 3*pow3[i-1]; 
        } 
        //init parities and positions:         
        r = board.size(); c = board[0].size(); 
        rowpar.resize(r); 
        colpar.resize(c); 
 
        n = 0; 
        for (int i=0; i<r; i++) { 
            for (int j=0; j<c; j++) { 
                rowpar[i] ^= ( board[i][j] == 'H'); 
                colpar[j] ^= ( board[i][j] == 'H'); 
                if (board[i][j] == 'H') { 
                    y[n] = j; 
                    x[n++] = i; 
                } 
            } 
        } 
        memset(could, -1, sizeof(could)); 
        if (! couldHappen(0) ) { 
            return -1; 
        } 
        memset(mem, -1, sizeof(mem)); 
        return rec(0); 
 
                 
    } 
}; 

I was not so lucky during the contest. Ultimately, the one bug that prevented me from submitting was : I typed int & res = mask; instead of int & res = mem[mask] ;

Outcome

Barely nothing in rating increase.

Again, I think the problems were good and interesting, but the clarity issues sort of broke the match for me. We don't want topcoder to become codeforces. Well, at least I don't...