Codeforces Round 972 Discussion stream (with hints)

Lets fix the count of aeiou $C_a,C_e,C_i,C_o,C_u$

What is the minimum number of subsequence palindromes?

No of palindromes that consist of only a is $2^{C_a}-1$ and similarly for eiou.

So lowerbound on no of palindrome is $2^{C_a}+2^{C_e}+2^{C_i}+2^{C_o}+2^{C_u}-5$

Does there exists a permutation where this lowerbound is achievable?

This lowerbound is achieved on strings of form aaaaaaaaaeeeeeeeeeeiiiiiiiiiioooooooooouuuuuuuuu

How to find optimal values of $C_a,C_e,C_i,C_o,C_u$?

In optimal answer $|C_x-C_y| \le 1$.

You can try to prove it using exchange arguments technique.

Separately solve for cases when David is on left side of both the teachers, in between the teachers and right side of both the teachers.

We need the nearest teacher on the left side and right side, and then B1 solution works.

To find the nearest teachers, you can either use binary search or use lower_bound stl function.

Let’s first simplify the scoring function.

Let’s say we have fixed string $t$, you do we find the score?

Let the no of narek strings formed is $c$ and total no of chars narek is $t$.

No of chars found by chatgpt will be $t-5 \cdot c$.

The score is $5 \cdot c-(t-5 \cdot c) = 10 \cdot c-t$.

Another way to see this cost function is -

Chatgpt will reduce score by -1 whenever it finds any of the char narek.

We will increase by +10 whenever we complete the string narek.

Now, $dp[i][j]$ can be the maximum score so far such that we have processed the first $i$ string, and we have got the first $j$ chars of uncompleted narek string (which is required for +10).

Use Minimax Algorithm

Let’s say we know what positions a player playing $i+1$ can select and still win the game.

Can we use this information to find all the positions that a player playing $i$ move can select?

A player selecting $r,c$ on the move $i$ wins the game if and only if there is no position in $[r+1…n][c+1…m]$ which player playing $i+1$ move can select and win.

With careful implementation, one can solve the above problem in $O(N \cdot M \cdot L)$ time complexity.

First solve E1.

Consider the following testcase -

1 2 2
2 2 1
2 3 3

If a player has to select $2$ from somewhere, they should only select $(1,3)$ or $(2,2)$ or $(3,1)$.

Selecting $(2,1)$ instead of $(2,2)$, will just increase no of possible moves for the opponent.

We should ignore the nos not present in A.

For each nos present X in A and each column C, we can precompute maximum R such that $B[R][C]=X$.

Now, we should play this game only on these indexes.

With careful implementation on can solve it in $O(N \cdot M+N \cdot L)$.