SRM551: slowness

Nothing like a TopCoder SRM with an ultra easy problem set to make you feel like a turtle. I solved both problems yet I am in position 230-th. (Starting to write this 5 minutes before the coding phase ends).

Div1 450 : The one with the wolves

Anyway, a wolf changes colors at night, when the wolf has a certain color, there is a list of available colors for it to change to. The wolf always picks the smallest color available. You are allowed to remove some of the possibilities to change from a color to another. What is the minimum number of removals you need so that a wolf starting at color 0 eventually reaches color N-1? (Does not have to stay in that color).

For some incredibly stupid reason, my old reflexes came back and I started with the medium problem. I really did not intend this to happen. This problem was so easy that I think I should have first warmed up on the division I 250 to be able to solve this one faster.

As my brain was just starting to function I was first lost on the idea that it was a maximum flow problem. Because in a way it asks you to cut roads. To the point that even when I thought of the cost function to make you go from a color to another, I decided to use min cost max flow instead of the obvious Dijkstra / or Floyd-Warshall. I would only discover my mistake after I made the code for the flow network...

Anyway, the wolf will always pick the smallest color available. It is always possible to force the wolf to pick any of the colors that are possible, you just need to remove the availability of the smaller colors. In order to force wolf color i to always turn into wolf color j, just remove all the available changes to colors of smaller value. This is the cost to move from color i to color j. You end up with a list of costs to move from each color to another. What is the cost to reach N-1 starting at 0? This is just a min-cost path problem. The paths are weighted. I just used Floyd-Warshall.

int getmin(vector <string> colormap) 
{ 
    int n = colormap.size(); 
    int cost[n][n]; 
    const int INF = 1<<20; 
    // Find the cost matrix 
    for (int i=0; i<n; i++) { 
        for (int j=0; j<n; j++) { 
           // infinite cost path means there is no path between the two colors 
            cost[i][j] = INF; 
            if (colormap[i][j] == 'Y') { 
                cost[i][j] = 0; 
                for (int k=0; k < j; k++) { 
                    cost[i][j] += (colormap[i][k] == 'Y'); 
                } 
            } 
        } 
    } 
    // Floyd-Warshall finds all minimum total costs, and is very simple to code: 
    for (int k=0; k<n; k++) { 
        for (int i=0; i<n; i++) { 
            for (int j=0; j<n; j++) { 
                cost[i][j] = std::min( cost[i][j], cost[i][k] + cost[k][j] ); 
            } 
        } 
    } 
    return ( (cost[0][n-1] == INF) ? -1 : cost[0][n-1]); 
} 

Div1 250 : The one with the string of colors

You are given a string, like "AABACAA", what is the maximum number of adjacent characters in a string you get by modifying the original one using at most maxSwaps swaps of adjacent characters?

A O(n⁵) algorithm: For each value of the number of adjacent characters. Try each possible starting index of the adjacent characters. For each of them, try the character of those. For each of them, find the minimum cost to have it that way.

The minimum cost can be found in O(n²), just find the starting point of the wanted letters used in the original string. Then you find the positions of the (spread) letters in the original string that have to be moved to the adjacent area.

It is much easier to do than explain.

Let us say that the X mark original positions of the characters we are interested in:

X.X....X.X

Somehow we want the final string to be "...XXXX...". What is the minimum cost? The first X in the string has to be the first X in the wanted area. That involves a distance and a cost. The second X has to be the second X and so and so. This is simple. The complication is when there are far more Xs than wanted:

X.X.X....X.X.X

If we still want ....XXXX..... , then we have to pick which of the original X is the first one.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) 
int maximumSpread(string chocolates, int maxSwaps) 
{ 
    //set some stuff up: 
    vector<char> colors; //available colors 
    {  
        set<char> chset(chocolates.begin(), chocolates.end()); 
        for_each(ch, chset) { 
            colors.push_back(*ch); 
        } 
    } 
    //  
    vector<int> cnt(256, 0); //number of times each color appears. 
    for_each(ch, chocolates) { 
        cnt[*ch] ++; 
    } 
    int n = chocolates.size(); 
     
    // For each possible spread: 
    for (int spread=n; spread > 1; spread--) { //O(n) 
 
        // for each starting index: 
        for (int start=0; start+spread <= n; start++) { //O(n*n) 
            // for each color :             
            for_each(ch, colors) {  //O(n*n*n) 
                if (cnt[*ch] >= spread ) { 
                    // for each starting index in the original string of that color: 
                    for (int o=0; o<n; o++) { //O(n*n*n*n) 
                        if ( chocolates[o] == *ch ) { 
                            int x = 0; 
                            int pos = o; 
                            int cost = 0; 
                            // find the costs to move each letter: 
                            while (pos < n && x < spread) {  //O(n*n*n*n*n) 
                                if ( chocolates[pos] == *ch ) { 
                                    cost += abs(start + x - pos); 
                                    x++; 
                                } 
                                pos++; 
                            } 
                            // the minimum cost is possible, return it 
                            if ( (cost <= maxSwaps) && (x == spread) ) { 
                                return spread; 
                            } 
                        } 
                    } 
                } 
            } 
        } 
    } 
    // 1 is always possible: 
    return 1; 
} 

This O(n⁵) solution can be easily improved to reduce the exponent, but that is not needed. For example, we can move the loop for o upwards and replace the color with it. In fact, this code is already O(n⁴) because there are O(n) valid pairs of (o, color).

The rest

I was severely dissappointed that everyone was solving both problems much faster. I don't like matches that are determined solely on speed. When the problems are this easy, speed tends to be almost indistinguishable from luck, imho.

I opened the 1000, but it seemed harder, and the targets who got plenty of time as solved the first two problems very fast did not solve it yet. So I instead tried to find possible mistakes in 250 and 450. But it seems that the example cases were very strong. Specially in 250. I thought that a common mistake would be to assume that the result adjacent area has to start at position that already includes the letter. This is not true, but it turns out the second example already catches that corner case.

Read More

SRM 451, BrickPuzzle : Part 2 (MAX2214)

In January I made a post about SRM 451's BrickPuzzle. I think it is the hardest problem I released yet and I am also in love with it because of the knowledge its solution can transmit. Yes, I am exaggerating so you are more interested in reading this post. Can you really blame me?

That day of January, I promised that the second part of the explanation would come the next day. I obviously lied.

MAX2214?

There are many ways to solve a hard problem. One that turns out to be very good is to first solve an easier problem. I will talk about a problem I wrote recently in an attempt to teach dp stuff. (To be honest, I am still very skeptical of the ICPC and programming camps as a whole, but that is another topic). This problem was then submitted to spoj and it is turning out to be very hard. Everybody who solved it to this point is not using the intended solution. Unlike BrickPuzzle, Max2214's is written in a way that turns out to be more permissive to heuristics and that sort of thing. But we will pretend that we do not know that, and will instead solve MAX2214 using dynamic programming. You will see that once you know the dp solution to MAX2214, you also know the solution to BrickPuzzle, but BrickPuzzle also has implementation complications...

In MAX2214, we want to know the maximum number of blocks we can place on a grid without making the blocks overlap with each other or with cells marked with X. Two kinds of blocks are allowed: 2x2 and 1x4.

Easy bitmask dp

The cynical in us, tend to view bitmask dp problems as very easy problems. Mostly because they are just dp problems (which become easy after you seen a good amount of them), yet their small constraints make it obvious that they are the intended solution.

Not in this case, if you committed to the idea of solving MAX2214 using dynamic programming and bitmasks, you would inevitably calculate the exponential complexity that is needed for time and memory and learn that it is impossible to solve the problem like that.... Except that it is. So let us ignore that part for now.

FourBlocks

There are many ways to solve a hard problem. One that turns out to be very good is to first solve an easier problem. Before solving MAX2214, solve FourBlocks. A topcoder problem I wrote back in the dark ages of topcoder. The time in which editorials were not paid and nobody really put any effort in them in the wiki. So the editorial for SRM444 is very bad. But I have found some stuff about FourBlocks in other places:

• TurtleShip's blog
• Wilan's blog
• The wiki editorial I already linked.

MAX2214, again To summarize the "easy" bitmask dp

Let us define a recurrence f(x,y, mask). We have already assigned the contents of the cells in the first y rows and the first x cells in row #y (0-indexed). The mask is a bitmask the first x bits tell us about the contents of the x first cells of row (y+1). The remaining bits tell us about the contents of the remaining cells in row y. A bit is turned on if and only if the related cell contains part of a 2x2 block.

In the image, we can see what x and y are. The mask represents the blue cells. The orange cells have already been decided. We want to find out the maximum number of new blocks in the cells that are not orange.

There are three decisions we can take regarding cell (x,y):

• Place a 2x2 block in such a way that cell (x,y) is its bottom-left corner. This requires us that the cells that will be occupied by the 2x2 block are not used by a cell marked with X or by a block we already placed. The maximum number of new blocks we can get is 1+f(x+2,y, new mask). Because we can just skip the next two cells as we already know they will contain a block. The new mask will now contain two consecutive turned on bits.
• Place a 1x4 block. Not a problem, just make sure the next 4 cells are usable, then skip to f(x+4,y, mask).
• Place nothing in this cell, we skip to f(x+1, y, new mask). The new mask might have one less of a turned on bit, in case the cell at (x,y) was already busy..

The image shows the sub-case f(x+2, y, new mask).

Some base cases:

• When we reach f(x = w, y, mask), then we have already used all the cells in the row, we can just skip to the next row. The result is f(x = 0,y + 1, mask).
• When we reach f(0, y = h, mask) then we have reached the end of the whole grid. The result is 0 (That is the maximum number of blocks we can add to the 0 remaining cells.

I think we can be very sure that this approach will give us the correct answer. But is it fast enough? You already read somewhere that it is not. The mask is a bitmask and can have any combination of w bits. That means 2^w different values for the mask. There are w * h pairs (x,y) so the complexity is O(w * h * 2^w ). In spoj, the width is at most 22 and the height is at most... 52. This certainly sounds too heavy, even for the 15 seconds per case limit.

Is it really so slow?

The key thing to notice is that there really are not that many different ways to set the mask. If you remember, the only bits we remember are pairs of consecutive bits that come from the 2x2 blocks.

This needs us to pay attention to the way the bit mask works. If at some point we add a 2x2 block using (x,y) as the bottom-left corner of the 2x2 block, it always adds two consecutive bits to the bitmask.

Let us talk about the case when we find a turned on bit at (x,y). We can just assume that whenever we find this bit, the next bit will also be turned on, so we can skip them both and not add a block to those positions. By doing this, the mask will lose both bits.

The image shows that transition.

What we can tell is that mask will never contain a lone turned on bit. 11000110110_{2 and 000011011112 are valid values for the mask. 101001101102 and 000010000012 are not.}

Fibonacci

Let us count the number of valid masks of length w. For w=1, there is only one valid mask: 0. For w=2, 00 and 11. For w=3: 000, 011 and 110. For w=4: 0000, 0011, 0110, 1100, 1111.

You will eventually notice that the results are all fibonacci numbers. It is not a coincidence, you can verify that a good formula is f(w) = f(w-1) + f(w-2), because you add either "11" or "0" to a previous valid mask. Let us say fib(w) gives the number of masks. The complexity of our algorithm has become O(h * w * fib(w)). You will see that for w=22, the difference between 2²² and fib(22) is very large. So our recurrence turned out to be much faster than we thought. In fact, it is fast enough for the 15 seconds limit. But there is a catch.

Memoization vs. iterative dp, not the same thing

This is the key to the problem. If we implement the recurrence using memoization, then only valid values of mask will be generated and thus the speed will be as predicted O(h * w * fib(w)). The catch is that if we implement it using a mem[h][w][fib(w)] array, it will go well beyond the 256 MB limit. If we use a hash table or something like that, we would be adding enough overhead that our fast solution would not be that fast anymore.

So, in order to save memory, we can do iterative dynamic programming. At every point, when calculating f(x,y) you need only keep in memory the results for row y and row y+1. Thus we can use the memory of 2 rows instead of 52 rows. This will fix the memory problem... But when doing iterative dp, you cannot enjoy cropping invalid states. So we will not only generate only the valid values of mask if we do an iteration from 0 to 2^w-1. We are back to exponential time.

Have we reached a dead end? It sure seems so. Iterative dp allows us to optimize memory, but we can't crop invalid states. Memoization allows us to crop invalid states, but we need cannot optimize more memory usage. We need the best of both worlds and it is completely possible to do it. Who says it is bad to get greedy? (not the algorithm category). Sometimes you can have your cake and eat it too. Let me explain the work around tomorrow (or maybe in 7 months, who knows?.

Read More

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.

Read More

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 :)

Read More

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...

Read More