Codeforces #204 (div 1) Recap

So, I could only solve 2 problems and I am not entirely sure of them.

Problem A - The one with rounding

Link to problem statement

The first thing is to notice that all numbers are guaranteed to have exactly three decimal points. From now on. we can just care of the decimal part (x[i] will be number from 0 to 999), and minimize the absolute value of the difference.

• If x[i] is 0 (So it was a number that ends with .000, like 12.000), then no matter what we do, it will contribute 0 to the difference.
• Else if we choose to round down the number, the difference increases by (-x[i]) / 1000.0 .
• If we choose to round up, then the difference changes by (1000 - x[i]) / 1000.0.

n numbers have to be rounded up. If i of those numbers are zero, then the total difference will be: (1000 * (n - i) - sum(x[i]) ) / 1000.0. In other words, the only thing that determines the difference is the number of zeros that we round up. We can just brute force for this number and pick the best difference we find

// input:
string a[4000];
int n2; // n in the statement

// other:
int x[4000];

double solve()
{
    int n = n2 * 2;
    for (int i=0; i<n; i++) {
        istringstream st( a[i] );
        int z=-1, f=-1; char ch;
        st >> z >> ch >> f;
        x[i] = f; // only the modulo , the decimal digits matters
    }
    int res = 5000000;
    int z = count(x, x + n, 0);     // number of zeros
    int sum = accumulate(x, x+n, 0); // total sum
    
    // how many zeros will be ceil?
    for (int i = 0; i <= z && i <= n2; i++) {
        res = min(res, abs( (n2 - i) * 1000 - sum ) );  
    }
    // divide result by 1000
    return res / 1000.0;
}

During the match I first tried a badly-thought greedy algorithm. I even tested it comparing it with a bruteforce algorithm before submitting, but it still failed, apparently the bug with the lame greedy needed very specific input. But while coding the greedy algorithm I noticed the -x[i] and 1000-x[i], which helped me solve the problem correctly (assuming it passes)

Problem B - The one with permutations

Problem statement

The first thing I noticed was that result for the second example was a integer, that is too much of a coincidence. Somehow I decided that maybe the result is equal to (number of steps needed to sort the permutation without the random stuff) * 2 - 1. It turns out the estimation was wrong, but the idea was almost correct (I think).

Anyway, assume you have to do X steps in order to solve it correctly. After you make a step, your friend will throw a coin, and there is a 50% probability he will help you and a 50% probability he will make things worse. It appears to me that he helping you will always decrease the number of required steps by 1, and he not helping you will always increase the number of required steps by 1 (This in addition to the step you performed). The result is the following recurrence, 'f(x)` where x is the number of required steps.:

`f(0) = 0`
`f(1) = 1`
`f(x) = 2 + f(x-2)/2 + f(x) / 2`
`f(x) = 4 + f(x-2)`

We can just fill the recurrence iteratively.

int n;
int p[3000];


double solve()
{
    //a) cost to sort
    int res = 0;
    for (int i = n - 1; i >= 0; i--) {
        pair<int,int> mx = make_pair(-1, -1); 
        for (int j = 0; j <= i; j++) {
            mx = std::max(mx, make_pair(p[j], j));
        }
        res += i - mx.second;
        for (int j = mx.second; j < i; j++) {
            p[j] = p[j+1];
        }
        p[n-1] = mx.first;
    }
    // b) Recurrence:
    double dp[3];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= res; i++) {
        dp[i % 3] = 4 + dp[ (i + 1) % 3 ];
        cout << i << " ; " << dp[i % 3] << endl;
    }
    
    return dp[res % 3];
}

Problem C : The one with parenthesis and cycles

Statement

I didn't have much time to code it (less than 10 minutes), but I think I found a solution.

It appears to me that the best parenthesis sequence has to be cyclic because the cost function is cyclic. When n is even, it should be of length n, when n is odd, it should be of length 2n. Since m is guaranteed to be even, we can half it.

So we just need to generate the cyclic parenthesis sequence. The cost of the sequence is easy to find because the costs are cyclic. Constraints are large in the case n is odd. But I am pretty sure we can use a meet in the middle approach so that the process is `O(2^n)`.