Samsung R&D | Online Assessment | Flow of Numbers

Round 1

Questions: You want to create a sequence {a[0], a[1], ... a[N-2], a[N-1]} whose length is N. The sequence must meet the following conditions:

1. a[0] should always be 0.
2. a[i], the ith number should always be 0 or a positive integer.
3. The absolute value of the difference between ith and i+1 th number should be equal to or smaller than 1. In other words, every i satisfies the condition: |a[i] - a[i+1]| <= 1.
4. Given a limited value of (x,y), the xth number cannot exceed y (a[x] <= y).

Given the length of a sequence N, and M limited values, you need to find the way that maximizes the largest value when creating a sequence satisfying the aforementioned conditions. Then you are required to print the max value. There may be multiple sequences that have a max value.

Example: N = 10, M = 2 {(2,1) , (7,1)} Output: 3 Explaination: The following sequence can be created using the given conditions {0, 1, 1, 2, 3, 3, 2, 1, 2, 3}. And the max value here is 3.

N = 10, M = 5 {(1,3) (2,9) (4, 6) (7, 4) (9, 5)} Output: 5

N = 10, M = 1 {(3, 1)} Output: 7 Explaination: {0, 1, 1, 2, 3, 4, 5, 6, 7}