Codeforces #140 (Div 1)

Another attempt to finally participate in codeforces again. This was more successful than the last one because for once I have registered for the match.

Problem A : Flying Saucer Segments

Link to statement

This reminds me of Hanoi towers although it is a little different.

We got n aliens in segment 1 that we want to take to segment 3. Define the function that solves that f(n). It is better to try to move the one alien with the smallest rank to the third segment first.

We cannot move the lowest-rank Alien to segment 2 until we move all the other Aliens to segment 3. The solution for this step is f(n-1). As that is the cost to move n-1 Aliens, since the other Alien has the lowest rank, it will not affect their costs.

We can now move the lowest-rank Alien to segment 2. But now we will not be able to move it to segment 3 until we move the other (n-1) Aliens from segment 3 to segment 1. By symmetry, the cost will also be f(n-1). Then we can move the smallest Alien to segment 3 (cost 1).

We now got a very useful state, the lowest-rank alien is in segment 3, and the other aliens are in segment 1. We need to move the remaining aliens to segment 3, add f(n-1) again.

In short, the formula to solve f(n) is : 3*f(n-1) + 2. The base case is f(1) = 2 (Two steps to move a single alien).

The problem is then about calculating f(N) using that recurrence. Believe it or not I found myself having the most issues with this. A formula is be: (3⁰+3¹+...+3^n-1)*2. But I prefered to use a linear recurrence (and matrix multiplication) during the match.

I took way too long to solve this problem.

Problem B : Naughty Stone Piles

Link to statement

This one required a bit more thought. Anyway, imagine if K was at least n-1. Then it would be best to move the n-1 smallest piles to the largest pile. This ensures a minimum possible cost equal to the sum of the n-1 smallest piles.

With more imagination, imagine that k is exactly the half of n-1. At the end, you will move k piles containing all the stones to the largest one. This is still the sum of the n-1 smallest piles. However, in order to reach a state with k piles, you first need to move k piles to merge the piles into a single group of k piles. The piles you move in this phase will have their cost repeated in the total cost. It is best to pick the k smallest piles, move each to any of the other k piles and the total cost will be: 0*(largest pile) + 1 * (k largest piles that are not the largest ever) + 2*(k smallest piles).

In fact, the maximum number of piles you can move in the second phase is k*k. To put it simply:

• The last phase involves verifying that the largest pile now contains all stones (Cost 0 * (size of largest pile) )
• The second-last phase involves moving k piles to the largest pile. The total cost is: 1*(total size of the n-1 piles).
• The third-last phase involves moving k*k piles. to other k piles. The cost is sum(of the n-1-k smallest stones).
• The fourth-last phase involves moving k*k*k piles. to other k*k piles. The cost is sum(of the n-1-k-k*k smallest piles).

And so and so, there is our algorithm. The largest pile will cost 0. The k next largest piles will each be added only once. The next k*k piles will each be added twice. The next k*k*k will each be added thrice and so and so...

You can calculate the cost in O(log_k(n)). Note that k can be 1, which turns it into O(n). The total complexity is O(q*log(n)) as long as you make sure not to calculate the case k=1 more than once.

int n, q; 
long a[100000]; 
long acum[100001]; 
long k[100000]; 
long res[100001]; 
 
long solve(long K) 
{ 
    long res = 0; 
    long N = n; 
    long p = 0; 
    long r = 1; 
    while (N > 0) { 
        long hi = N; 
        long lo = std::max(0LL, N - r); 
         
        // p times the sum of the stone piles between lo and hi.  
        res += p*(acum[hi] - acum[lo]); 
         
        N = lo; 
        if (r > N / K) { 
            //we don't want overflows here... 
            r = N; 
        } else { 
            r = r*K; 
        }        
        p++; 
    } 
    return res; 
} 
 
void solve() 
{ 
    memset(res, -1, sizeof(res)); 
    sort(a, a+n); 
    acum[0] = 0; 
    for (int i=0; i<n; i++) { 
        acum[i+1] = a[i] + acum[i];  
    } 
    long whenOne = solve(1); 
    // when k=1, solve(k) is linear in complexity, you do not want it 
    // to be executed many O(q) times... 
    for (int i=0; i<q; i++) { 
        if (i > 0) {  
            cout << " "; 
        } 
        cout << ( (k[i] == 1)? whenOne : solve(k[i]) ); 
    } 
    cout << endl; 
} 

I went to have lunch between figuring out the solution and implementing it. Slow to solve is today's theme.

Problem C : Aniversary

Link to statement

Did not really have much time to think of a solution for this. Google Gibonacci GCD and you will find out that there is a very interesting property about the GCD of Fibonacci numbers. In effect, since the GCD of Fibonacci numbers is equal to the X-th Fibonacci number such that X is the GCD of the indexes of the Fibonacci numbers (And also because the larger the index, the larger the Fibonacci number) then the problem becomes about finding the largest GCD of a k-subset of numbers between l and r, inclusive. Then use this largest GCD as an index for the Fibonacci function (if the value is large, you can use Matrix multiplication to find out this large Fibonacci number modulo m).

Could not solve the sub-problem.

Let us see how it goes.

Opinions, corrections, complaints, etc

Feel free to post comments.