Codeforces round #111 (div2 only)

Oh boy, I hate-respect these div2 only matches, because even though they are supposedly easier than matches with div1, I do terribly at them.

Problem A: Twins
As you want to increase the possibility that the coins you don't take are less than the ones you take. You are interested in taking the coins with the greater value. If you take X coins, take the X largest coins. You can try this for every value of X from 1 to N until you find a value in which the coins you take are enough to be greater than the remaining coins.

The examples were quite weak, during the match I accidentally sorted ascendingly instead of descendingly, yet examples were correct. I guess the existence of pretests can be a good pretext for adding weak example cases.

Problem A: Unlucky Ticket
First, say you are only interested in cases where the first half can match to greater values in the second half. Later you can just reverse the string and re-use your code to catch the second kind of unluckiness.

You have some digits on one side that have to be matched with greater digits on the other side. In fact, this is a typical bipartite matching. That's what I did during the match. I knew that there was likely a solution that didn't need that, but pasting a MaxFLow code you have coded years ago is a lot easier than thinking of something clever.

If you do want a clever algorithm, here is one: Let us count the times each of the digits appears in the right and left places. It is harder to find a digit greater than 8 than it is to find a digit greater than 1. So, you can just iterate from 8 to 0 (If 9 exists in the left side, it is impossible to match). Let us say right is the number of digits in the right side that can be matched to your current value in the left.

For d = 8, you want to match left '8' digits with something in the right. We can now use the right side's 9s, so let us say: right += rightcount[9]. Then we have to check (leftcount[8] <= right). If that is true, then there is a match for all 8 digits, else there is not and we can just return "NO". If there exists, do right -= leftCount[8].

For d = 7, you can now match you left side's 7 digits to the unmatched right digits greater than 8 and also those equal to 8. So you do right += rightcount[8]. Then if (leftcount[7] <= right), and so and so. IF you manage to match all left digits from 8 to 0, then there is a valid match.

Problem C: Find pair
I didn't like that this problem allows duplicates but tries not to mention how they are supposed to work. No single duplicate value in the samples. Thankfully, there is one in the pretests. I actually tried to handle them from the beginning but I made a mistake in my logic on how to handle them...

It is a coincidence, I was just writing the editorial for SRM 535 yesterday (I finished it last night, should come to topcoder's site soon). And the division 2 1000 from that match requires the same trick that is used in this problem. To turn the question of getting the element K of a sorted sequence into a counting problem.

Counting problem? Yeah, let us say you need element #K . Ask yourself: How many elements begin with -10^9, if the number is greater than K, then you can say with certainty that your element will begin with -10^9. Else do K -= (number of elements that begin with -10⁹) proceed to the next number, 999999999, how many begin with that number? Decide to use the number or decrease K again.

After deciding the first element, you can decide the second using the same logic. Note though that if the first element appears multiple times, it affects the number of elements the second element appears.

Of course, you cannot do that right away, the values can be very large or small. Just notice that the number of different values is at most 100000, so you can just use the values from a sorted array (or better, a map, look at my implementation next).

// long long caused the black plague. 
typedef long long int64; 
#define long int64 
 
int a[100000]; 
int n; 
long k; 
 
#define var(q, s) typeof(s) q=s 
#define for_each(q,s) for(var(q,s.begin()); q!=s.end(); q++) 
 
pair<int,int> solve() 
{ 
    map<int, int> numbers; 
    for (int i=0; i<n; i++) { 
        numbers[a[i]]++; 
    } 
    pair<int,int> res; 
    long amount = 1; 
    for_each(q, numbers) { 
        //how many pairs start with this number? 
        long s = q->second * (long)n; 
        if (k <= s) { 
            amount = q->second; 
            res.first = q->first; 
            //can do it 
            break; 
        } else { 
            k -= s; 
        }         
    } 
    //now the second part 
    for_each(q, numbers) { 
        //how many pairs end with this number? 
        long s = amount * q->second; 
        if (k <= s) { 
            res.second = q->first; 
            break; 
        } else { 
            k -= s; 
        } 
    } 
    return res; 
} 
 

If it wasn't for the duplicates condition, you could do something as easy as sortednumbers[ (K-1)/n][ (K-1)%n ] . If you have any doubts, just remember that this is how decimal numbers work. In order to select a number from 00 to 99... But duplicates would break this logic.

Problem D: The one with the spanning trees

I had a very strange idea about Kruskal algorith: Take a look to Kruskal's MST algorithm. You try edges in ascending order of weight. For each vertex you try, if it connects two different components, use it, else do not use it.

There is a catch, when there are many edges with the same weight that connect different components, you can pick any of them. My theory is that it does not matter which of those edges you pick, at the end of all the steps with the same weight, the same nodes will belong to the same components. This allows you to treat all edges in order of their weight, and deciding for each group of edges with a weight which of those edges are never useful, or always useful or only useful a handful of times. But this part is missing from me yet. I am not sure the theory is true either.

After the match, I learned thanks to codeforces coder sanchit_h, that there are a couple of easy to apply edge properties in regards to a MST: http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cycle_property. Need to improve my theory.