Codeforces Round #631 (Div. 2) - Thanks, Denis aramis Shitov!

Problem : Problem - B - Codeforces

Submission: Submission #75419195 - Codeforces

I’m try to compute sum of valid permutations from both sides and then checking whether these two permutations are immediate to each other.

I’d like to know whether my logic is correct. If not, how should I fix it? TIA.

At any index checks whether left and right are value permutations…Use a data structure like multiset

It’s easier than that. There are only 2 permutations to check, depending on the maximal element x. Either the first x and the last n-x or the first n-x and last x.

3 Likes

Haha, that’s a good one… How can i miss that

1 Like

Sorry, can you please explain more with a short example?

link: here

This submission of mine is without any advanced data structure.

Lemma 1: find x such that two x’s are not present in array.So now there can only be two possibilities of permutations from index 1 to x and x+1 to n and 1 to n-x and n-x+1 to n.

which we can check using two boolean arrays or norma arrays .

check solution .

Man it took some trying but did it finally. Thanks to all.

I wasn’t taking care of repeated elements in permutation sum. Any type of improvement is

appreciated.

1 Like