How can we solve Problem D in O(n)?

Is someone solved C using the ternary search on final value of minimum element and cost of comparison equals no of moves required for that final value?

Why do we need random numbers for primes in problem F?

Here I've got a solution to problem F without hashing or any other randomicity. Though I don't know how to prove it, it seems to be correct. Due to the limitation of the space, I'll only put the conclusions here.

First if $$$ n = 1 $$$, the answer subset include only $$$ 1 $$$. Now we assume $$$ n \not = 1 $$$.

If $$$ n \equiv 1 \pmod 2 $$$, we check if $$$ n \cdot (\frac{n - 1}{2} - 1) $$$ is a square number. If so, the answer subset is all numbers from $$$ 1 $$$ to $$$ n $$$ except $$$ \frac{n - 1}{2} - 2 $$$ and $$$ n - 2 $$$.

If $$$ n \cdot (\frac{n - 1}{2} - 1) $$$ is not a square number, $$$ n $$$ will not be in the answer subset, and we let $$$ n \leftarrow n - 1 $$$ and continue our discussion.

So we now have $$$ n \equiv 0 \pmod 2 $$$. Let $$$ m = \frac{n}{2} $$$.

If $$$ m \equiv 0 \pmod 2 $$$, the answer is $$$ 1, \cdots, n $$$ except $$$ m $$$.

Else we have $$$ m \equiv 1 \pmod 2 $$$. Check if $$$ \frac{m + 1}{2} $$$ is a square number. If so, answer is $$$ 1, \cdots, n $$$ except $$$ m + 1 $$$.

We also check if $$$ m = 9 $$$. If $$$ m = 9 $$$, answer is $$$ 1, \cdots, n $$$ except $$$ 7 $$$.

In the case that neither $$$ \frac{m + 1}{2} $$$ is a square number nor $$$ m = 9 $$$, answer is $$$ 1, \cdots, n $$$ except $$$ 2 $$$ and $$$ m $$$.

Obviously there must be $$$ \text{answer's size} \geqslant n - 3 $$$, for there will be at most $$$ 2 $$$ absent number for even $$$ n $$$ and one more for odd $$$ n $$$.

Check 140891764 for code. I use this OEIS sequence to reach some of the same conclusion as in the official solution.

As you see, this solution is partly based on the official solution, but to construct the subset by just discussing about $$$ n $$$, instead of using hashing.

I don't know why I printed max(result, 1) and ruined my submission in problem D :'(

In problem C i'm facing overflow issue. Can someone please help to find out where is my code overflowing i have verified the calculations and data type multiple times. 140977108

Problem B: "The general way to prove it is to show that if the order has any inversions, we can always fix the leftmost of them (swap two adjacent values), and the cost doesn't increase." Can anyone give a proof on that?

Can someone please explain D, tutorial explanation is somewhat tough to understand.

For D test case 23 the jury answer is 0.How is 0 answer possible given we always have the string s?

For problem D test case 23 has answer 0.How is 0 answer possible given we always have the string s?

For problem F, solution part: Why do we have to include rf[x]!=x in if (rf.count(x) && rf[x] != x) return {rf[x], i};?

Is there any efficient ternary search algorithm???? I have used ternary search on 1622C - Присвоить или уменьшить. It passed the pretest but give a wrong verdict on system test case. Though, I have also checked +-2 range from the expected range manually. Here is my solution 140786085

Please help me.

I tried using binary search for C. But the solution gets TLE. I can't find the reason for my mistake. Can somebody help?

Here's the link to my submission 141226085

How sometimes answer for D can be 0. Could you please explain?

Can someone explain the accurate floor function in problem C? why can't we simply do (c/d -1) when c<0 and c/d when c > 0 to find the floor?

Can someone explain the accurateFloor function in problem C? why can't we simply write c/d — 1 when c<0?

For problem D, can't we use the inclusion/exclusion principle to count duplicate occurrences?
Here is my solution, but it's giving WA in test 10.
These are the steps of my solution:
1. Compute all the intervals [i,j] such that the number of 1 in the interval is k. Let s1, s2, s3,...sk be the intervals.
2. Number of common combinations between s1, s2, s3,...si is the arrangement of one and zero that are present in the intersection of these. Then use inclusion and exclusion principle to get union of these.

For Problem D, I think there's a pretty manageable way of iterating over the substrings of interest and keeping track of how shuffling different substrings may result in the same string.

Iterating from left to right, say we have processed the substring $$$[l_1, r_1]$$$ and we're now processing $$$[l_2, r_2]$$$. $$$[l_2, r_2]$$$ has a part that overlaps with $$$[l_1, r_1]$$$ and a part that doesn't. Shuffling $$$[l_2, r_2]$$$ will result in a duplicate string if the part that doesn't overlap remains the same as the original.

If there are $$$c$$$ ones in the overlapping interval, then there are $$${{r_1 - l_2 + 1} \choose c}$$$ duplicate strings that result from shuffling $$$[l_2, r_2]$$$.

This approach can reach $$$O(n)$$$.

Can anyone tell me why we can ignore the illegal permutations in problem E? thanks a lot!

My approach for D runs in O(n) except the precalculation of combination (you can easily reduce it to O(n) by using factorials). 150862644

In problem C, I don't understand how the testcase: 10 1 1 2 3 1 2 6 1 6 8 10 gives 7.

Could someone explain a possible sequence of moves?

For C given equation for binary search is,

I believe it should be,