Codeforces Round #655 Editorial

Notice that since all elements must be positive, . The most simple construction of this problem is to simply make all elements equal to .

Short Solution: The two integers are and , where is the largest proper factor of .

Proof: Let the two integers be and . Assume WLOG that . Notice that this implies that .

We first claim that if , and we prove this as follows: if , then there exists some integer such that . The integer can then be written as , which is a multiple of . Thus, if .

We now show that if . We show this by using the fact that iff , so if , , and so . And since must be a multiple of both and , it follows that .

We have now established that to minimize , must be a factor of . And, since when is a factor of , we need to minimize , so we must maximize by choosing it to be the largest proper factor of (i. e. the largest factor of other than ).

We then simply need to find , the largest proper factor of . If is the smallest prime dividing , then , so it suffices to find the smallest prime factor of . We can do this by simply checking all values of such that . If is not prime, then it must have a prime factor not exceeding . Furthermore, if we do not find a factor of between and , then must be prime so we simply get and .

We're given that , so . , meaning that we will check less than numbers, which runs well under the time limit.

You need at most special exchanges to sort the permutation. Obviously, special exchanges are needed if the array is already sorted. Let's look into cases in which you need special exchange to sort the array.

Refer to i as a matching index if . If there are no matching indices, then you can just use one special exchange to sort the entire thing. Otherwise, you can use the location of matching indices to determine whether you need more than special exchange. If all matching indices are located in some prefix of the permutation, you can sort the permutation with one special exchange. The same is true for a suffix. In other words, if you can choose a subarray in the permutation such that all elements contained in the subarray are NOT matching and the elements outside of this subarray are matching, then one special exchange is needed to sort the array.

Otherwise, you need special exchanges to sort the permutation. Let's prove why you do not need more than special exchanges. You can quickly check that you need at most special exchanges for all permutations of length . For permutations of length , I claim that we can perform special exchanges on the whole array; to show this it suffices to construct a permutation that has no matching indices with either the given permutation or the identity permutation . We can do this as follows:

For simplicity, assume that is even. We will assign the numbers to the first positions of our permutation and the numbers to the last positions of . This ensures that has no matching indices with the identity permutation. Then, for all integers such that their position in (i. e. the such that ) is in the appropriate half of , assign ; assign other to arbitrary positions in the appropriate half of . Finally, cyclically rotate each half of – this ensures that has no matching indices with .

As an example, let's take . You can quickly check that this cannot be done in less than special exchanges. The construction of goes as follows:

First, we move all numbers to the proper half of , so that .

Observing that and , we set and then replace the remaining elements arbitrarily into the correct half, so we can get, for example, .

Finally, we cyclically rotate each half of , obtaining , which has no matching indexes with either or .

This can be extended to odd by first choosing some element other than and to be (this works for and we must have anyway in this case), and then running the same algorithm on the rest of .

First note that any possible circular value consists of the sum of some elements. Now let's think about how these values would look like in the circle.

Let's consider any one move on index . will be replaced with the sum of and (wrap around to index or if needed). Then let's consider making a move on , since it will be adjacent to after the first move. Then its value will become . This implies that alternating values play a role in the construction of the values contained in the final circular value.

Now let's consider the final move when there's elements left in the circle. This is the only move that takes the sum of two adjacent elements in the initial circle. With this observation, we can achieve our final construction as follows:

Choose any elements in the initial circle such that exactly one pair of chosen numbers are adjacent to each other. The answer will be the maximum of the circular value over all possible constructions.

While there are ways involving complicated prefix sums/segment trees, the cleanest implementation is as follows: create an array whose values consists of . Append this new array to itself to account for the circular structure. Now all you simply have to do is to find the maximum sum over all subarrays of length . This can be done with sliding window in time.

Let be the answer for the columns from to .

To solve , it is optimal to always fill some column within to to the max. Let's call this column . The transition is thus number of intervals that are fully within and and include . For every loop through all possible columns to be and take the max.

The answer is .

The efficiency is . There are dp states. For every state, you transition based on cases of , and it takes to determine how much the max column contributes.

Proof: Consider an optimal arrangement and the column with the most 1's in that arrangement. If there is an interval intersecting that column whose 1 isn't in that column, then moving the 1 to that column would not decrease (and possibly would increase) the quality of that arrangement. Thus, it's optimal for the column with the most 1s to have all the possible 1s that it can have.

For both solutions, we must first make the critical observation that because the array is sorted, all occurrences of a value occur as a single contiguous block.

Solution 1

We will define a recursive function which will use queries to determine the array. We will also store an auxiliary list of previously returned query values – not the queries themselves, but only the values returned, so that we know that if is in the list then some previous query revealed that there were instances of in some query, and that we haven't already determined exactly where in the array those instances of are.

The execution of will proceed as follows: first, query the interval , and let the result be .

If there exists some previous query result in our auxiliary list, then we will guarantee by details yet to be explained of that the interval that produced that result contained and that no part of those occurrences of occurred to the left of . This allows us to exactly determine the location of those occurrences of . We mark these occurrences in our answer, and then remove from our auxiliary list and do not add . If is not entirely composed of occurrences of , then the remaineder of the interval must be for some , and in that case we then call .

If there does not exist some previous query result in our auxiliary list, then we add to the list and do as follows: while the exact locations of those occurrences of have not been determined, call , where is the leftmost index in which has not yet been determined. Once those locations have been determined, call .

To determine the entire array we simply call . It is clear that this will correctly determine the array. We can see that it uses at most queries as follows: for each block of integers of the same value represented by a query result that we add to our auxiliary list, we use queries to determine the exact location of those integers: one when added to the list, and one when removing from the list.

This does not guarantee that the algorithm uses queries because some calls of can split a block of integers of the same value into two blocks. However, we can show that any blocks formed by splitting a single block into two cannot be further split as they occur either at the beginning or end of a queried interval (the full proof is left as an exercise to the reader), so each distinct value in the array will produce at most blocks, each of which will be determined in queries, meaning that the algorithm uses at most queries.

Side note: you can in fact further show that the algorithm always uses at most queries and that there exists an array for all which forces the algorithm to use queries.

Solution 2

Again, we will define a recursive function , but this time we will only additionally maintain the currently known values in the answer.

The execution of will proceed as follows: first, query the interval and let the result be . Then, find the largest integer such that and then for all in that are multiples of , determine the value located at index , either by querying or by using already known values.

By the definition of , there will be either one or two such indexes such that the values at those indexes are equal to .

If there is only one such index, let this index be . Make two queries and and let the results of these queries be and respectively. We can show that at least one of and must be equal to . If , then we see that the occurrences of must be precisely the interval . If , then we see that the occurrences of must be precisely the interval .

If there are two such indexes, let these indexes be and so that . Note that it must be true that . Make a single query and let the result be . We can show that must be equal to , so we can then conclude that the occurrences fo must be precisely the interval .

After the interval containing the occurrences of has been determined, mark these occurrences in our answer and then call on the remaining not-fully-determined interval to the left if it exists and the remaining not-fully-determined interval to the right if it exists.

To determine the entire array we simply call . It is clear that this will correctly determine the array. We can see that it uses at most queries as follows: Each call to finds all occurrences of a distinct value . We will refer to the queries of single indexes that were multiples of some as -queries. For each , we perform the following queries other than -queries: the first query in , and then either two additional queries if only one -query was found to equal , or a single additional query if two -queries were found to equal . This means that if we group each -query with the value that it equaled, then we will have performed exactly queries for each , and so the algorithm must therefore use exactly queries.