Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Number of partitions

Revision en4, by CopeCope, 2019-02-19 17:09:01

Given array A of N <  = 500000 elements and each A[i] <  = N. Find number of partitions of array into some number of subsegments such that every subsegment has length greater or equal to minimum value of subsegment and smaller or equal to maximum value of subsegment.

Example:
A = {1, 6, 2, 3, 4, 3, 4}
Partitions are:
|1|6, 2, 3, 4, 3, 4|
|1, 6, 2|3, 4, 3, 4|
|1, 6, 2, 3|4, 3, 4|
|1|6, 2|3, 4, 3, 4|
|1|6, 2, 3|4, 3, 4|
|1, 6|2, 3|4, 3, 4|

How to solve this problem?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English CopeCope 2019-02-19 17:09:01 0 Reverted to en1
en3 English CopeCope 2019-02-15 02:25:49 6 Reverted to en1
en2 English CopeCope 2019-02-15 02:25:30 6
en1 English CopeCope 2019-02-14 19:56:25 644 Initial revision (published)