Please subscribe to the official Codeforces channel in Telegram via the link ×

reyad's blog

By reyad, history, 18 months ago, In English

A O(V * N) solution is also possible for Array Shrinking.

The idea of this solution is building segments of value V+1 from V. Let's have a sequence i...j of value V and j+1...h is another sequence of value V, then value of sequence i...h would be V+1.

Let's consider e[v][i] = j, then we can do as follows:

j = e[v][i]
h = e[v][j+1]
if j != -1 and h != -1:
    e[v+1][i] = h

This process can be used to find all the possible shrinking sequences. Then the start and end index of the sequences can be used to find the possible minimum length.

Here's the Solution.

  • Vote: I like it
  • +20
  • Vote: I do not like it