thematdev's blog

By thematdev, 2 years ago, In English

This blog is inspired by problem 1591D - Yet Another Sorting Problem, hope you will enjoy it.

Basic concepts

First of all, let's define some basic things, you can skip it if you know it.

Parity of permutation $$$p$$$ is parity of number of inversions in it. Inversion is pair $$$(i, j)$$$ such that $$$i < j, p_i > p_j$$$.

Composition of permutations defined as follows $$$(f \circ g)_x = f_{g_x}$$$, we first apply $$$g$$$, then $$$f$$$.

Cycle is a permutation, where some indices are cyclic shifted, for example $$$p = \begin{pmatrix}1 & 5 & 2 & 4 & 3\end{pmatrix}$$$ is a cycle $$$\begin{pmatrix}2 & 3 & 5\end{pmatrix}$$$.

Theorem. Every permutation is composition of non-intersecting cycles.

Proof. Consider directed graph where vertices are numbers from $$$1$$$ to $$$n$$$, and edges are $$$i \to p_i$$$ for all $$$i$$$. Since $$$p$$$ is permutation, indegree and outdegree of each vertex is 1, hence our graph is collection of cycles, that's what we want.

Lemma. Applying swap to permutation will change its parity.

This lemma is very important, so it is left to reader as an exercise.

Fact. Parity of $$$(f \circ g)$$$ is sum of parities of $$$f$$$ and $$$g$$$.

Proof. Applying swap to permutation change its parity, thus if permutation $$$f$$$ can be represented as $$$k$$$ swaps, then parity of $$$k$$$ is parity of $$$f$$$. So if $$$f$$$ can be represented as $$$k$$$ swaps, and $$$g$$$ can be represented as $$$m$$$ swaps, then $$$f \circ g$$$ can be represented as $$$k + m$$$ swaps, but parity of $$$f \circ g$$$ is parity of $$$k + m$$$, which is sum of parities of $$$f$$$ and $$$g$$$, QED.

Counting inversions, parity of permutation

There are many ways to count number of inversions in $$$O(n \log n)$$$ time.

But there is a simple way to count parity of permutation, without directly counting number of inversions.

Theorem. Permutation can be represented as composition of 3-cycles if and only if it is even.

Proof. 3-cycle is even, so composition of 3-cycles must be even, so all that we need to do is proof, that for any even permutation exists such representation.

We will try to build our permutation from identical applying 3-cycles. On $$$i$$$-th iteration we assume, that first $$$i - 1$$$ elements of permutation are in place, and we will try to place $$$i$$$-th element. If $$$i$$$-th element is not in place, then now in current permutation it is on $$$j$$$-th place, $$$j > i$$$. Let's do cycle $$$n \to j \to i$$$, if $$$j \neq n$$$, and if $$$j = n$$$, do $$$n - 1 \to j \to i$$$, so we won't corrupt first $$$i - 1$$$ elements, and we will place $$$i$$$-th element.

So we can do $$$n - 2$$$ steps. After that there are two possible situations.

  1. $$$n - 1$$$-th and $$$n$$$-th elements are in place, this means that we represented our permutation as 3-cycles, so our permutation is even and we've found representation for it.

  2. They are not in place, they are swapped. Because on each step of algorithm permutation is even, and it differs from our permutation by one swap, thus our permutation is odd, so it can't be represented.


So we've proven this theorem and got $$$O(n)$$$ algorithm with good constant, which can be useful in other problems involving parity of permutation.

Full text and comments »

  • Vote: I like it
  • +85
  • Vote: I do not like it

By thematdev, history, 3 years ago, translation, In English

Hello, Codeforces.

I've sent three submissions with different compilers on problem 1553E - Permutation Shift from last round and got different results(OK, ML 1, WA 1)




Then i've ran valgrind (g++ 11.1.0) and discovered strange "still reachable" memory addresses, somehow connected with ios_base::sync_with_stdio. Then I realised, that fast IO was in solve function, which is called in main $$$T$$$ times for each test case. Then I moved it to main and got OK in all compilers.

valgrind output on sample

Pretty strange and interesting situation, so I am asking those, who know what's the problem to write about it in comments. Also I am glad to see critics of my code, especially if it will help to avoid situations like this.

Full text and comments »

  • Vote: I like it
  • +53
  • Vote: I do not like it

By thematdev, history, 3 years ago, In English

Hi, Codeforces! I have 13 successful hacks of problem D on last round, and also my solution is TLed(probably on one of my tests :)), and i am going to show you, how it works.

So we have two parts of solution.

The first is to precalculate lowest divisor of each number. It can be done with simple Eratosthenes sieve, which has time complexity $$$O(N \log N)$$$ if you do sieve loop for all numbers, and $$$O(N \log \log N)$$$ if you do loop only when number is prime. It can also be done with $$$O(N)$$$ time and memory using linear sieve.

Second part is the answer calculation, you need to add $$$2^k$$$, where $$$k$$$ -- number of different prime divisors. So if you haven't precalucated it on sieve step, it will be $$$O(\log x)$$$ per divisor, otherwise it will be $$$O(1)$$$.

Now we will try to adjust numbers $$$c, d, x$$$ to hack $$$O(t\sqrt{x} \log x + N \log \log N)$$$ solution. Because we are counting distinct prime factors of numbers like $$$\frac{\frac{x}{d_x} + d}{c}$$$, we will use $$$c = 1$$$. And we are factorizing $$$x$$$. So the first idea is to find $$$x$$$ with biggest divisors number, and that $$$x$$$ is $$$8648640$$$. And then we will try to maximize

$$$\sum\limits_{d_x \mid x} s(x/d_x + d)$$$

where $$$s(n)$$$ -- sum of powers of primes in factorization of $$$n$$$(exactly that much operations we do).

And we have first powerful hack. 10000 tests with $$$c=1, d=x=8648640$$$. List of successful hacks using this method is below

But some solutions weren't hacked by this test. And there are more reasons of it. Sometimes people precalculate lowest divisors powered to its power, and by Second Merten's Theorem it is $$$O(\log \log x)$$$ average, and also our $$$d$$$ approach doesn't work. But the main problem is memory and cache, so we can use randomized generator with more numbers with huge amount of divisors. But how can we use randomized generator on codeforces? It is simple, we just need to set seed in mt19937 and try to adjust it.

Some examples

User: haruki_K

Submission: 110353111

So, there're a lot possibilities to hack solutions, such like use number $$$d = (3 \cdot 5 \cdot 7 \cdot 11 \dots) - x$$$. But there are more stranger things. For example three submissions(all of them is my code of this problem, and all same): 110370237, 110420633, 110439475

If you can explain time difference, you're welcome.

So in summary, I want to say, that constaints was quite imbalanced, because people who just hadn't precalculated answer, but figured out idea just got TL or hacked solution and negative delta and it is bad. EDUCATIONAL round problems constraints shouldn't be like this.

Also i want to thank plagues just for sending my solution to try to mock me :)

Full text and comments »

  • Vote: I like it
  • +110
  • Vote: I do not like it