Hi guys!

So, if you have given the recent contest, you may have encountered Problem E which is a construction problem, well let's try a little different version of it.

You are given a positive integer n. Find a permutation that does not contain any bad indices or say it doesn't exist.

Now, the intuition here is first start with a base solution and slowly make it better and see if it solves the problem. Here, the base solution is the one mentioned in the editorial. Let's see how it looks:

[_, 2, 2, _, 2, 2, _, 2, 2, _, 3, 3, _, 3, 3, _, 3, 3, 2, 3, _, _]

Here, 2 and 3 represents the spf value of numbers present at those indices. _ represents remaining numbers.

The above is just one representation that shows two issues with this construction. The first one is putting the remaining 2 at the end of the sequence which makes for one bad index in below example_1:

[1, 2, 4, 5, 6, 8, 7, 10, 12, 11, 14, 16, 13, 18, 20, 17, 3, 9, 19, 15, 21, `22`, 23]

The solution is simply to put it with rest of the sequence of 2 such that it looks:

[_, 2, 2, _, 2, 2, _, 2, 2, 2, _, 3, 3, _, 3, 3, _, 3, 3, 3, _, _]

So, our example_1 will change to this:

[1, 2, 4, 5, 6, 8, 7, 10, 12, 11, 14, 16, 13, 18, 20, `22`, 17, 3, 9, 19, 15, 21, 23]

This is one of the solution having bad indices upper bound of 1 which is minimum you can get. But still not enough to solve the task above. The second issue is to resolve the remaining one bad index [22, 17, 3] which can be done by swapping the 22 with a number divisible by 3 that occur before it, like 18. So the sequence will look like:

[1, 2, 4, 5, 6, 8, 7, 10, 12, 11, 14, 16, 13, `22`, 20, `18`, 17, 3, 9, 19, 15, 21, 23]

Now, the above bad index issue is resolved so it should solve the problem, well not quite take a look at the below example_2:

[1, 2, 4, 5, 6, 8, 7, 10, 12, 11, 14, 16, 18, 13, 3, 9, 15, 17, 19]

In this the bad index is [15, 17, 19] and as you can see this example_2 does not have the example_1's bad index issue and it's a pattern I have seen but couldn't prove, also it repeats after every 12 values of n starting from 19. Also, when this pattern of bad index will occur there are two triplets like [14, 16, 18] and [3, 9, 15] will occur at the end of sequence 2 and 3 that looks:

[_, 2, 2, _, 2, 2, _, `2, 2, 2`, _, 3, 3, _, 3, 3, _, `3, 3, 3`, _, _]

We need to utilize these, the idea is to pick the last value from these triplet's and transform the sequence like this:

[1, 2, 4, 5, 6, 8, 7, 10, 12, 11, 14, 16, 13, 3, 9, 17, `15`, `18`, 19]

It resolved the example_2's bad index but introduce the example_1's bad index which can be resolved as mentioned above. So does it solves the problem for all values of n. Almost all except for these 3, 5, 7, 8. So does these values did not have an answer:

[1, 2, 4, 5, 6, 3, 7]

[1, 2, 4, 5, 8, 6, 3, 7]

Except for 3 and 5. Basically, brute force it to find them. And that solves it. Here's the Submission.