Hello,

I have been trying this question on Spoj BatMan2

It requires to find a LIS from left to right and a LIS from right to left but non overlapping

Someone suggested this solution in comments

really aww sum problem cant wait to share the idea simply go one way and give each number to a increasing or decreasing or nothing max among three is ans

can anyone help with this DP problem

Given a number k , a number n We have to form a K*K square matrix using just the numbers 0 and n such that it has maximum possible determinant We have to write a program that returns such determinant for given values of k and n

for example if k = 3 and n = 13

13 13 0

0 13 13

13 0 13

ie for k = 3 and any non negative value of n required matrix is

n n 0

0 n n

n 0 n

Given a number k , a number n We have to form a K*K square matrix using just the numbers 0 and n such that it has maximum possible determinant We have to write a program that returns such determinant for given values of k and n

for example if k = 3 and n = 13

13 13 0

0 13 13

13 0 13

ie for k = 3 and any non negative value of n required matrix is

n n 0

0 n n

n 0 n

have been trying this question which requires below work done.

PROBLEM

Given an integer n which signifies a sequence of n numbers from {0,1,2,3,4,5.......n-2,n-1}

We are provided m ranges in form of (L,R) such that (0<=L<=n-1)(0<=R<=n-1)

if(L <= R) (L,R) signifies numbers {L,L+1,L+2,L+3.......R-1,R} from above sequence

else (L,R) signifies numbers {R,R+1,R+2,.......n-2,n-1} & {0,1,2,3....L-1,L} ie numbers wrap around

example

n = 5   ie {0,1,2,3,4}
(0,3) signifies {0,1,2,3}
(3,0) signifies {3,4,0}
(3,2) signifies {3,4,0,1,2}

Now we have to select ONE (only one) number from each range without repeating any selection. We have to tell is it possible to select one number from each(and every) range without repetition.

Example test case

n = 5// numbers {0,1,2,3,4}
// ranges  m in number //
0 0 ie {0}
1 2 ie {1,2}
2 3 ie {2,3}
4 4 ie {4}
4 0 ie {4,0}

 Answer is "NO" it's not possible.

Because we cannot select any number from range 4 0 because if we select 4 from it we could not be able to select from range 4 4 and if select 0 from it we would not be able to select from 0 0

My approaches -

1) it can be done in O(N*M) using recurrsion checking all possibilitie of selection from each range and side by side using hash map to record our selections.

2) I was trying it in order n or m ie linear order .Problem lack editorial explanation .Only a code is mentioned in the editorial without comments and explanation . I m not able to get the code

I am not able to understand the logic/algo used in the code and why is it working?

Please suggest ANY linear method and logic behind it because problem has these constraints

1 <= N<= 10^9
  1 <= M <= 10^5
  0 <= L, R < N

which demands a linear or nlogn solution as i guess??

The code in the editorial can also be seen here http://ideone.com/5Xb6xw

Warning --After looking The code I found the code is using n and m interchangebly So i would like to mention the input format for the problem.

INPUT FORMAT

The first line contains test cases, tc, followed by two integers N,M- the first one depicting the number of countries on the globe, the second one depicting the number of ranges his girlfriend has given him. After which, the next M lines will have two integers describing the range, X and Y. If (X <= Y), then range covers countries [X,X+1... Y] else range covers [X,X+1,.... N-1,0,1..., Y].

Output Format

Print "YES" if it is possible to do so, print "NO", if it is not.