TopCoder SRM 557: GreatFairyWar and IncubatorEasy

SRM 557

Explanation for division 1 Easy and match recap. Explanation for div2 easy and div2 medium.

Div2 Easy: GreatFairyWar (250 points)

Link to problem statement

You have way too large hp. You are battling against N fairies, indexed from 0 to N-1 which you must kill in the given order (First kill 0, then 1, ...). The i-th fairy has hp[i] hit points and will do dmg[i] damage per second while she is alive (meaning that in each second, the fairy will remove dmg[i] from your hit points). Your damage per second is 1, which means that in each second you reduce 1 hp from the fairy you are currently killing. What is the total number of hit points you will lose before the last fairy finally dies?.

Let us try with fairy 0: fairy 0 has hp[0] hitpoints, and you can only reduce one per second, which means that you need hp[0] seconds before the fairy dies.

During each of those hp[0] seconds, all the fairies will use their attacks on you. If each fairy attacks you, the total damage you will receive each second is equal to the sum of all the dps[i]. This happens during hp[0] seconds, so while fairy 0 is alive, you will receive a total of hp[0] * (sum of all dps[i]) damage.

After fairy 0 dies, there are only fairies 1 to n-1 left. The logic shall be the same: Fairy 1 will be alive for hp[1] seconds. During each of those seconds you will receive attacks from each fairy (except fairy 0), totaling to (sum of (dps[1], dps[2], ... dps[n-1]). The total damage you will receive while killing fairy 1 is: hp[1] * (sum of all dps[i] minus dps[0].

Repeat and you shall see, for each fairy i add hp[i]*(sum of dps[j] starting with j=i). This can be easily implemented with two for loops - one nested inside of another.

How about we simplify the code a bit, it is not necessary, but it makes the code look more awesome. If we did the main loop in reverse, and first calculated the damage done to you while killing fairy n-1, then fairy n-2, and so and so until fairy 0, we can then calculate the appropriate sum by using the sum used in the previous step. Something like this:.

The low constraints on the number of fairies (at most 30) was probably there to avoid overflow bugs.

int minHP(vector <int> dps, vector <int> hp) 
{ 
    int sum = 0, lose = 0; 
    // For each fairy i (go in reverse). 
    for (int i= hp.size() - 1; i >= 0; i--) { 
        // Calculate the sum of dps from j=i to j=n-1: 
        // just add dps[i] to the sum from j=i+1 to j=n-1: 
         
        sum += dps[i]; 
         
        // The damage inflicted while killing fairy i is : 
        lose += hp[i] * sum; 
    } 
    // And done! 
    return lose; 
} 

Div2 Medium: IncubatorEasy (550 points)

Link to problem statement

We got a group of at most girls. Some girls love other girls and/or themselves. Love is not necessarily symmetric. You have the ability to give any girls a magical super power (Turn the girl magical) any time you want. Once a girl is magical she will cast a protection spell on all the girls she loves. Also, whenever a girl receives a protection spell, she will also cast the protection spell on all the girls she loves. Thus when you set a girl magical, you may create a chain reaction of many girls casting protection on many other girls and so and so (it is even possible that the girl you made magical ends up protected after all of this).

The objective is to maximize the number of girls that are magical but not protected.

In effect, the objective of the game is to select the sub-set of girls that you will make magical. Then simulate all the process, all girls that are magical or protected cast the spell on the girls they love. Until there are no changes possible. Finally, count the number of girls that are magical but not protected. Return the maximum number you find.

That is most likely the intended approach. The number of girls has a small limit (10). There are going to be at most 2¹⁰ sub-sets of girls you can pick. So, as long as you do the simulation part fast enough, the execution time should not be a problem.

Simulate this

The simulation part. Here is both a proof to show that it can be done in O(n^3) and also a suggestion to simplify the code a bit. How about we ask ourselves (If this girl was made magical or protected, what is the resulting set of girls that will eventually becomes protected because of this?). If girl i is made magical or protected these are the girls that will become protected because of that:

• Girls loved by girl i.
• Girls loved by girls loved by girl i.
• Girls loved by girls loved by girls loved by girl i.

An easier way to see this is that, girls that are loved by girls that are loved by i, are actually indirectly or (much better) transitively loved by girl i. What we have to do here is turn the [love] relation into a transitive relation. By that , we will have to make the transitive closure.. In effect, we will turn the love matrix, into a matrix that gives, for each i, a list of girls that are loved directly or indirectly by i. The list of girls that will eventually become protected if girl i becomes magical or protected.

In order to make the transitive closure, we can use the very easy Floyd-Warshall algorithm. It works like this: For each girl k, find pairs (i,j). If girl k can act as a love intermediary between i and j, then i and j become connected. See more details at the code section of the wikipedia article or at the code at the end of this post.

Bruteforce this

A important thing to mention is how to use brute force to find all 2ⁿ sets of girls to make magical. You could use backtracking., but to be honest, in programming contests, we do not use that to generate all sub-sets. Instead, we use bitmasks!. It is the power of binary numbers! Read this tutorial by bmerry for more info.

Code

So much to mention. Note how the complexity is: O(n³ + 2ⁿ*n²). For n=10, this is actually pretty fast.

int maxMagicalGirls(vector <string> love) 
{ 
    // Let us use Floyd-Warshall to turn the love[][] matrix 
    // into its transitive closure: 
    int n = love.size(); 
    for (int k=0; k<n; k++) { 
        for (int i=0; i<n; i++) { 
            for (int j=0; j<n; j++) { 
                if ( love[i][k]=='Y' && love[k][j]=='Y' ) { 
                    love[i][j] = 'Y'; 
                } 
            } 
        } 
    } 
    // now love[i][j] is 'Y' if making i protected or magical 
    // will imply that j becomes protected. 
    int best = 0; 
    // Use the bitmask called mask, to generate all subsets 
    // of the n girls: 
    for (int mask=0; mask<(1<<n); mask++) { 
        int protMask = 0; 
        // For each girl: 
        for (int i=0; i<n; i++) { 
            if ( mask & (1<<i)) { // If she belongs to the subset 
                // Find all the girls that (according to the transitive closure) 
                //  will become protected because of i. 
                for (int j=0; j<n; j++) { 
                    if ( love[i][j]=='Y' ) { 
                        // Then add the girl to the protected subset. 
                        protMask |= (1 << j); 
                    } 
                } 
            } 
        } 
        // We got a set of magical girls, and the set of girls that become 
        //  protected after that. Who are the girls that are magical but  
        //  not protected? Just the subtraction between the two sets. 
        //  or the intersection between magical and the complement of protected 
        int sub = (mask &~ protMask); 
        // __builtin_popcount(sub) returns the number of 1 bits (elements) 
        //  so that is the number of girls that are magical and not protected 
        best = std::max( best, __builtin_popcount(sub) ); 
        // remember the best. 
    } 
    return best; 
} 

More to come.

I pretend to do div2 hard and div1 medium later. Perhaps If I am VERY motivated will do div1 hard as well.

Comments, corrections, rants, criticisms, etc

Feel free to comment, really.

Read More

Test SRM the 16th

http://apps.topcoder.com/forums/?module=Thread&threadID=764869&start=0

After a successful Test SRM on September 25, we are planning to have another one on next Tuesday (October 16th), at 11:00 EDT. It will be followed by a Test MM that starts next Wednesday (October 17th) at 13:00 EDT and lasts for 1 week.

For Test SRM, we again will reuse random problems from the period of SRM 200 -- SRM 400. We will either override the standard applet or I'll post connection link here later.

For Test MM, we will reuse the problem PolygonEstimation from the recent TCO'12 Championship Round. It will either use standard website interface or I'll post participation details here later.

Both rounds are not rated.

Let us fill this one up. It is much better to participate in an actual contest environment than to practice random problems in the arena. Even if you have seen the problems before, funny things happen and you might find them hard or interesting to solve again (has happened...).

Also, note that in the case of PolygonEstimation, it might actually be a interesting match. There is always room for improvement on the algorithms that the top places were using.

Read More

TopCoder SRM 557 - finally

SRM 557

Explanation for division 1 Easy and match recap. Explanations for div2 easy and div2 medium.

It feels like it has been ages since the last SRM. Here we go again.

It began with a bang. The 250 points problem reminds me a bit of a problem I wrote in the past, but I cannot remember its name. Something with black and white squares. They are very different problems, but I do remember that that problem was very tricky. This 250 points problem had like 8 examples, so I sort of felt it was going to have tricky written all over it. And decided to be careful rather than fast.

Div1 250: FoxAndMountainEasy

So, you start at height h0, is there is a sequence of n up and down moves such that:

• Each up move increases height by 1
• Each down move decreases height by 1. It is invalid to go bellow height 0.
• The given string history is a substring of the sequence of moves.
• The height after all of that stuff is hn

n is at most 100000. This problem gave me the feeling that it was initially intended for the TCO finals, but later they adapted it to SRM difficulty by reducing the constraints and adding plenty of examples.

The solution goes as follows: First process the history substring. After executing this series of moves, how much will be the netChange of the current height? (This is just equal to (number of Us) - (number of Ds). So if your current height is b before starting the sub-sequence of moves, the height after doing so will be b+netChange.

There is a catch though, if there are many D characters in the history sequence and not preceded by enough U characters, then the starting height before running the sequence, b, cannot be too small. b has to be large enough such that the current height while executing the subsequence is never bellow 0. (This can be calculated with a simple for loop - just simulate the movement starting at height 0, and remember the lowest height, if this lowest height is negative, then -lowest height is the minimum height value for b). We will call this required height before the subsequence - minStart.

After you have two things: netChange and minStart. We just need to do some extra things. There are (n - size(history)) moves left that we have to pick. Now here is the thing, the order of the moves does not matter a lot. We really only care about the height before the sub-sequence being at least minStart. Let us say that we are going to make u up moves, this means we will do d = (n - size(history) - u) down moves (in addition to the moves in history). Since we want the height before running the steps of the subsequence to be as large as possible, then it is better to first run all the u up moves before the sub-sequence and then all the d moves.

Due to the small constraints, we can just loop for a possible value of u between 0 and n-size(history). Then verify a couple of conditions: a) Is the height after running the first u moves at least minStart? . and b) Is the height after running all the moves, including the u up moves, the moves in history and the d down moves equal to exactly hn?. If you find a value of u for which the conditions are true, the result is YES.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct FoxAndMountainEasy
{
    string possible(int n, int h0, int hn, string history)
    {
        int netChange = 0;
        int minStart = 0;
        for_each(ch, history) {
            // just simulate the movement, if ch=='U', increase
            netChange += ( (*ch == 'U') ? 1 : -1);
            // too low? remember this for minStart
            minStart = std::max(minStart, -netChange);
        }
        // Pick a value for u, the number of up moves done right at the start
        // and before the moves in the history string: 
        for (int u = 0; u <= n - history.size(); u++) {
            // the number of down moves to do later:
            int d = n - history.size() - u;
            // Do things work out?
            if ( (h0 + u >= minStart) && (h0 + u + netChange - d == hn) ) {
                return "YES";
            }
        }
        return "NO";
                 
    }
};

I took my time. Also , I made a couple of mistakes. It is a good thing the examples were so strong. (At first, I was first running all the up moves , then the down moves and finally the history moves. That is not correct.). I knew though that even with the strong examples, there were going to be many challenge opportunities. (And I also was not sure I was not missing a corner case).

Happened later

Then I opened the 550 points problem. Tried many things but faced some dead ends. Went back to 250, trying to think of corner cases. Opened 1000 5 minutes before the end of the coding phase and it seemed interesting.

The challenge phase was interesting because some people had very different solutions , and some were extra clever (or perhaps too clever?). I knew many of those solutions were going to have bugs, but it is not really easy to read them.

I was lucky though, because I caught a solution with an obvious bug. It began by checking if (hn - h0) % 2 != n % 2 and returning "NO". This logic is correct, and perhaps the approach needed this extra check. But there is something very wrong about the languages like c++ and Java that we love so much. Some language designers thought it is a useful convention to make the % operator return a negative number if the dividend is also negative. In my opinion, this feature is never useful and almost always just a cause of bugs. Modular arithmetic works by stating -1 belongs to 1 modulo 2. So it does not make sense. This bug with % operator has caught me in the past, so this time I could sense it and gained 50 points. Then I tried to find more instances of that mistake, but other coders doing this parity check took better previsions (In some cases though, I am not sure if intentionally).

Comments / etc?

Feel free to post your own opinions and accounts. I liked this match. It was a bit tough. But it is good to be back at competition. I am tired of watching people compete.

Read More

Surprise test SRM the 25-th (Tomorrow!)

http://apps.topcoder.com/forums/?module=Thread&threadID=762941&start=0

After the TCO, TopCoder plans to start releasing functionality updates and bug fixes into both algorithm and marathon competition software. This will be done via sofware competitions, so in addition to algo/mm systems becoming better, those of you active at software side will get a chance to win some money for helping us make them better.

Last several months were devoted to different preparations in order to make it possible (some of you could have noticed assembly contests we've run for that purpose). People who previously developed those systems are no longer working at TopCoder and it happened so that large part of knowledge about them was lost. Even putting together a code to be used for further updates presented a certain challenge, which now is close to be solved.

At this point we think we have a codebase which resembles the current competition systems very closely (we know about a couple of minor differences, but almost everything is the same). While we've done quite a lot of testing, we still feel it would be useful to have even more extensive testing.

Therefore we would like to deploy this new code temporarily instead of the current systems and use it to conduct a test SRM. The more people compete in this, the more feedback we will be able to gather, so we invite and kindly ask all of you who can take part to do this tomorrow.

Some more details:

- We will reuse problems from some old SRMs (between 200 and 400). Exact problems to use will be chosen more-less randomly.

- The exact time of the SRM is not yet known, since we exactly don't know how much time it takes to do the deploy and some difficulties can potentially arise during this process. In fact, it's even possible that we won't be able to conduct this SRM tomorrow due to some unforeseen difficulties, though of course we'll do our best to conduct it. We will announce the exact start time in this thread at least 2 hours before the actual start. It is almost certain that start time is 2 PM or later.

- The SRM is not rated. We can't guarantee that SRM runs smoothly, since the code has not been tested very extensively and in fact, it is the purpose of this SRM to find out problems (hopefully and most likely, minor ones) with this new code.

If you have any questions, please feel free to ask here.

Read More

Codeforces #140 (Div 1)

Another attempt to finally participate in codeforces again. This was more successful than the last one because for once I have registered for the match.

Problem A : Flying Saucer Segments

Link to statement

This reminds me of Hanoi towers although it is a little different.

We got n aliens in segment 1 that we want to take to segment 3. Define the function that solves that f(n). It is better to try to move the one alien with the smallest rank to the third segment first.

We cannot move the lowest-rank Alien to segment 2 until we move all the other Aliens to segment 3. The solution for this step is f(n-1). As that is the cost to move n-1 Aliens, since the other Alien has the lowest rank, it will not affect their costs.

We can now move the lowest-rank Alien to segment 2. But now we will not be able to move it to segment 3 until we move the other (n-1) Aliens from segment 3 to segment 1. By symmetry, the cost will also be f(n-1). Then we can move the smallest Alien to segment 3 (cost 1).

We now got a very useful state, the lowest-rank alien is in segment 3, and the other aliens are in segment 1. We need to move the remaining aliens to segment 3, add f(n-1) again.

In short, the formula to solve f(n) is : 3*f(n-1) + 2. The base case is f(1) = 2 (Two steps to move a single alien).

The problem is then about calculating f(N) using that recurrence. Believe it or not I found myself having the most issues with this. A formula is be: (3⁰+3¹+...+3^n-1)*2. But I prefered to use a linear recurrence (and matrix multiplication) during the match.

I took way too long to solve this problem.

Problem B : Naughty Stone Piles

Link to statement

This one required a bit more thought. Anyway, imagine if K was at least n-1. Then it would be best to move the n-1 smallest piles to the largest pile. This ensures a minimum possible cost equal to the sum of the n-1 smallest piles.

With more imagination, imagine that k is exactly the half of n-1. At the end, you will move k piles containing all the stones to the largest one. This is still the sum of the n-1 smallest piles. However, in order to reach a state with k piles, you first need to move k piles to merge the piles into a single group of k piles. The piles you move in this phase will have their cost repeated in the total cost. It is best to pick the k smallest piles, move each to any of the other k piles and the total cost will be: 0*(largest pile) + 1 * (k largest piles that are not the largest ever) + 2*(k smallest piles).

In fact, the maximum number of piles you can move in the second phase is k*k. To put it simply:

• The last phase involves verifying that the largest pile now contains all stones (Cost 0 * (size of largest pile) )
• The second-last phase involves moving k piles to the largest pile. The total cost is: 1*(total size of the n-1 piles).
• The third-last phase involves moving k*k piles. to other k piles. The cost is sum(of the n-1-k smallest stones).
• The fourth-last phase involves moving k*k*k piles. to other k*k piles. The cost is sum(of the n-1-k-k*k smallest piles).

And so and so, there is our algorithm. The largest pile will cost 0. The k next largest piles will each be added only once. The next k*k piles will each be added twice. The next k*k*k will each be added thrice and so and so...

You can calculate the cost in O(log_k(n)). Note that k can be 1, which turns it into O(n). The total complexity is O(q*log(n)) as long as you make sure not to calculate the case k=1 more than once.

int n, q; 
long a[100000]; 
long acum[100001]; 
long k[100000]; 
long res[100001]; 
 
long solve(long K) 
{ 
    long res = 0; 
    long N = n; 
    long p = 0; 
    long r = 1; 
    while (N > 0) { 
        long hi = N; 
        long lo = std::max(0LL, N - r); 
         
        // p times the sum of the stone piles between lo and hi.  
        res += p*(acum[hi] - acum[lo]); 
         
        N = lo; 
        if (r > N / K) { 
            //we don't want overflows here... 
            r = N; 
        } else { 
            r = r*K; 
        }        
        p++; 
    } 
    return res; 
} 
 
void solve() 
{ 
    memset(res, -1, sizeof(res)); 
    sort(a, a+n); 
    acum[0] = 0; 
    for (int i=0; i<n; i++) { 
        acum[i+1] = a[i] + acum[i];  
    } 
    long whenOne = solve(1); 
    // when k=1, solve(k) is linear in complexity, you do not want it 
    // to be executed many O(q) times... 
    for (int i=0; i<q; i++) { 
        if (i > 0) {  
            cout << " "; 
        } 
        cout << ( (k[i] == 1)? whenOne : solve(k[i]) ); 
    } 
    cout << endl; 
} 

I went to have lunch between figuring out the solution and implementing it. Slow to solve is today's theme.

Problem C : Aniversary

Link to statement

Did not really have much time to think of a solution for this. Google Gibonacci GCD and you will find out that there is a very interesting property about the GCD of Fibonacci numbers. In effect, since the GCD of Fibonacci numbers is equal to the X-th Fibonacci number such that X is the GCD of the indexes of the Fibonacci numbers (And also because the larger the index, the larger the Fibonacci number) then the problem becomes about finding the largest GCD of a k-subset of numbers between l and r, inclusive. Then use this largest GCD as an index for the Fibonacci function (if the value is large, you can use Matrix multiplication to find out this large Fibonacci number modulo m).

Could not solve the sub-problem.

Let us see how it goes.

Opinions, corrections, complaints, etc

Feel free to post comments.

Read More

Learning to find bugs

In SRM 556, I made an algorithmic mistake in a problem that completely ruined the day (although the failed challenge was a larger factor, BTW, I found out why my challenge did not work out. It turns out that the solution I tried to challenge had two major bugs, but I only noticed one, but in the specific test case I gave it, the second bug made it work.

I keep saying this. After a match, ask yourself what should you have done to solve one more problem than the amount of problems you solved correctly? In case of failing system tests due to a bug that amounts to modifying a single line of code, then the answer is "find the bug before the end of the coding phase". But how?

Well the answer is in remembering the match. I actually submitted the first two problems quite fast yesterday. So I had like 40 minutes to do basically nothing. I tried to put some interest in div1 1000. But I kept having the feeling I had to find bugs in the other solutions just in case. I kept reviewing the codes and not finding anything. I think that was a mistake. Because we can do better than that to find bugs.

Bruteforce

In the aftermath, I kept reviewing the events. I noticed that it is not difficult to make a bruteforce solution for this problem that works in all right speed for (number of digits) <= 17.

It is not difficult. After placing the first digit card. Then you have two choices for the side at which you place the following cards. So if there are n cards, there are 2ⁿ choices of numbers you can make. A single bruteforce using bitmasks can simulate all the cases. Then you can just compare the generated strings and find the one that works better as a result.

// Brute force solution. 
string minNumberBrute(string digits, string lowerBound) 
{ 
    string best = "z"; //represents a very large number... 
                      // in string lexicographical comparisons 
                      // "z" is larger than any chain of digits. 
    int n = digits.size(); 
    // try a mask for the 2^(n-1) choices 
    for (int mask=0; mask < (1<<(n-1) ); mask++) { 
        string x = string(1, digits[0] ); 
        for (int i=0; i<n-1; i++) { 
            // depending on the choice, put the digit left or right 
            if ( mask & (1<<i) ) { 
                x += digits[i+1]; 
            } else { 
                x = string(1, digits[i+1]) + x; 
            } 
        } 
        // compare and remember the best. 
        if (x >= lowerBound) { 
            best = std::min(best, x); 
        } 
    } 
     
    return (best == "z") ? string("") : best; 
} 

Generating test cases

The idea is then to make a program that generates random test cases of 17 digits runs the solution I submitted and the brute force solution and compares the results. If they are the same, repeat. Else output a message saying that the program found a bug.

In c++, use the srand() function to initialize a random number generator. It is very convenient to always use a fixed seed. This way you can repeat the experiment in case something went wrong. (It could happen that your brute force implementation had bugs).

Then use rand() function to generate each of the 17 digits in each of the strings. There are two ways to use rand() to generate integer numbers within a range: A correct one, and an "almost" correct one.

You might use %. Like this page describes: http://www.cplusplus.com/reference/clibrary/cstdlib/rand/, but keep in mind it is not really uniform. If you really want uniformly random then you will need to use something like (int)(X * (rand()/(float)RAND_MAX) ). I just used %. With rand()%10 you get a number from 0 to 9, add it to '0' and you get a random digit.

Some critical thinking please

If you find a mismatch between your solution and bruteforce , it does not always mean you found a bug in your solution. It could be a bug in bruteforce. This is the problem with this idea. You have to develop and debug twice and brute force solutions are not always very easy to implement.

There is also another problem. Random test cases might not be the best way to find bugs in your specific code. Perhaps your code needs something very specific to fail. The alternative is to, instead of using random, try making up your challenges yourself. But this requires you to already suspect that a part of your solution might be wrong. It might also happen that your bug is only found when the size of the input is large, and in that case, you cannot use brute force to test...

Write it down

If you truly found a bug. Then write the case you found down. Once you understand the bug in your solution, resubmit and keep it in mind at the time of the challenge phase. Maybe this information will be of benefit...

Results

Ok, so I tried to measure how well this would help me to find a bug in my failed 500 yesterday. For this specific bug, it took only about 50 random test case attempts before it found a mismatch. I also found out that 2 of the 3 other guys who failed system tests in my room would fail the case I found. I think next time that I have so many time after solving div1 500 I will do this again, because trying the div1 1000 out rarely pays.

Read More

SRM 556 : #@!$%!

I am getting tired of this. Every latest SRM is the same situation. Approachable div1 easy and div1 mediums thus everyone solves them. But I take too much time to solve the easy a lame mistake stops me from solving div1 medium. Thus I end up with very low score whereas most people have two problems. Rating is killed. Over and over and over again. Can we go back to the times with very hard problems? I am starting to miss them. At least when the div1 easy is hard a low score can still allow you to keep your yellow rating.

Div1 easy

Nothing to see here. Just a BFS. I took very long because I used the wrong variable in one index.

Div2 medium

You are given a stack of digits. Initially, place the top digit on a table. Then place the top of the remaining digits either to the left or right of the digit on the table. Repeat placing each top digit to the right or left of the group of digits in the table. When you are finished, a number will be generated.

The number should be the smallest possible number you can make that is larger than or equal to lowerBound. If it is impossible to make a number larger than or equal to lowerBound return ""

So, at first I thought it was a typical [use dp to build numbers by digits] problem. Then I noticed that the top rule makes it a bit harder than usual. Then I noticed that you can still solve it like that.

It is important to make sure to make a number greater than or equal to the bound. Thus we need to somehow add numbers from left to right. But there is a catch, at some situations you might to place a digit to the right. More formally, let us do the opposite. Instead of placing the top card in the center of the table, think of the problem as first placing the bottom-most card either to the left side or the right side of the available space. Repeat until you run out of cards.

Thus we start from the largest index of the stack of digits, and we have a decision to make: We can place it left or we can place it right. There are some details to cover. We need to remember if the number we are building in the left side is already greater than lowerBound (If it is greater than, then we can place any digit on the remaining left side, else we can only post digits greater than or equal to the specific digit position in lowerBound. Thus we will call a variable greater.

The other catch is that, when placing digits to the right side, they might be smaller than the specific digit position. Note that this means that later moves should be done in such a way that the number is guaranteed to be greater before the right-most index is reached. This will be the variable mustGreater.

In the base case, we will reach a moment in which all available positions to the left and right are used - except a last one. In this case, we will have only one digit left. We must ensure that the digit follows the rules (If the digit is not greater yet, then the digit must be greater than or equal; Also make sure that if mustGreater, the number should be greater after placing this digit.

This is where my mistake was. I missed one special case (and I blame the examples for being so simple that this was not reached). What if mustGreater is true, but we place a greater digit to the right side? This means that the mustGreater condition has already been fulfilled. But after this, notice that if one of the following digits placed to the right side is again smaller, then mustGreater must be set back to true.

yadda yadda yadda, this should translate to a dp:

struct LeftRightDigitsGame2 
{ 
    int n; 
    string digits, lowerBound; 
    string dp[50][51][2][2]; 
     
    // How to fill the remaining interval [a, b[ if: 
    //  The left side is already greater <==> (greater) 
    //  The right side must be precceeded by a greater number <==> (mustGreater) 
    string rec(int a, int b, int greater, int mustGreater) 
    { 
        string & res = dp[a][b][greater][mustGreater]; 
        // We are using memoization, at first all contents of dp are "". 
        // but that is invalid because the result is either z or at least one digit. 
        if (res == "") { 
            if (a+1 == b) { // base case 
                // the position of the next bottom-most digit we have not 
                // used yet. 
                // We have used (a) digits for the left side and n-b digits for 
                // the right side. 
                // index 0 is the top, so do it in reverse... 
                int p = n - (a + n - b) - 1; 
                 
                 
                // "z" is the lex greatest string, a sort of infinite. 
                // Lex smallest string is the same as smallest number in this case. 
                 
                // If left side it is already greater, then we can place any digit 
                if (greater || (digits[p] >= lowerBound[a])) { 
                     // as long as the digit follows the mustGreater condition... 
                    int ngreater = greater || (digits[p] > lowerBound[a]); 
                    if ( !mustGreater || ngreater) { 
                        res = digits[p]; 
                    } else { 
                        res = "z"; 
                    } 
                } else { 
                    res = "z"; 
                } 
            } else { 
                res = "z"; 
                // p: same stuff as above, really... 
                int p = n - (a + n - b) - 1; 
                 
                // put digits[p] to the left side. 
                // -  a is incremented. 
                // Make sure we only place smaller digits if left side is already "greater" 
                // maybe upgrade greater if we found a good case for that. 
                // 
                if (greater || (digits[p] >= lowerBound[a])) { 
                    int ngreater = greater || (digits[p] > lowerBound[a]); 
                    string tm = rec(a+1, b, ngreater, mustGreater); 
                    if (tm[0] != 'z') { 
                        res = std::min(res, string(1, digits[p]) + tm ); 
                    } 
                } 
                // put digits[p] to the right side. 
                // -  b is decremented 
                // - If digits[p] is smaller than bound, then something before must be greater. 
                // - But if digits[p] is larger, then it can cancel a previous requirement. 
                // - But if some other digit in the future is smaller, we will need the requirement again 
                // 
                int nmust = (mustGreater || (digits[p] < lowerBound[b-1]) ) && (digits[p] <= lowerBound[b-1]) ; 
                string tm = rec(a, b-1, greater, nmust); 
                if (tm[0] != 'z') { 
                    res = std::min(res, tm + string(1, digits[p]) ); 
                } 
                 
                // recursion works like that, if the decision leads to a valid case 
                // then you have the smallest number to fill the remaining interval... 
                // so append the digit you placed (to the left or the right) to 
                // generate the real candidate for smallest number. Take the minimimum 
                // out of both numbers. 
            } 
        } 
        return res; 
    } 
         
    string minNumber(string digits, string lowerBound) 
    { 
        this->n = digits.size(); 
        this->digits = digits; 
        this->lowerBound = lowerBound; 
        string tm = rec(0, n, false, false); 
        return (tm[0] =='z') ? string("") : tm; 
    } 
}; 

Div1 1000

Seemed interesting. My first idea was terribly wrong. Like a Max flow giving an capacity between source and a1 and between a2 and sink. And bn capacity between source and b1 and between b2 and sink. This approach was obviously wrong (because a path between b1 and a2 would count as flow sometimes). But maybe there was a solution to it?

Writer mentioned that the intended solution involves making compound nodes? Like (x,y) where x is the current position starting from a1 and y is the current position starting from b1. Maybe the writer meant something else. But this does sound like a good idea. hmnn.

Challenge phase

I discovered a code with a bug. But somehow the test case I crafted did not catch the bug. I have to investigate further once statistics re-appear (must be something silly). So to the top of thing, I lost 25 points in challenge. If I failed div1 easy as well, then the negative score would have kicked me to the worst rating in years. It is rule #1: DO NOT challenge.

Any questions?

As usual, feel free to place comments, questions, rants, opinions and corrections in this post's comments section.

What an awful sequence of terrible matches for me. No, the problem sets were all fine in these recent SRMs. But this situation is killing my rating. I am really mad this time, because without the hindsight in div1 500 I would have been in top 20. Without the failed challenge in top 150. And if I actually did the challenge correctly (the code WAS wrong) in top 100.

Read More