How to solve this problem from the recent contest on codechef "Any body can code"

problem link -

In a nutshell: do DP.

Key observation 1: When you encode each character c \in \{0, ..., 25\} to 2^c, range XOR of ‘palindromic’ substrings is always one of 27 integers. That is, a ‘palindromic’ substring of even length always takes 0 and one of odd length takes 1, 2, 4, …, or 2^{25}.

Now let \operatorname{cumxor} be the array of the cumulative XORs of the given sequence s. Here we express a range XOR s[l] \oplus s[l+1] \oplus, ..., \oplus s[r-1] as \operatorname{cumxor}[l, r). The DP array will be as follows:

\operatorname{dp} [x] := the smallest number of partitions of s[0, x) such that each substring is ‘palindromic’.

For each x, we want to update \operatorname{dp}[y] with \min(\operatorname{dp}[y], \operatorname{dp}[x] + 1) for all y such that \operatorname{cumxor}[x, y) takes one of the above-mentioned values. The problem is, these destinations may be too many and the worst time complexity of this DP is {\mathcal O}(N^2).

Key observation 2: If \operatorname{cumxor}[x, y_1) = \operatorname{cumxor}[x, y_2) and y_1 < y_2, you only have to update \operatorname{dp}[y_2].

Think about that you further ‘palindromically’ move from y_1 to another index z (> y_2). Since \operatorname{cumxor}[y1, z) = \operatorname{cumxor}[y_2, z), you can also update \operatorname{dp}[z] from \operatorname{dp}[y_2]. i.e. these two update paths x \rightarrow y_1 \rightarrow z and x \rightarrow y_2 \rightarrow z are redundant. (I leave the other case to you: z is in (y_1, y_2).)

Then we introduce another map \operatorname{last}:

\operatorname{last}[b] := the rightmost position x in s, such that cumulative XOR \operatorname{cumxor}[0, x) is equal to b.

Now we can reduce the destinations of update: for each x, we only have to update \operatorname{dp}[\operatorname{last}[b]], for all b such that b \oplus \operatorname{cumxor}[0, x) \in \{0, 1, 2, ..., 2^{25}\}.

The time complexity of this DP is {\mathcal O}(\alpha N), where \alpha is the size of the alphabet.

1 Like