Codeforces round #89

I have been meaning to participate in Codeforces again since a couple of months ago. But CF has the habit of always picking the worst possible schedules for me. Today was not going to be the exception, but thanks to social unrest, I didn't have class today so I tried CF again.

C - Fancy Number
Problem statement
I opened this first. In reality I think that in these division 2 contests I should open D first. What's done is done. I had a little disruption while solving it, went to eat something. Anyway.

At first I really didn't understand exactly what the statement meant by repeated digits. For example, 00001122 has 8 repeated digits. At the end I concluded that it means that at least one digit must be repeated at least K times.

So, there are only 10 available digits. Let us try the minimum cost to have one of those digits repeat at least K times AND the lex-first string that has such cost. Then we pick the best result among all digits.

Given a digit ch, build the minimum cost, lex-first string that contains that digit at least k times. We just need to pick the best k positions in which we will place ch. Of all positions, let's find the cost to turn that position into ch. Note that we should always pick the k minimum costs. Not doing that will yield a higher total cost to convert the string. However, sometimes there will be more than k positions we could use for the same cost. Then we need a tie-breaker to ensure that the first string is the lexicographically-first.

So, how about this, if two positions would yield the same cost to turn into ch, we need to pick the one that would yield the lexicographically-first string.

* If one of the positions had a digit larger than ch and the other didn't, pick the former.
* If both positions had a digit larger than ch, pick the earliest one. Because the first position has priority when doing lexicographical comparisons.
* If If both positions had a digit smaller than ch. Pick the latest position.

This is somewhere in which std::pair is helpful.

So, here is the solution:

int n, k;
string digits;

pair<int,string> make_best(char ch)
{

    set< pair<int, pair<int, int> > > pos;
    // Rate all the positions in the string
    for (int i=0; i<n; i++) {
        int low = 0;
        int ni = i;
        if (ch == digits[i] ) {
            low = 1;
        } else if (ch > digits[i]) {
            ni = -i;
            low = 2;
        }
        int c = abs( ch - digits[i] );
        
        pos.insert( make_pair( c, make_pair(low, ni) ) );
    }
    //pick the k best positions to put a ch there.
    string nw = digits; 
    int sum = 0;
    for (int i=0; i<k; i++) {
        set< pair<int, pair<int, int> > >::iterator q = pos.begin();
        int c = q->first;
        int ni = abs(q->second.second);
        nw[ni] = ch;
        sum += c;
        pos.erase(q);
    }
    return make_pair(sum, nw);
}

void solve()
{
    pair<int, string> best = make_pair(1000000, string("ERROR") );
    for (char ch='0'; ch<='9'; ch++) {
        best = std::min(best, make_best(ch) );
    }
    cout<<best.first<<endl;
    cout<<best.second<<endl;
}

A - B
There is really nothing to say about these problems. They are just about implementation. So , you better know your language. I failed A twice because I didn't expect Y to be considered a vowel and because I really didn't notice that you were supposed to convert upper case consonants to lower case. Need to pay more attention.


D - Caesar's Legions
Link to statement.
I think this problem was easier than C, to be honest. K1 and K2 were very low (<= 10) . I am not sure why. But there is a dp solution.

Let us say that we have r1 footmen and r2 horsemen left to place. The previous lastn positions, contain footmen or horsemen depending of the value of a variable lasttype, if lasttype = 1, then the previous lastn positions contain horsemen. So, we in fact remember the contents of the previous positions, we just have to make sure that lastn does not ever exceed k1 or k2 depending on whether they are footmen or horsemen.

Let f(r1,r2,lasttype, lastn) the total number of ways to solve that sub-problem. The final result will be f(n1,n2, 0,0) (There are n1 footmen to place, n2 horsemen, and we can pretend that there are 0 footmen in the previous positions). So, let us think of transitions:

* At each position, we can place a footman, or a horseman. Depending on what we do, we increase lastn or set (lastype = 1, lastn = 1) in case we placed a different type of unit than the previous one.


That yields the following dp solution:

const int MOD = 100000000;
int n1, n2, k1, k2;

int mem[101][101][2][11];

int count(int r1, int r2, int lasttype, int lastn) {
    int & c = mem[r1][r2][lasttype][lastn];
    
    if (c == -1) {
        c = 0;
        // place r1
        if (r1 > 0) {
            if (lasttype == 1) {
                c += count(r1-1,r2,0,1);
            } else if (lastn < k1) {
                c += count(r1-1,r2,0,lastn+1); 
            }
        }
        //place r2
        if (r2 > 0) {
            if (lasttype == 0) {
                c += count(r1,r2-1,1,1);
            } else if (lastn < k2) {
                c += count(r1,r2-1,1,lastn+1); 
            }
            c %= MOD;
        }
        
        if (r1 == 0 && r2 == 0) {
            //all done!
            c = 1;
        }

    }
    return c;
}

int solve()
{
    memset(mem,-1,sizeof(mem));
    
    return count(n1, n2, 0,0);
}

Problem E
Problem statement
Thank you CF, apparently I needed to be reminded that graph theory is not my strength.

Things that I tried and failed:
a) Assumed that for there to be a solution, there needs to be a Hamiltonian cycle in the solution. Then the solution is to build that cycle. At first, for some reason I was finding and building Eulerian cycles instead, and that's wrong. Once I tried to do Hamiltonian cycles instead, I noticed that the idea is probably wrong. Building such cycles is NP-hard :/.

Update: So the idea about cycles was close. All vertices must belong to the same cycle = They should belong to the same strongly connected component.

Hacks
Apparently CF thought that the best thing they could copy from TC was the randomness from the challenge phase. Unfortunately, you need flash to look at the solutions. Why? Really, why? You have this web-based contest system that is very portable and easy to setup, and you ruin it with flash? I mean , gosh.




Conclusion
Quite honestly, CF's problem sets seems to have gotten less annoying and better than back when I stopped it. Though this is only the div2 contest, I am not sure how div1 is now. Hacks however, really need to stop requiring flash.

I will participate in more CF contests, provided the schedule works for me.