October 28, 2022 Single Round Match 840 Editorials

RepeatedHalving

The simplest efficient solution to this problem simply simulates the process described in the problem statement, with one additional smart step: if all bags are empty, we can stop the simulation early.

Below we give a proof why this solution is efficient.

Whenever we select a bag, we halve the number of marbles it contains. As we are rounding the number of removed marbles up, the number of remaining marbles is rounded down.

This tells us that a bag will become empty very quickly: if we start with at most 2^N marbles in a bag and select the bag N+1 times during the process, after the last time the bag is guaranteed to be empty. For the largest possible starting bag (10^9 marbles, which is slightly less than 2^30) this gives us a mere 31 iterations.

Thus, regardless of what N bags we start with, after at most 31*N <= 3100 steps all bags will be empty. Thus, the solution described above will simulate at most that many steps, which is clearly efficient (for any reasonable implementation of the simulation of a single step).

public int[] simulate(int[] bags, int steps) {
    int N = bags.length;
    
    int[] state = new int[N];
    for (int n=0; n<N; ++n) state[n] = bags[n];

    while (steps-- > 0) {
        // find the largest bag in a dumb but easy way
        Arrays.sort(state);

        // check whether we have all zeros
        if (state[N-1] == 0) break;

        // remove one half of marbles from the biggest bag
        state[N-1] /= 2;
    }

    Arrays.sort(state);
    return state;
}

An alternate solution can do this distinction at the beginning. If the number of steps to simulate is 3100 or more, we can immediately return an array of all zeros. If not, the number of steps is so small that we can afford to simulate them one at a time.

BarongAndRangda

A good approach towards solving problems like this one is to find ways to reduce the number of possible cases as much as possible, and to simplify the analysis of the remaining ones as much as possible.

Here, we can start by arguing as follows:

• As long as both teams contain a Barong, their strength difference does not change if we remove one Barong from each team.
• Similarly, as long as both teams contain a Rangda, we can remove one Rangda from each team.
• After we do that, we are now left in the situation where at least two of the four given numbers are zeros. Even more precisely, there is at most one non-empty group of Barongs and at most one such group of Rangdas.

Now we can proceed for example by looking at the cases where there are exactly two such groups:

• If B1 > 0 and R1 > 0, the first team is clearly stronger.
• If B2 > 0 and R2 > 0, the second team is clearly stronger.
• If B1 > 0 and R2 > 0, we have Barongs on team 1 versus Rangdas on team 2.
  If B1 >= R2, Barongs win. In the opposite case the answer is “unknown”: more Rangdas may or may not be more powerful than fewer Barongs.
• Finally, if R1 > 0 and B2 > 0, we have the opposite of the previous case. If B2 >= R1, Barongs win (and thus team 2 wins), in the opposite case team 1 may or may not win depending on the ratio between the strengths of a Barong and a Rangda.

Once we dealt with these cases, all that remains are cases in which at most one group is non-empty. If there is one such group, the math is easy: the non-empty team wins. If there is no such group, we get the case covered by the examples: both teams are equally strong, and thus the statement “team 1 is stronger” is incorrect.

public String compare(int B1, int R1, int B2, int R2) {
    while (B1 > 0 && B2 > 0) { --B1; --B2; }
    while (R1 > 0 && R2 > 0) { --R1; --R2; }

    // maybe two of the piles are still non-zero
    // in that case, it must be one of Barongs and one of Rangdas
    if (B1 > 0 && R1 > 0) return "correct";
    if (B2 > 0 && R2 > 0) return "incorrect";
    if (B1 > 0 && R2 > 0) {
        if (B1 >= R2) return "correct"; else return "unknown";
    }
    if (R1 > 0 && B2 > 0) {
        if (R1 <= B2) return "incorrect"; else return "unknown";
    }

    // if we got here, at most one of the piles is non-zero
    // maybe it's exactly one
    if (B1 > 0 || R1 > 0) return "correct";
    if (B2 > 0 || R2 > 0) return "incorrect";

    // if we got here, everything is zero
    return "incorrect";
}

An alternate approach to solving this problem is by simply testing two corner cases. In general, the winner of a duel may depend on the ratio r/b between the strengths of a single Barong and a single Rangda. For example, if we have a team of 3 Barongs vs. a team of 5 Rangdas, the ratio r/b = 5/3 leads to a tie, bigger ratios mean that Barongs win and smaller ratios mean that Rangdas win.
It is enough to test two ratios: one that is very large and one that is very small, more precisely, very close to 1. If the maximum number of entities of a single type in the input is M, we can for example test the ratios r/b = (M+7)/1 and r/b = (M+7)/(M+6). Note that the second ratio is closer to 1 than any valid ratio between the numbers of Barongs on one team and Rangdas on the other team can be. If team 1 wins for both ratios, it is guaranteed to win. Else, if it wins for one of them, the result is unknown. Else, team 1 cannot win and the statement is incorrect.

public String compareByMath(int B1, int R1, int B2, int R2) {
    long M = 7 + Math.max( Math.max(B1,R1), Math.max(B2,R2) );
    boolean winIfFar = (M * B1 + R1 > M * B2 + R2);
    boolean winIfClose = (M * B1 + (M-1) * R1 > M * B2 + (M-1) * R2);
    if (winIfFar && winIfClose) return "correct";
    if ((!winIfFar) && (!winIfClose)) return "incorrect";
    return "unknown";
}

Postcards

Before year 0, postcards would only be delivered within each city. Within city x there are x people sending postcards, each of them to each of the other (x-1) citizens, for a total of x*(x-1) = x^2 – x postcards sent.

We can calculate the total number of postcards sent in this scenario in constant time, for example, by using the formulas that the sum of the first N integers is N(N+1)/2 and that the sum of the first N squares is N(N+1)(2N+1)/6.

Once we start adding roads, we will be connecting some components together. Each time we actually do connect two components that currently contain X and Y people, there will be 2*X*Y new postcards that can reach their destinations.

Thus, all we have to implement is a disjoint set union algorithm. Both the standard Union-Find and the technique where you always merge the smaller component into the larger one should be efficient enough to pass comfortably. The range of N makes the implementation slightly more complicated, but we can easily handle that, for example, by explicitly doing coordinate compression: if there are Y years, there are at most 2*Y cities that get a road, and when merging the components of the underlying graph we only care about those 2*Y <= 300,000 nodes.

long MOD, state;
int[] boss;
long[] componentSize;

long gcd(long x, long y) {
    if (y == 0) return x;
    return gcd(y, x%y);
}

long getFraction(long[] numerator, long denominator) {
    // returns (product(numerator) / denominator) modulo MOD
    for (int i=0; i<numerator.length; ++i) {
        long d = gcd( numerator[i], denominator );
        numerator[i] /= d;
        denominator /= d;
    }
    long answer = 1;
    for (long x : numerator) answer = (answer * x) % MOD;
    return answer;
}

long sumNumbers(long N) {
    // returns (1 + 2 + ... + N) modulo MOD
    return getFraction( new long[] {N, N+1}, 2 );
}

long sumSquares(long N) {
    // returns (1^2 + 2^2 + ... + N^2) modulo MOD
    return getFraction( new long[] {N, N+1, 2*N+1}, 6 );
}

int topboss(int x) {
    if (x == boss[x]) return x;
    return boss[x] = topboss(boss[x]);
}

long union(int x, int y) {
    int tx = topboss(x), ty = topboss(y);
    if (tx == ty) return 0;
    
    // when doing the union flip a pseudorandom coin for the new root
    state = (state * 1103515245 + 12345) % (1L << 31);
    if (((state >> 13) & 1) == 1) { int z=tx; tx=ty; ty=z; }

    long added = (2 * componentSize[tx] * componentSize[ty]) % MOD;
    componentSize[tx] += componentSize[ty];
    if (componentSize[tx] >= MOD) componentSize[tx] -= MOD;
    boss[ty] = tx;
    return added;
}

public int count(int N, int Y, int seed) {
    
    MOD = 1_000_000_007;
    
    int[] A = new int[Y];
    int[] B = new int[Y];
    state = seed;
    for (int y=0; y<Y; ++y) {
        state = (state * 1103515245 + 12345) % (1L << 31);
        A[y] = (int)(state % N);
        state = (state * 1103515245 + 12345) % (1L << 31);
        B[y] = (int)(state % N);
        if (Y < 50) System.out.println(A[y] + " " + B[y]);
    }

    long answer = 0;

    // calculate the initial number of postcards:
    // sum n*(n-1) for n = 1 to N
    long pairs = (sumSquares(N) - sumNumbers(N) + MOD) % MOD;

    // coordinate compression: collect the edge endpoints
    TreeSet<Integer> used = new TreeSet<Integer>();
    for (int y=0; y<Y; ++y) {
        used.add( A[y] );
        used.add( B[y] );
    }
    
    int Z = used.size();
    int[] cityList = new int[Z];
    {
        int t = 0;
        for (int x : used) cityList[t++] = x;
    }

    // initialize the Union-Find, including component sizes
    componentSize = new long[Z];
    for (int z=0; z<Z; ++z) componentSize[z] = cityList[z]+1;
    boss = new int[Z];
    for (int z=0; z<Z; ++z) boss[z] = z;

    // do the Union-Find
    for (int y=0; y<Y; ++y) {
        A[y] = Arrays.binarySearch( cityList, A[y] );
        B[y] = Arrays.binarySearch( cityList, B[y] );
        pairs += union( A[y], B[y] );
        if (pairs >= MOD) pairs -= MOD;
        answer += pairs;
        if (answer >= MOD) answer -= MOD;
    }

    return (int)answer;
}

AlternatingPermutations

Clearly, an equivalent way of stating the definition of these permutations is that their values alternately go up and down.

Let D[n,x] denote the number of permutations of order n that start with x and the first step (if any) goes down.

Let U[n,x] denote the same thing for permutations that start by going up.

These two arrays of counts are symmetric: If we take a permutation that is counted by D[n,x] and we swap each element y with n-1-y, we get a valid alternating permutation of order n that starts with n-1-x and goes up. This is clearly a bijection, hence U[n,n-1-x] = D[n,x]. This means that once we compute the values D, by symmetry we automatically know the values U.

We will now show how to compute all the values D[1,0] to D[N,*] in O(N^2) time. The start is easy: D[1,0] = 1 as the only such permutation is {0}.

It would be easy to compute the D values in O(N^3) time by counting them as follows: when computing D[n,x], the next value after x must be some y < x. Let’s fix one such y. We now have a permutation that starts {x, y}. The next step of this permutation will be up. We will now show a bijection between all these permutations and all permutations of order n-1 that start with y and go up first. The bijection is pretty simple: Remove the x from the start. We now have an array of order n-1 but there is a gap in the values used: the x we just removed is missing. To get rid of the gap, simply decrement all elements that are greater than x by 1. (This does not change their relative order, so the result is always a valid alternating permutation.) We leave it as an exercise to verify that this is indeed a bijection.

Thus, we have just shown that D[n,x] is the sum of U[n-1,y] over all y < x.

As we already stated above, the above observation would easily allow us to compute the entire array D in O(N^3) time: for each pair (n,x) we would iterate over all y.

But we can be smarter than that. To speed up the calculation we just need to notice that we are computing the same sum over and over again. For example, D[n,3] = U[n-1,0] + U[n-1,1] + U[n-1,2] and then D[n,4] = U[n-1,0] + U[n-1,1] + U[n-1,2] + U[n-1,3]. This allows us to rewrite the formula as follows: D[n,0] = 0 and then D[n,x] = D[n,x-1] + U[n-1,x-1] for all x > 0.

This new recurrence relation can now easily be evaluated in O(N^2) time.

What remains is dealing with the prefix. We do that as follows:

• First, we verify that the prefix is a valid prefix of an alternating permutation: there can be no duplicate value, and (if there are at least three elements in the prefix) the values themselves have to alternate.
• Next, we handle the special case N = 1. It is really easy to get this case wrong and count the only alternating sequence {0} twice: once as “starts with 0 and first goes up” and once as “starts with 0 and first goes down”
• Now, we are left with the general case. What we do depends on what the prefix looks like:
  • If the prefix is empty, we return the sum of all D[N,x] and all U[N,x]: we may start anywhere and in either direction.
  • If the prefix has a single value x, we return D[N,x] + U[n,x]: we must start at x but we still get to choose the direction.
  • If the prefix has L > 1 values, we look at its last value x and we check the previous value to know whether the next step goes up or down. Now we need to count all ways to finish this prefix. We will do this by doing the same trick we already used once when we removed the first element. Imagine that we already finished the full permutation. Now we remove the first L-1 elements and we decrement the remaining ones to close the gaps. (Equivalently, we renumber the remaining ones from 0 to N-L while maintaining their relative order.) What we get is a valid alternating permutation of order N-L+1 that starts by going in the correct direction. Moreover, we know what the first element now is: its value is clearly always y = (x minus (the number of elements smaller than x we removed)). Thus, there are exactly ?[N-L+1,y] ways to finish this prefix, where ? is either U or D depending on what is the correct first direction.

public int count(int N, int[] prefix) {

    // check whether the prefix is valid
    int L = prefix.length;
    for (int i=0; i<L; ++i) for (int j=i+1; j<L; ++j)
        if (prefix[i] == prefix[j]) return 0;
    for (int i=0; i+2<L; ++i) { 
        int d1 = prefix[i+1] - prefix[i], d2 = prefix[i+2] - prefix[i+1];
        if (d1 * d2 >= 0) return 0;
    }
    
    long MOD = 1_000_000_007;

    // determine the length of the tail
    if (L > 0) N = N+1-L;

    // do the DP to ompute D[N,*] in the array count[]
    long[] count = new long[N];
    long[] oldCount = new long[N];
    count[0] = 1;
    for (int d=2; d<=N; ++d) {
        for (int n=0; n<d-1; ++n) oldCount[n] = count[n];
        for (int n=0; n<d; ++n) {
            if (n == 0) {
                count[n] = 0;
                continue;
            }
            count[n] = count[n-1] + oldCount[d-2-(n-1)];
            if (count[n] >= MOD) count[n] -= MOD;
        }
    }

    // do the casework to determine the final answer 
    if (L == 0) {
        if (N == 1) return 1;
        long answer = 0;
        for (long x : count) answer += x;
        answer *= 2;
        return (int)(answer % MOD);
    }
    if (L == 1) {
        if (N == 1) return 1;
        long answer = count[prefix[0]] + count[N-1-prefix[0]];
        return (int)(answer % MOD);
    }
    int start = prefix[L-1];
    for (int i=0; i<L-1; ++i) if (prefix[i] < prefix[L-1]) --start;
    if (prefix[L-2] < prefix[L-1]) return (int)count[start];
    return (int)count[N-1-start];
}

MaximizeValue

If the knight chooses some S that has a common divisor D > 1 with N, the maximum number of coins collected will be 1. This is because, just like in one of the examples, once the knight leaves room 1 to go to room S, the knight’s room number will always be divisible by D and thus the knight will never be able to leave the castle. The values S=0 and S=1 lead to the same result for slightly different reasons.

Thus, the first good step is to only look at values S > 1 that are coprime to N. For these, the knight is guaranteed to return to room 1 eventually, and thus collect at least 1+S coins.

For any N, the values coprime to N and the operation of multiplication modulo N form a multiplicative group. (In slightly more human words, the operation is associative and there are inverse elements: we can “divide” within the group.) 

The value N in this problem was chosen in a very particular way: for all these N the above multiplicative group is cyclic and thus it has some generators: there are some numbers G such that each element of the group is equal to some power of G. These values are, in this context, also known as primitive roots modulo n.

We don’t know any deterministic way to find them that would be guaranteed to run quickly, but we know that there’s a lot of them and we know a simple and fast way to verify whether some number is a generator. This gives us a quick randomized algorithm to find one: simply generate random elements of the group and test them until you hit one that works.

Our multiplicative group has varphi(n) elements, where varphi(n) is Euler’s totient function that gives the number of positive integers less than n and coprime to n. The value G is a generator if and only if G^varphi(n) is the smallest positive power of G that equals 1. To test this efficiently, we can find all prime divisors of varphi(n) and for each such divisor q we can calculate G^(varphi(n)/q) using fast exponentiation. If any of these values is 1, G is not a generator, if all of them differ from 1, it can be shown that G is a generator.

Additionally, there are some simple relationships between generators for N=p and generators for N=2p^k. We give these without a proof. Using them is not necessary but it makes it easier to argue about the time complexity of the algorithm.

• For a prime N the expected number of attempts to hit a generator is O(log log N).
• If we find a G that is a generator modulo a prime P, there are two cases: either it’s also a generator modulo any P^x, or already G^(P-1) = 1 modulo P^2. In the second case, G+P is a generator modulo all P^x.
• If G is a generator modulo P^K then either G or G+P^K is a generator modulo 2P^K. The correct one is the odd one.

When using the above sequence of steps, we will first spend O(sqrt(varphi(n))) steps once to find its O(log n) distinct prime factors, and then we do an expected O(log log n) attempts to find a generator. In each of them we perform O(log n) fast exponentiations, each of them to a power not exceeding n.

// extra helper functions to do arithmetic in 64-bit ints without overflow
long safemul(long a, long b, long n) {
    long res=0;
    for (int pw=0; pw<62; pw++) {
        if ((b & 1L << pw) != 0) res = (res + a) % n;
        a = (2*a) % n;
    }
    return res;
}

long safemodexp(long a, long b, long n) {
    long res = 1;
    for (int pw=0; pw<62; pw++) {
        if ((b & 1L << pw) != 0) res = safemul(res,a,n);
        a = safemul(a,a,n);
    }
    return res;
}

long[] primeFactors(long N) {
    ArrayList<Long> answer = new ArrayList<Long>();
    for (long d=2; d*d<=N; ++d) {
        if (N % d == 0) {
            answer.add(d);
            while (N % d == 0) N /= d;
        }
    }
    if (N > 1) answer.add(N);
    long[] finalAnswer = new long[ answer.size() ];
    for (int i=0; i<answer.size(); ++i) finalAnswer[i] = answer.get(i);
    return finalAnswer;
}

long findPrimeGenerator(long P) {
    long[] primes = primeFactors(P-1);
    Random rnd = new Random();
    while (true) {
        long G = rnd.nextLong() % (P-2);
        if (G < 0) G += P-2;
        G += 2;
        boolean allOK = true;
        for (long q : primes) {
            if (safemodexp(G, (P-1)/q, P) == 1) {
                allOK = false;
                break;
            }
        }
        if (allOK) return G;
    }
}

public long solve(long P, int K) {
    long G = findPrimeGenerator(P);
    if (K > 1) {
        if (safemodexp(G, P-1, P*P) == 1) G += P;
    }
    if (G % 2 == 0) {
        long P_to_K = 1;
        for (int k=0; k<K; ++k) P_to_K *= P;
        G += P_to_K;
        G %= 2*P_to_K;
    }
    return G;
}