Any idea? I have solved part a) it is rather easy, but part b) seems difficult to me.

These days you should know preliminary results (less than a week), organizators will send that results to local organizers and you should ask them and when all complaints on preliminary results are done you should know results about 2 weeks after preliminary results I hope this will help you

Assume $n>1$

(a) The answer is Click to reveal hidden text

For the upper bound consider the sequence $111\dots 10\dots 000$ where we have $\left \lfloor \frac{n}{2} \right \rfloor$ 1s and $\left \lceil \frac{n}{2} \right \rceil$ 0s. As for the lower bound let $f(n)$ be the number of permutations, and let there be $a$ 1s and $b$ 0s in the sequence. We have that $f(n) = 2^a - 1 + 2^b - 1$ + #mixed permutations $\geq 2^a + 2^b - 2 \geq 2\cdot 2^{\frac{n}{2}}-2$ From this the conclusion follows.

(b) The answer is Click to reveal hidden text

For the lower bound notice that each 1, besides the last 1 forms a nice permutation with the next 1 in the sequence, as well as with itself. And the same holds for the 0s. Therefore we have $f(n) \geq a + (a-1) + b + (b-1) = 2n - 2$ As for the lower bound, we proceed by induction. One can easily find constructions for $n=2,3,4$, so let $x_1x_2\dots x_n$ be a sequence with $2n-2$ nice permutations. Note that if $(x_0, x_{k>2})$ is a permutation, then so is $(x_1,x_{k-1})$. However we know by our assumption that $k-1$ and thus $k$ is unique. We insert $x_0 \neq x_k$ for this $k$, then we can have added at most $2$ new nice permutations $(x_0,x_0)$ and $(x_0, x_i)$ [where i=1 or i=2], and thus the bound holds.