1528B - Kavi on pairing duty

Problem statement

Link : https://codeforces.com/problemset/problem/1528/B
 

Gist

There are $2 \times n$ points on the X-axis. You join every point to *some* other point. So it can have different permutations. A permutation is "good" if for all the connections, at least one these hold:
1. Connection A is within connection B - so let's say we have 1,2,3 and 4. And 1 and 4 are connected, and 2 and 3 are connected. So 2 and 3 is *within* 1 and 4. Therefore this works.
2. Connection A is of the same length as connection B. Again let's say we have 1,2,3 and 4. 1 and 2 are connected, and 3 and 4 are connected. Since 1 and 2's connection is of length 1 and 3 and 4's connection is also of length 1 this is a good permutation.

Given the input $n$ we need to output the number of good permutations.

Solution

Thinking

Let's think about the case of over-arches. That is, let's say you have some $n$, and you have a connection from 1 to 2n. Then you have 2n-2 points inside this connection / arch. For each of these connection & this arch, the first condition holds, as each connection is within this arch. Therefore we can just add the answer of $n-1$ input to get that value.

Let's think about the cases when there are no arches.

Can we have small arches which have the other arches within them, but are separate from other small arches? Like for example, let's say $n = 10$. Then you can divide it into 5 groups of 4 points. So can we re-use the answer for 4 here?

The issue here is that the arch of group1 and the inner connection of group2 don't satisfy any condition. Neither they are within each other - as the group 2 connection is not within group 1's arch. Nor do they have the same length, as group 2 connection is smaller than group 1's arch.

One other condition where this can work is you have a group of connections which are of the same length, which are archs for other connections which are smaller but again of the same length. So again the same rule applies like the 1 super arch. Everything inside actually satisfies the first property with these archs, so we can use the previous answers here. So instead of just adding $ans(n-1)$ we add everything from $ans(1)$ ... $ans(n-1)$ here.

Now that, that is out of the picture, besides the 1 super arch, can we have cases when connection lengths are different? If there are two connections with different lengths then one of them needs to be inside the other connection. Since we can't have groups of such archs, having smaller connections within them, then this would mean that if we have connections with different length, we need to have a composition of arches within each other. 1-10, 2-9, 3-8, 4-7, 5-6 - but this is already covered as the first case. 1-10 + $ans(8)$ as the answer of 8 will already contain this case.

Therefore from this we understand that the other case is the only one when all of the connection lengths are the same.



How do we calculate them? So basically you have $2 \times n$ points, and you want to divide them into *some* equal points. Seems like the number of factors would do? Yep.

So for $n$ we find the number of factors - all of them, and add those to $\sum_{i=1}^{n-1} ans(i)$ - and that pretty much is the answer here. This summation can be saved in a var.
 

Implementation

My implementation took 999ms when the time limit was 1000ms. Take this with a grain of salt. I think there definitely should be a better solution.

$dp[n] = (\sum_{i=1}^{n-1}dp[i]) + factors(n)$

Here finding $factors(n)$ efficiently is the main problem. I did it by keeping a vector of `unordered_map`s which kept the number of prime factors. So for example, for $12 = 2^2 \times 3^1$ we save in the map 12 : {{2,2}, {3,1}}. Now if you want to find the number of factors, you just do $(powerOf2+1) \times (powerOf3 + 1)$ = $(2 + 1) * (1 + 1)$  = 6.

12 has 1, 2, 3, 4, 6, 12 as the factors. Yes we are counting the number itself as well in this case.

You get a list of primes, using sieve of eratosthenes, and then find the first prime that divides $n$. Once you get that, you re-use $n / prime$ to query the `unoredered_map` to get it's factors, and then add 1 to the $prime$ you found. Then you use the current map to get factors, and save the map to the `unoredered_map` for $n$.

Here is the submission : https://codeforces.com/contest/1528/submission/304791168




## Learnings



## Timelog