A Greedy, Math Problem

Rachit Jain, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft

Tags: math, greedy, constructive, combinatorics

So I have found questions from AtCoder interesting since the launch of the site.  

Here is another problem: you are given a  number $n(<10^{12})$ and you have to find an array of size $\le 200$, such that there exist exactly $n$ subsequences of the array which are good. A subsequence is good if it's first half is same as the second half like (1,2,3,1,2,3).   

I was amazed by looking at the solution for this. I wasn't able to solve it on my own. So here is the solution:  

Let $P_k$ denote any permutation of first $k$ natural nos. Then consider the array $A$ formed by adding the sequence of first $k$ natural nos to $P_k$  i.e $A$ = $\{P_k, 1, 2,3,4,...,k\}$  

Now the total no of good subsequences of $A$ is same as number of increasing subsequences in $P_k$.   

Now, note that if total no of good subsequences in $P_k$ are $x$, then we can place the next number $k+1$ in  

1. Front of $P_k$, resulting in total good subsequences to be $x+1$.
2. Back of $P_k$, resulting in total good subsequences to be $2x$.

Now when we need $n$ total good subsequences, we can recursively find the array that will generate it based on the parity of $n$.  Note that you scale down $n$ by half in atmost two steps, so we will need at max $2log_2(10^{12})$ steps i.e $80$ steps.

Check the code for details.