Author: Trung Nguyen Problem LinkPracticeContest DifficultyEasyMedium PREREQUISITES:Data Structure ProblemWe are given an array A with some elements and some unknowns. The goal is to find the number of possible arrays with numbers from 1 to k that satisfies certain constraints. Every constraint forces us to make some interval either strictly increasing or strictly decreasing in steps of one. ExplanationLet's store the information of constraints in another way. Let dx[i] = how much we have to add to A[i] to get A[i+1].
For some elements there are no constraints and we have more freedom, for sake of simplicity let's define its dx value as 0. Note that all information about constraints is stored in dx. Moreover the structure of dx is as follows: [C][0][C][0][C][0]... Where each [C] represent a block of contiguos cells with values either 1 or 1, and [0] represents a block were dx is 0. Let's see in how many ways is possible to complete the array A for every type of block.
The only question that remains is how to generate array dx. If we iterate over every constraint it is quadratic. However, if constraints are not overlapping it is linear. Note that is not necessary to store overlapping intervals (constraints). For example, if segments [3, 5] and [4, 6] should be increasing, then is the same as saying that [3,6] is increasing. Therefore we can merge intervals and get only nonoverlapping intervals. There are many ways of merging intervals. For example, we can keep a set of disjoint intervals. Let's say that interval [l1, r1] is smaller than [l2, r2] iff r1 < l2. When we add a new interval to the set, we have to remove all the intervals that intersect it (we can find them with binary search) and add a new interval. Every interval is added and removed at most once, so it is asymptotically efficient. Implementation
This question is marked "community wiki".
asked 18 Mar '18, 23:43

Is there any other way to solve this question? Thanks in advance. answered 22 Mar '18, 17:46

In the author's solution and in the line  if (a[k] < 1  a[k] > ::k) res = 0; what is the meaning of ::k ? what does a[k]> ::k give ? answered 25 Mar '18, 11:59

If there are two increasing sequence [1..5], [10.. 15] And one decreasing sequence [5 10] How will divide the block in [c][0][c] answered 25 Mar '18, 15:20
@kamal_kulu_23, This case will not have the block [0]. So, it can be represented as, [c][c][c], where, the first [c] is a block with increasing values [1,1,1,1], second [c] will be [1,1,1,1,1] and the third would be [1,1,1,1,1].
(25 Mar '18, 22:01)

Can someone please explain me how are we calculating number of ways = k(maxmin) for a range having all unknown elements(a[i]=1) using sum,max,min from dx[] We can generate new possibilities by adding some constant c to all the elements of the block, however c + minimum ≥ 1, and c + maximum ≤ k (remember that all numbers should be between 1 and k) answered 26 Mar '18, 14:22

Perhaps an elegant way to generate array dx[] can be
answered 26 Mar '18, 19:13

can we make array dx[] with the help pf segment trees? how much will be its time complexity? O(mlogn) i guess? answered 31 Mar '18, 00:41
