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.

Tags education round, dp, greedy, python


  Rev. Lang. By When Δ Comment
en4 English reyad 2020-03-14 09:58:38 0 (published)
en3 English reyad 2020-03-14 09:52:21 70
en2 English reyad 2020-03-14 09:47:47 6
en1 English reyad 2020-03-14 09:44:22 790 Initial revision (saved to drafts)