Hello everybody, this time I just want to share the situation that I lived yesterday during the round 422. I like math problems, so I decided to start solving problem D(I solved the problem and got pretest passed with 1430 ~ 1450 ms(I don't remember exactly) since I submitted an nlogn solution). Well, at that moment, I was aware that the final verdict in the System Test could be TLE, however, my solution during the contest should take the same time for any input since I precomputed the value of the prefix sums and, right after that, the output can be found substracting and multiplying some variables.

Thus, I thought that if that solution had passed pretest, it must pass the SysTest as well(even when it was slow). Okay, after some time, the contest ended and the SysTest started. I was waiting for my submission for problem D and I noticed that, on the status page, my submission got TLE on test 1 and suddenly, it disappeared from the standings. As you can see, it seems that I never submitted any solution for D.

At that moment, I was a bit confused by the situtation and I sent messages to the author contest Melnik and to the coordinators of the contest. Well, after some time, the ratings were updated D: and I didn't receive any answer from them. After some more minutes, Melnik replied to my message. He explained that it was unexpected and he was really sorry about it(I understand that there are always some issues during any contest).

I decided to forget that situation yesterday. Today, with a better mood, I decided to submit exactly the same solution again(was it really TLE on test 1? Hahaha) and the result was this (The answer was: No, it seems it was not TLE on test1).

It turned out to be really sad because I would rank around 20 — 30(and I would have recovered my violet color) instead of ranking 420 :D and decrease my rating by 30. Moreover, according to the Editorial the first submission for D in Div2 was after 18 minutes while mine was in 17 minutes. Totally sad.

Okay, that was my sad story(maybe in some other contest I can still recover my violet color) and as Len pointed out, I was relying on my luck too much.

However, currently, I ask the same thing that sup_bro asked in the comments. Why does Codeforces run our code against pretest again? For instance, if they had run my solution against the first official test(those that don't belong to the pretest), this situtation wouldn't have occurred. I think that the answer to this question can be something technical that almost doesn't mind in competitive programming, but I would like to read some answer just to feel a bit better.

Hi guys, today a friend asked me about this problem. He said it was just a random problem that came to his mind. So, I don't know any OJ to submit it. Do you know any way to solve it efficienty? i.e. I know we can compute it using Java or Python, but I'm looknig for something better(Imagine you have 3s as time limit)

Hi guys, given that the tutorial didn't include any solution for problem F of that round, I decided to explain my solution because I'm sure the problem was really interesting.

First step

Let's denote f as the inverse map of p.

We can easily notice that the key is about looking at the prime factors of the numbers because the condition (i, j) = 1 iff (p_i, p_j) = 1 is equal to (i and j don't share any prime factor) iff (p_i and p_j don't share any prime factor). So, we will divide the numbers into some groups(which are not necessarily disjoint) such that any two numbers in the same group share a common prime factor. Then, let G_q be the group of all numbers between 1 and n which are divisible by q. In addition, we will keep a group G₁ = { 1 }, because as we know 1 is coprime with any number and it also doesn't have any prime factor.

Now, these groups are interesting because p_x and p_y will be in some group G_r for any numbers x and y in G_q (r depends on x and y, obviously). However, we could show that p(G_q) = G_r for any prime number q. The proof consists on noticing that if p_q belongs to some group G_r then (f(r) , q) is not 1(because r and p_q are in the same group) then f(r) belongs to G_q. Now, if y belongs to G_q then (y, x) is not 1 and then (p_y, r),so p_y belongs to G_r. Then, p(G_q) G_r. Analogously, we can prove that f(G_r) G_q and that completes the proof.(We used that q is prime, but this proof also works if q = 1).

So, we have proved that any q is mapped into some other r(where q and r are the indexes of the groups i.e. primes or 1). And this is basically all the solution because the next step will be about proving that if h is a bijective map which takes indexes into indexes of groups, then p_x = y is a feasible permutation , where all the prime factors of y are the images by h of the prime factors of x(here we are considering that the only factor of 1 is 1).

Second step

Claim: The only feasible permutations are those which satisfies p_x = y where all the prime factor of y are the images by h of the prime factors of x.

It is fairly easy to prove that if p satisfies the condition stated before, then p satisfies (i , j) = 1 iff (p_i, p_j) = 1

Now, we will prove that the condition is necessary. It is clear that h needs to be bijective(a group can only be mapped into one group).If q is any prime factor of x then h(q) is a prime factor of p_x(because of First Step). If r is any prime factor of y then the preimage of r is a prime factor of the preimage of p_x(This is also the first step, but considering the inverse of h instead of h). (Again, the proof remains true for the case q = 1).

Conclusion

In summary, we have proved that any bijective map h and any permutation satisfying Claim will turn out to be a feasible solution for p. So, the answer will be (#of feasible h)(# number of feasible p given h)

For one hand, number of feasible h is the number of ways to assign a prime r to any other prime q(here we will say 1 is "prime"), but those h are not only random bijective maps between primes, we should remember that the assignment satisfies that h(q) = r iff p(G_q) = G_r, so it is necessary that (number of elements of G_r) = (number of elements of G_q). Then, in the implementation, we will compute (number of elements of every group G_s) which is 1 if s = 1 and n/s if s is a prime greater than 1.(Think about it for a while if it's not clear at the beginning). Then, we should know how many groups have a fixed numbers of elements , say there are gr[t] groups which have t elements. Provided of this notation, the number of maps h will be .( Note that above we were considering the array p was empty, so if p has some entries already assigned, say p_x = y, then we should look at the prime factors of x (in increasing order) and the prime factors of y(in increasing order), here we observe that the i-th prime factor of x assigns(by h) the i-th prime factor of y. So, we observe that x and y should have the same number of prime factors, the number of elements of G_q should be equal to the number of elements of G_r(q and r are the i-th prime factors of x and y) and the assigment(by h) must be injective(then bijective because the sets are finite and have the same number of elementes), otherwise the answer = 0.(The primes must be ordered because if q is less or equal than then the only group with the same numbers of G_q is G_q, and if q is greater than then q is the last prime in the list of x and the groups with the same number of G_q are those G_r where r is a prime greater than , which is also the last one). Then, if ans is not 0, we should reduce gr[t] the number of times that a group with t elements is assigned to other group with t elements. Thus, the right answer for the number of maps h is ans1 =

For the other hand, once we have fixed a feasible h (i.e. assigns primes into primes with the same number of elements in their groups, Claim states that if x and z have the same prime factors, then p_x could be y or p_y could be y(there's no difference). So, we can divide numbers [1,n] into groups with the same factors(for example, {2,4,8} and {6,12,18,24} will be some groups). Again, let's denote by rep[t] the elements which have the same factors of t.(here we could store all the elements of a group in t were t is square-free i.e. the product of the common factors). The answer for the number of feasible permutations p is . (Here we don't have to deal with the verification in which some values of p are already assigned because we already did the verification before(assigment bettwen indexes) i.e. if x and y have the same prime factors, then p_x and p_y have the same prime factors(because of Claim) and we already know that p is bijective).Therefore, we just need to know how many numbers in a collection in which all share the same prime factors are already assigned and decrease rep[t] by one every time we find a number already assigned(p[x] != 0 where x and t have the same prime factors). Thus, in the general case the right answer will be ans2 equals to

Then, The final answer will be ans1 * ans2. It is clear (from the expression of the answer) that the complexity of the algorithm is O(n).

My implementaion ( I have to say that the names of my arrays are different from those that I described here, but I believe that you won't have any problem with these details).

Finally, I will describe Test case #17. Input: 5 0 2 0 4 0 Output: 6

So, here our groups G_i are {1}, {2,4}, {3}, {5}(we were lucky because the groups are disjoint). Then, gr[1] = 3, gr[2] = 1, rep[1] = 1, rep[2] = 2, rep[3] = 1, rep[5] = 1. Given that p[2] = 2, p[4] = 4, then ans1 = 3! * (1 — 1)! = 6, ans2 = 1! * (2 — 2)! * 1! * 1! = 1. Then, ans1 * ans2 = 6.

I hope you understand everything.Please, tell me, if you have any doubt about the solution(I tried to be a bit formal), comment and I will reply as soon as I can.