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

Правка en3, от reyad, 2020-03-14 09:52:21

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.

Теги education round, dp, greedy, python

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский reyad 2020-03-14 09:58:38 0 (published)
en3 Английский reyad 2020-03-14 09:52:21 70
en2 Английский reyad 2020-03-14 09:47:47 6
en1 Английский reyad 2020-03-14 09:44:22 790 Initial revision (saved to drafts)