### Edvard's blog

By Edvard, history, 4 years ago, translation, , ### 691A - Fashion in Berland

The problem was suggested and prepared by Arthur Jaworski KingArthur.

In this problem you should simply check the conditions from the problem statement.

С++ solution

Complexity: O(n).

### 691B - s-palindrome

The problem was suggested by Nikita Melnikov nickmeller.

In this problem you should simply find the symmetric letters by picture and also observe that the pairs (b, d) and (p, q) is the symmteric reflections.

C++ solution

Complexity: O(n).

### 691C - Exponential notation

The problem was suggsted by user I_Had_A_Great_Time.

This is an implementation problem. You should do exactly what is written in the problem statement. On my mind the simplest way is to find the position of the first not zero digit and the position of the dot. The difference between that positions is the value of b (if the value is positive you should also decrease it by one).

C++ solution

Complexity: O(n).

### 691D - Swaps in Permutation

The problem was suggested by Zi Song Yeoh zscoder.

Consider a graph with n vertices whose edges is the pairs from the input. It's possible to swap any two values with the positions in some connected component in that graph. So we can sort the values from any component in decreasing order. Easy to see that after sorting the values of each component we will get the lexicographically maximal permutation.

C++ solution

Complexity: O(n + m).

### 691E - Xor-sequences

The problem was suggested by Zi Song Yeoh zscoder.

Let z ij be the number of xor-sequences of length i with the last element equal to a j. Let g ij be equal to one if contains the number of ones in binary presentation that is multiple of three. Otherwise let g ij be equal to zero. Consider a vectors z i = {z ij}, z i - 1 = {z i - 1, j} and a matrix G = {g ij}. Easy to see that z i = G × z i - 1. So z n = G n z 0. Let's use the associative property of matrix multiplication: at first let's calculate G n with binary matrix exponentiation and then multiply it to the vector z 0.

C++ solution

Complexity: O(n 3 logk).

### 691F - Couple Cover

The problem was suggested by Michael Kirsche mkirsche.

Let's count the number of pairs with multiple less than p. To get the number of not less pairs we should sumply subtract from n·(n - 1) the number of less pairs. Let cnt i be the number of values in a equal to i and z j be the number of pairs from a with the multiple equal to j. To calculate the values from z we can use something like Eratosthenes sieve: let's iterate over the first multiplier a and the multiple of it b = ka and increment z b by the value cnt a·cnt k. After calculating the array z we should calculate the array of its partial sums and find the number of less pairs in O(1) time.

C++ solution

Complexity: O(n + XlogX), where X is the maximal value in p. Tutorial of Educational Codeforces Round 14  Comments (7)
 » Can 691D - Swaps in Permutation be solved using merge sort ? If we allow swaps only if its one of valid swaps given in the input.
 » 4 years ago, # | ← Rev. 2 →   For problem D,Though not necessary , even has a larger complexity and even dsu can be used in a better way to lower complexity I always wanted to use some kind of heuristic in my code 19211367. Got WA in contest due to some minor major mistake( A mistake that is so minor but changes everything you are doing :P ).
 » In case someone faced the same issue. For problem E, my O(n3logk) solution in C# was getting TLE, so I parallelized matrix multiplication and got AC. 19309384
 » Apologies all for what is probably a silly question.The solution to 691D includes the line: const int N = 1200300; pti a[N];I can't find any documentation for a pti datatype. I assume this is an abbreviation commonly used in codeforces solutions? If so can someone link me to an explanation of what this is? Or a solution where the abbreviation is defined.
•  » » I had never seen this abbreviation before, but looking through Edvard's submissions, for example, 19489538 you can see it means pair .
 » I think that problem 691D - Swaps in Permutation have the same concept as problem 500B - New Year Permutation. I use dsu to solve both of these two problems. Anyway, D is still very good problems I think so. Thanks zscoder.
 » I think the complexity of problem D is wrong. did you mention the sorting complexity?