Educational Round 83 problem E (Array Shrinking): Another solution O(V * N)

Revision en4, by reyad, 2020-03-14 09:58:38

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.

History

Revisions

Rev. Lang. By When Δ Comment
en4 reyad 2020-03-14 09:58:38 0 (published)