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.