Codeforces Educational round 170 Discussion stream (with hints)

We can do one of the following 2 things -

• Either write both strings without using 2nd action
• Or we first write longest common prefix string, then use 2nd action and then write the remaining strings.

Use pen and paper and write down table C.

Table C looks like this -

1
1 1
1 2 1
1 2 4 1
1 2 4 8 1
1 2 4 8 16 1

If $k=n$, $C[n][k] = 1$, else $C[n][k]=2^k$

Sort the array and then use two pointers

Alternatively, sort the array and then for each fixed L, binary search largest R such that you can take all elements in subarray $[L \ldots R]$

$dp[i][x][y]$ denotes maximum checks among first $i$ queries that we can pass if our current intelligence level is $x$ and current strength level is $y$.

Its never optimal to leave any acquiring point. So $x+y$ will always be no of $r_j=0$ for $j \le i$.

This allows us to remove one dp dimension.

$dp[i][y]$ denotes maximum checks among first $i$ queries that we can pass if we have used $y$ attribute points for strength, and all remaining points for intelligence.

Whenever we have $r_i < 0$, we essentially do $+1$ to a suffix in above dp array.

Whenever we have $r_i > 0$, we essentially do $+1$ to a prefix in above dp array.

For $r_i=0$,

If we increase strength, we can do $dp[i][y]=\max(dp[i][y],dp[i-1][y-1])$

If we increase intelligence, we can do $dp[i][y]=\max(dp[i][y],dp[i-1][y])$

If we use lazy segment tree for range addition.

We can solve this problem in $O(m^2 \log m + n \log m)$.

$O(m \log m)$ per attribute point query, and $O(\log m)$ per check query.

We can even do better, without using any segment tree.

Lets maintain difference array for $dp[i][*]$ table.

So range additions are just $+1$ and $-1$ at 2 places.

Allowing us to do this $O(m^2+n)$.

Refer implementation for more details.

Lets pick a suite and distribute $m$ cards in descending order.

Lets say we have distributed all cards between $[i \ldots m]$, we have given $p_1$ cards to first player and $p_2$ cards to second player.

Let $Y$ denotes minimum no of suite 1 cards we need for this assignment.

Let $dP = p_1-p_2$

Now, we can use dp here,

$dp[i][dP][Y]$ denotes above state.

$Y$ is essentially minimum possible value of $dP$ when we are assigning all the cards.

The transitions are as follows -

If we assign $i-1$ card to first player $dp[i-1][dP+1][Y]+=dp[i][dP][Y]$

If we assign $i-1$ card to second player $dp[i-1][dP-1][\min(Y,dp-1)]+=dp[i][dP][Y]$

Another important observation is we can only give away equal no of cards to both the player if $dp=Y$ for every suites except 1, ie we only need $dp[1][X][X]$

Another important observation is -

No of suite 1 cards assigned to first player $\ge$ No of suite 1 cards assigned to second player.

For all other suites $2 \le j \le n$,

No of suite $j$ cards assigned to first player $\le$ No of suite $j$ cards assigned to second player.

Now, we can first fix the no of extra suite 1 cards (say $K$) we want to give to first player.

Let the no of extra cards given to second play for other suites be $x_2, x_3, \ldots, x_n$.

Then we need $x_2+x_3+\ldots+x_n = K$.

This part can be done using knapsack.

Its possible to solve this problem for following constraints -

• $N \le 10^{18}$
• $M \le 500$

Let first decide if we want to do an operation on $x_i$ or $y_i$.

We can ensure that each $a_i$ is either 0 or 1.

Do $-1$ if $a_i$ is 1, and $+1$ if $a_i$ is 0.

Now, lets create a graph with $n$ nodes and $q$ edges.

$i$-th edge connects $x_i$ and $y_i$.

Selecting $x_i$ or $y_i$ for each query is equivalent to giving a direction to each edge in this graph.

If edge is directed from $x_i \to y_i$, we select $x_i$.

If edge is directed from $y_i \to x_i$, we select $y_i$.

$a_u$ will be equal to parity of no of incoming edges on $u$.

Formally, we have a graph with $n$ nodes, and $q$ edges.

We want to assign direction to each edge such that no of nodes with odd parity of incoming is minimum possible.

This is quite a well known problem (CodeChef EDGEDIR), and have appeared quite many times.

For each connected components, if no of edges is odd, then its possible to direct edges in such a way that only one node has odd parity of incoming edges.

For each connected components, if no of edges is even, then its possible to direct edges in such a way that all nodes have even parity of incoming edges.