Codeforces Round #718 Group Photo - Binary Search

Solution:

First of all, Base on $c_i-c_{i-1}\leq c_{i+1}-c_i$ and $p_i-p_{i-1}\geq p_{i+1}-p_i$ we can roughly found that：

1. C is to the left of P. Because C is dense on the left and sparse on the right, P is dense on the right and sparse on the left.
2. The maximum interval between any two C or any two P is 1. Because if the interval between two Ps is 2, then the two ?s in the middle of CP??PP can only be C, and the interval between them is 1, which is smaller than the 2 in the leftmost C.

But the above conclusion has 4 special cases:

1. There is a P on the far left. Like PCCPP.
2. There is a C on the far right. Like CCPPC.
3. There is a P on the far left and is a C on the far right. Like PCCPPC.
4. Several digits on the left are all P, and all the digits on the left are C. Lke PPPPCCC.
   In the first three special cases, the length of the special bit can only be 1. It is not difficult to find that adding one more bit will produce a result that does not meet the conditions like PPCCPP.

Excluding the fourth special case, the ordinary case + 3 special cases can be expressed as: (P)?(C){1,}(PC)*(P){1,}(C)?. That is, the beginning P is optional, and the end C is optional. Then there are at least one C and P on both sides, and the remaining positions are filled with PC.

So we can notice that for the length of C that has been selected, the more PC, the smaller the sum of P.

So we enumerate the length of C according to 4 cases. Then find the maximum length of PC by binary search. Then we find the number of possibilities for the current case and the selected length of C.
In the second special case, the length of C is 3 as an example：CCC???????C
There are the following possibilities: CCC|PCPCPC|P|C, CCC|PCPC|PPP|C, CCC|PC|PPPPP|C, CCC|PPPPPPP|C.
Obviously the less the PC the more the P. So we can get the number of PCs by binary search.

Code:

Submission #114072656 - Codeforces

Codeforces. Programming competitions and contests, programming community

Codeforces

Tips for implementation:

It is recommended to extract a function to specifically binary search the number of PC under the conditions given by the external situation

    private static long solve(int last_c_pos, int last_unknown_pos, long current_sum_P_minus_C) {
        int len = last_unknown_pos - last_c_pos - 1;
        if (len % 2 == 1) len--;
        int left = 0;
        int right = len / 2;
        while (left < right) {
            // binary search
        }
        // return the number of all possibilities
    }