Good Bye 2018 — Editorial

Consider some solution , , , where and . Let's add two yellow ornaments and one blue both to the solution and to the reserve, then we have . We can see that this new problem is equivalent to the old one. In this problem, the best solution is achieved when we use ornaments of each colour. Hence, we can find the said minimum, multiply by three and then remove the three extra ornaments again.

We know that there exists some permutation such that for all the following holds:

Summing this for all we get:

We can thus sum all , respectively , coordinates of both obelisks and clues, and divide by . This takes time.

Alternative solution: Take the lexicographically smallest obelisk coordinate. It is clear that this needs to be paired with the lexicographically largest clue. We simply find minimum and maximum in and sum.

Subtract from all values for convenience. Fix the value of . We get values of for all from until we reach again. This value can be also written as . Due to Bezout's theorem, the equation has an integer solution for and if and only if is divisible by .

Furthermore, all possible values of will be visited before it returns to . This is because the element generates the group .

We can thus consider only values of that divide . We can find all of them by trial division in . For each of them, we can find a closed form solution by summing arithmetic series.

There are two types of subarrays with length :

• They are fully formed from one permutations.
• They are a concatenation of a long suffix of one permutation, and a long prefix of the next permutation.

There are such subarrays of the first type, and they all have the the correct sum.

Let's investigate the second type. Recall the algorithm of finding the next permutation in lexicographical order. We find the longest suffix that is in decreasing order, let its length be . We swap the preceding element with the smallest one from the decreasing sequence larger than , and sort the suffix in increasing order. The prefix of length is left unchanged, but all longer proper prefixes are different and also change their sum.

Coming back to our problem, if the suffix of length is in decreasing order, than the prefix of length of the next permutation has different sum from the prefix of the same length of the current permutation, hence the subarray has incorrect sum. Conversely, if the suffix of length is not in decreasing order, then the prefix of length of the next permutation equals to the prefix of the current permutation, and its sum is .

To find the answer, we must thus subtract the number of suffixes of all permutations that are decreasing. How many of them are there for a fixed ? This is simple – we choose the first elements freely, and permute them. The rest has to be sorted in a particular way. Hence the number of bad subarrays coming from a suffix of length equals .

Convince yourself that this approach works correctly even for the last permutation, where there is no next permutation to concatenate its suffixes with.

The answer is:

This can be calculated in without the need of modular division.

There is also a simple recurrence counting the same answer, found by arsijo:

The first observation is that using the Handshaking lemma, we know the parity of .

Secondly, on the integers of same parity, the answer always forms a continuous interval, that is if is one possible answer and is another with , then every satisfying is also an answer. We should thus look into some binary search approaches.

We use the Erdos-Gallai theorem linked in the statement to determine whether a sequence is graphic. If it is not the case, we must determine whether the answer is too big or too small. This depends on whether the is on the left or the right side of the inequality when it is not satisfied. If it is on the left, it means that it is too big – clearly making it larger is never going to change the sign of the inequality. On the contrary, if is on the right, it is clearly too small.

It can also happen that the inequality is false for some where is on the left and for some other it is on the right. Then there clearly is no solution.

Checking the inequality naively takes time, but we can also do it in : for left side we need a prefix sum, and for right side we maintain the sum and also how many times a particular value occurs. The sum of values at most can then be maintained in . This yields an algorithm in .

Alternatively, we can perform a similar binary search using Havel-Hakimi algorithm, using a segment tree or a multiset and tracking whether the was already processed or not to find out whether the answer is too small or too big. This yields algorithm.

We start with a greedy solution. This means that we fly over lava, swim on water and walk on grass, keeping track of time and the stamina. There are two types of issues that may happen – either we don't have enough stamina to fly over lava, or we have some leftover stamina at the end.

If we lack some stamina, we can walk or swim "in place" for some amount of time to gain it. This "in place" movement can be perform by simply walking or swimming half a meter backwards and then half a meter forwards. This gains stamina. It is more effective to do on water, as we move faster there, so we may as well do it on the first water on the journey. If there was no water before the lava we are flying across, we use slightly more expensive ground.

On the other hand, if we have some unused stamina in the end, we should convert some previous movement to flying to save time. Note that converting meter of movement costs us stamina, not one, since we consume stamina and also gain stamina less. Since moving on grass is slower, we prefer to convert such movements. However, we must take care not to convert a walking segment that is too early – we should not modify the journey in such a way that we run out of stamina at some point. We thus keep track of the length of grass that we travelled across during our journey. Consider the end of some patch of terrain. Let the total length of grass that we've travelled through until now be , and let the current stamina be . We may never convert more than grass, and also no more than since if not, we would have run out of stamina at the current location. We simply lower the amount of grass that is available to be converted, to . In the end, we convert walking to flying, and swimming to flying to save some time.

This works in .

Most of the operations we're given are useless, as we can perform them on our own. However, we cannot perform the square root ourselves, so we should be able to use the information given us by the square root oracle to find the factorisation.

First let's solve the task for a product of two primes.

Select uniformly at random and assign . Let be the answer to the query sqrt z. We have For a fixed , thanks to Chinese remainder theorem there are four solutions to this equation for , two of them being and . If that is not the case, then as and are coprime, then divides one of the factors while divides the other. Hence, one factor can be computed as . Since we selected at random, the probability that the interactor returns or is exactly and queries are needed in expectation.

Let's take a look what happens when there are more than two prime factors. Some of them will be accumulated in , and the others in . Collect all these values (again, after taking gcd of them with ) over multiple queries. We can find the prime factor if and only if for we have seen a value such that . This is because we can take gcd of exactly all values containing as a factor and to get .

We do not know which values contain the prime factor before we know the prime factor, but we simply calculate gcd of all subsets of retrieved values. Since gcd is a commutative and associative operation, and all values we get this way must be factors of , we can perform this step in time, where is the number of prime factors of . We can then a primality checking algorithm to check which of these are primes. Alternatively, we can just greedily pick the smallest of all values (except ) that is coprime to all the values that have been selected so far – this will always be a prime.

It remains to show what is the probability of success. We need each pair of primes to be separated at least once. The probability of that happening in one query is . Over the course of queries, we have probability that we are still unable to separate the two primes. Taking union bound over all prime pairs yields an upper bound on the error probability .

Implementation note: To find the square root, we use Chinese remainder theorem and find the square roots in the respective finite fields. The primes are of form for a simple reason – we can find the square root of modulo by simply calculating . For primes of form , we need Tonelli-Shanks, which empirically uses about modular exponentiations. With the number of queries and prime factors, and the size of the numbers, it was suddenly impossible for the interactor to fit into the time limit.

If you represent the row state as a pair where is the distance between blue and white token and is the distance between white and red, we can see that each player has one operation that reduces by , and a second operation which reduces by . In other words, each and defines a symmetric game, and all games are independent. This is an impartial game after all!

Once we have the Grundy numbers for each pile, we can use Sprague-Grundy theorem to find the answer. How to find the Grundy numbers? We find the set of primes and semiprime by sieving. To find the value of pile of size , we can collect the Grundy numbers of each pile size reachable from (i.e. where p is a prime or semiprime), and then find the mex. This takes , where is the maximum distance between two tokens () and is too slow.

To improve upon this, we can use bitset, but that's not enough. We actually need more of these! Maintain bitsets , ..., where -th bitset contains true at -th position when there is a transition from state to state with grundy number .

How do you do that? You have one bitset storing all primes and semiprimes. For each , preform linear search for the mex, let the grundy number be . Then or with .

This works in . The maximum Grundy number given the input constraints is less than 100, so we can safely pick .