SRM 546: relief

I figured I should post something about this SRM. I've been very busy these weeks because the semester is ending and I tried to win a t-shirt in the Marathon AND I am not assigned more editorials. But there we go.

Div1 250 - The one with the bit operations

I was just returning to the topcoder mindset after working a lot on an assignment. At the start of the match I felt like running in 10% of steam capacity. I truly felt dumb. I knew what to do to solve the problem, but I was having issues translating it to code.

Kleofas tail : If x is even, x = x / 2. If x is odd then x = x - 1. Repeat and repeat until you will eventually have a sequence of tons of 0s. Given K, A and B, return the number of numbers between A and B, inclusive such that the Kleofas pairs starting from number x eventually include K.

This is heavily related to the binary representation of a number. Let us say the binary representation of x is 10010010101. The sequence goes like this: 10010010101, 10010010100, 1001001010, 100100101, 100100100, 10010010, 1001001, 1001000, 100100, 10010, 1001, 100, 10, 1, 0, 0, 0, ... - If the right most bit is 1, it becomes 0 , else it gets removed. This means that there are two ways for a number x to eventually become K:

• The binary representation of K is a prefix of the binary representation of x.
• If K is even, the binary representation of (K+1) is a prefix of the binary representation of x.

Assuming that you have a function that counts the number of times a given number K' appears as a prefix in numbers between A and B, then you have an instant solution. But we can simplify it a bit more: Let f(A, K) return the number of elements X between 0 and A, inclusive such that K appears in their Kleofas tail:

• f( A , K) = 0 for (A < K).
• f( A, K = 0) = A+1 (All numbers between 0 and A, eventually reach 0.
• f(A, 2*K1) = f(A, 2*K1+1) + (number of times 2*K1 appears as a prefix). (In other words, K = 2*K1, which means K is even).
• f(A, 2*K2 + 1) = (number of times 2*K2+1 appears as a prefix). (In other words, K = 2*K2 + 1, which means K is odd).

We just need to calculate prefixes(A, K): The number of times K is a prefix of X for every X between 0 and A, inclusive.

The problem is how to do that... This is the moment at which my brain froze. At first I tried to do it arithmetically, but I could not. (It is possible, but slightly tricky). Eventually, I recognized that I was not at full brain capacity and that the best I could do would be a bullet (and idiot)-proof dynamic programming solution for the simple counting problem.

Now that I am in my senses, here is a quick approach. Imagine there are i bits after the K part in x. For example, if K=101 then x = 101?????. The minimum x that follows that condition is: 10100000 and the maximum x is : 10111111. Both values can be calculate easily given i. (The minimum is K multiplied by 2ⁱ, the maximum is the same plus (2ⁱ-1) ). Then the true maximum is min( K*2ⁱ + 2ⁱ-1, A). There are (true_maximum - minimum + 1) values of x. Then you can just iterate through all values of i until the minimum is larger than A.

// Number of times K appears as a binary prefix of numbers between
// 0 and A, inclusive.
long prefixes(long K, long A)
{
    long res = 0;
    long mx = 0;
    while (true) {
        long lo = K;
        long hi = Math.min(K + mx, A);
        res += hi - lo + 1;
        if (K > A/2) {
            break;
        }
        K *= 2;
        mx = mx * 2 + 1;
    }
    return res;
}
// Amount of times a number between 0 and A, inclusive contains
// K in the Kleofas tail :
long countGoodSequences(long K, long A)
{
    if (A < K) {
        return 0;
    }
    if (K==0) {
        return A+1;
    }
    long res = 0;
    if (K % 2 == 0) {
        res += prefixes(K+1, A);
    }
    res += prefixes(K, A);
    return res;
}

public long countGoodSequences(long K, long A, long B)
{
    // This allows us to reduce the number of arguments.
    return countGoodSequences(K, B) - countGoodSequences(K, A-1);
}

Mixed feelings about this problem. Although it was good, we have had too many of these (tricky binary operations) division 1 250s.

Div1 500: the one with digits

I was better now. I knew that if I wanted to save my rating I had to solve this problem. Luckily it turned out to be a typical digit dynamic programming. I am not sure why, but I find these problems very easy. I still needed a lot of time though, because when I coded it my brain was still not functioning and I left as many bugs as you would ever find.

Given N (Between 1 and 99...9 (15 times), inclusive) , digit1, count1 , digit2, count2. (count1 + count2 <= 15). Return the minimum number >= N that has digit1 at least count1 times and digit2 at least count2 times.

Thanks to the notes, we know that the result always fits a signed 64 bits integer. This means 18 digits. We will say that the maximum number has 20 digits at most. The idea is to use a recurrence relation. f(count1, count2, p, eq, zero): We have already decided the p first digits. eq means that the number is currently equal to N. zero means that the number is currently equal to 0. count1 is the minimum number of times we need to add digit1, and count2 works the same way. For convenience, we will say that numbers are strings, strings of digits. Once we get the final result we can convert it to long long. f() will actually find a string of MAX digits, it will have leading zeros when the result needs less than MAX digits.

Let us say p==MAX, this means that we have already decided all digits, what is the minimum remaining number? Well, if count1 or count2 is positive, then there is no way to fulfill this requirement anymore. Thus there is no result. We will mark instances with no result as infinite. If count1 and count2 are 0, then the result is the empty string - do not modify any new bit.

For another p, then we can try all digits from 0 to 9. Well, actually, we sometimes cannot. If eq==1, it means that all of the previous digits were equal to N, this means that the digit at first position cant be smaller than the digit at the same position in N - Because that would make our result smaller than N. If eq==0, then we can use any digit from 0 to 9. After picking a digit, the values of count1, count2, eq and zero will change according to it and we will have a new instance of the recurrence. (Just note that when zero==1, we cannot count digit 0 as part of the digits to reduce from the count1 requirement, because it is a leading 0 and will not actually appear in the number. The same happens with digit2)

And that's it:)

const int MAX = 20; 
struct FavouriteDigits 
{ 
    string dp[MAX+1][MAX+1][MAX+1][2][2]; 
    bool vis[MAX+1][MAX+1][MAX+1][2][2]; 
     
    string R; 
    string rec(int p, char digit1, int count1, char digit2, int count2, int eq, int zero) 
    { 
        if (! vis[p][count1][count2][eq][zero] ) { 
            vis[p][count1][count2][eq][zero] = true; 
            string & res =  dp[p][count1][count2][eq][zero] ; 
            // We mark infinite as a string that begins with : 
            if (p == MAX) { 
                // base case 
                if ( count1 == 0 && count2 == 0) { 
                    res = ""; 
                } else { 
                    res = ":"; // no luck 
                } 
            } else {                 
                res = string(MAX - p, ':'); 
                for (char ch = (eq?R[p]:'0') ; ch <= '9'; ch++) { 
                    int ncount1 = count1, ncount2 = count2; 
                     
                    int nzero = zero && (ch == '0'); //once we use a digit different to 0 
                                                     // the number stops being equal to 0. 
                     
                    // update count1, note that if digit1 is 0 and zero==1, 
                    // it does not count (leading zero) 
                    if (ch == digit1 && (ch!='0' || !zero) ) { 
                        ncount1 = std::max(ncount1-1, 0); 
                    } 
                    // update count2, similar story 
                    if ( (ch == digit2) && (ch!='0' || !zero) ) { 
                        ncount2 = std::max(ncount2-1, 0); 
                    } 
                     
                    int neq = ( eq && (ch==R[p]) ); //once a character differs from N 
                                                    //the new number is larger. 
                    string x = rec(p+1, digit1, ncount1, digit2, ncount2, neq, nzero); 
                    // x begins with :, there is no result in that direction... 
                    if (x.length() > 0 && x[0] == ':') { 
                        continue; 
                    } 
                    //concatenate, we now have a good result remember the minimum. 
                    res = std::min(res, string(1,ch)+x); 
                } 
            } 
             
 
        } 
        return dp[p][count1][count2][eq][zero]; 
    } 
     
     
    long findNext(long N, int digit1, int count1, int digit2, int count2) 
    { 
        // convert N to a string, with the appropriate leading zeros. 
        { ostringstream st; st << N; this->N = st.str(); }; 
        this->N = string(MAX - R.length(), '0') + this->N; 
         
        memset(vis, 0 ,sizeof(vis)); 
        string s = rec(0, digit1+'0', count1, digit2+'0', count2, 1, 1); 
        // convert s to from string to long: 
        istringstream st(s); 
        long x; 
        st >> x; 
        return x; 
         
    } 
}; 
#undef long 

This problem was better. But it is odd to have two problems in the same match and same division that can be solved with the same approach. (I used a similar digit dp to solve 250).

Challenge phase, etc.

The example cases for div1 500 seemed quite strong. I knew div1 250 was tricky, but I also knew that I would likely mistaken if I tried to challenge. I preferred to go to lunch during the challenge phase. Returned, and after all the hours it takes results to arrive lately, I noticed I passed everything and somehow even my slow submissions were enough for top 100. I cannot believe I managed to increase my rating and even reach (again) the area that is close to 2200. I was just lucky though that div1 500 was my style of problem.

As far as the problem set goes. It is not misof's best problem set. But that is only because he set a great standard in previous problem sets. It was a good match, nevertheless. But we writers need to avoid those bit operations in div1 250 for a while.

SRM 595: And now , for something completely different

Believe it or not, I do have a life outside of programming contests. That life, however, involves barely studying Computer Science.

I have a sort of a final today, which overlaps with SRM 525. I always try to organize my subjects to minimize the amount of SRMs I lose. Unfortunately, it was not possible to avoid this overlap. In cases where the overlap is forced, I prioritize the SRM unless the class is very urgent/important. But today that's not the case.

However, I am tired of this, maybe I can't control the overlap, but I can still control my fate. I can still decide to participate in SRM 525. Here is how it goes: I can arrive to the sort of final at 08:30, the SRM starts at 08:02. I do not have the ability of teleportation. So, what I will do is participate until exactly 08:15 AM. That gives me 13 minutes which are statistically enough for me to solve the division 1 easy problem. Also statistically, that might be enough for me to gain rating points.

There are risks. If for some reason I don't manage to solve the problem on time. Or if the medium problem turns out to be more approachable, then the easy won't be enough. Let us see what happens.

Update after the SRM: Experiment went sort of ok.

Div1 300

You have a grid of at most 30x30 cells. There may be coins in each cell. You can move all the coins up, left, down or right in one step. If in any step a number of coins get out of the grid, they are lost forever. Return the minimum number of turns needed to end with exactly K coins. Or -1 if it is impossible.

First of all, note that at the end you will necessarily end with the coins inside one of the sub-rectangles of the grid. Thus if no sub-rectangle contains exactly K coins, it is impossible. If one does, however it is possible. There are w*w*h*h, total sub-rectangles. If one of these rectangles has K coins, then we can try to find the required number of steps to remove the coins in the cells outside it.

Now, for each rectangle we have to count the number of coins. We can actually do it in O(w*h) time. Many people did not notice that the constraints are small enough to allow a total time complexity of O(w*w*w*h*h*h), so they went with a way of counting the number of coins in O(1) time (by first making a matrix of accumulated sums).

Now that we know that a given sub-rectangle has K coins, we need to find the minimum number of steps to remove the coins in the other rectangles. This is similar to just removing rows or columns. First of all, I'd like to point out that we can treat rows and columns separately. Moving horizontally won't affect your requirements to move vertically.

So, we have to make a decision, we will go up a X number of times and down a Y number of times. Minimize (X+Y). What is cool here is that every move up, will add a requirement for a move down (There will be a whole new column that we have to remove). And viceversa. Thus if we first do the moves up required to clear the top rows, we will need to do a similar amount of extra moves down to return the grid to normal before removing the bottom rows.

Long story short, if c id the number of top rows to remove and d is the number of bottom rows. Then the number of moves will be at least (c+d) on top of that, we will need T extra moves, and T is either c or d. It is best to minimize T, and that is done by taking the minimum between c and d.

Now, the same will happen with columns, if you have to remove a left columns and b right columns, the number of steps will be (a + b + min(a,b)).

The rectangle with K coins that needs the minimum number of steps is the overall answer.
....

I then went to the "exam". To my disgrace it started later than I thought so I would have had more time to try the medium problem. During all the waiting time I had a lot of second thoughts about the approach, but I was able to think of many arguments to show that it is correct.

I was able to grab a computer during the challenge phase and tried to open some solutions. My room seemed very solid.

The final result: I passed system tests. The speed in 300 was indeed good enough to gain rating. But I am still in [less than 1900] land, which is not where I feel I should be.