DMOPC '15 November Solutions


P1 - Grumpy Dwarf

by FatalEagle

Despite the fact that it's only the first problem, a lot of people overthought it. The intended solution is simple simulation. Keep track of the number of metal bars as well as swords we've made. Once we run out of bars, output the number of swords we've made.

bars = input()
K = input()
swords = 0
total = 0
while bars > 0:
    bars -= 1
    swords += 1
    total += 1
    if swords == K:
        bars += 1
        swords = 0
print total

Time Complexity: \mathcal{O}(N)


P2 - Admin War

by cheesecake

Simple implementation problem. Store card values in arrays, then iterate through both while keeping track of the score. Output the score and outcome as required.

#include <bits/stdc++.h>
using namespace std;

int N, X[201], F[201], x, f;;
int main()
{
    scanf("%d",&N);
    for (int i = 0; i < N; ++i)
        scanf("%d",&X[i]);
    for (int i = 0; i < N; ++i)
        scanf("%d",&F[i]);
    for (int i = 0; i < N; ++i)
    {
        if (X[i] > F[i])
            x++;
        else if (F[i] > X[i])
            f++;
    }
    printf("%d %d\n",x,f);
    if (x > f)
        printf("Xyene\n");
    else if (f > x)
        printf("FatalEagle\n");
    else
        printf("Tie\n");
    return 0;
}

Time Complexity: \mathcal{O}(N)


P3 - Origami

by cheesecake

Every cut we make, let's greedily cut the maximum amount of paper we can. Until we have more pieces of paper than K, we will always double the amount that we currently have with each cut. Once we have more than K, we can only obtain K pieces more with each cut, so we can use division to find the remaining cuts needed.

#include <bits/stdc++.h>
using namespace std;

long long N, K;
int main()
{
    scanf("%lld%lld",&N,&K);
    long long ans = 0;
    long long piece = 1;
    while (piece < K && piece < N)
    {
        piece += piece;
        ans++;
    }
    ans += (N-piece+K-1)/K;
    printf("%lld",ans);
    return 0;
}

Time Complexity: \mathcal{O}(log(min(N,K)))


P4 - Personal Assistant

by cheesecake

This is a variation of the classical knapsack problem.

For subtasks 1 and 2, let dp[i] represent the maximum possible happiness value we can obtain if we only consider the i-th minute and onward. Iterate backwards through the array, for each minute with an anime, we can either skip it or watch it. If anime j is released on the i-th minute, we have the transition formula dp[i] = max(dp[i+1], H[j] + dp[i+L[j]]).

For subtask 3, we need to realize that only the minutes with animes matter. The happiness value we can obtain from watching an anime can be found by greedily binary searching for the next anime we can watch if we watch this one. Implementation is left to the reader as an exercise.

Time Complexity: \mathcal{O}(NlogN)


P5 - Sysadmin

by Xyene, WallE256

The intended solution is the Convex Hull Trick. Implementation is left as an exercise.

Time Complexity: \mathcal{O}((N+Q)logN)


P6 - Manhattan Magnets

by k_53P

For each piece of metal, find the distance to the closest magnet. In order to pick this piece of metal up, the new magnet must be placed within a certain zone where every square’s Manhattan distance is closer than the Manhattan distance to the closest magnet.

If you tilt the coordinate plane 45 degrees, this zone looks like a square. If you then draw a checkerboard on the coordinate plane, and look only at the white tiles, it is a square. If you look only at the black tiles, it is also a square.

The intended solution is to do a 2-D line sweep after separating the coordinate plane into two planes, black and white. Out of both planes, the tile which is in the most “zones” is the tile which will pick up the most metal.

Time Complexity: \mathcal{O}(NM+4000^2)

Comments

There are no comments at the moment.