PERMSHOP is a cool problem.

The core observation is that only $$$K = 3$$$ and $$$K = 6$$$ contribute to the answer. Bruteforce all permutations of length $$$3$$$ and length $$$6$$$, and store these “valid permutations”, which are those where Alice and Bob choose the same item set.

Now, a valid permutation must be a subsequence of the original permutation $$$P$$$. Use DP to count them.

Moreover, the difficulty of the problem set is absolutely worthy of being rated till $$$6$$$ stars.

AC Code

people are sleeping on codechef. lovely contest!

I don't know why my solution for Stable Diffusion works.

So I checked the obvious — an array $$$a$$$ ($$$0$$$-indexed) is stable if one of the following holds:

1. $$$|a|$$$ is odd

2. $$$|a| = 2$$$

3. There is an index such that $$$a[i]=a[n-i-1]$$$

Now, the only remaining array format that needs to be checked is $$$a[i] = 3 - a[n-i-1]$$$, where $$$|a|$$$ is even and $$$|a|\ge 4$$$. Using brute force, I found this case for such arrays, which I'm not sure how to prove:

If there is a pair $$$a[i]==a[i-1]$$$ where $$$i=1$$$ or $$$i=2$$$ or $$$i=|a|/2-1$$$, the array is stable. Otherwise it's unstable.

Submission