ACMICL5 - Editorial

dynamic-programming
editorial
hard
icl2015

#1

PROBLEM LINK:

http://www.codechef.com/ICL2015/problems/ACMICL5

##Author:
Jaiwant Rawat
##Tester:
Ankit Sultana

##DIFFICULTY:
HARD

##PREREQUISITES:
Dynamic Programming

##EXPLANATION:

For solving it we will keep track of state as ( a , b ).
In the state ( a , b )

  1. a - denotes the sum
  2. b - denotes the sum formed from only using the first b numbers from the interval [ k1 , k2 ]
    where k1 = minimum value of the start of all the intervals
    k2 = maximum value of the end of all the intervals

Example -

Taking the test case given in question
2
0 2
2 5
1 2

Here we have two intervals [ 0 , 2 ] & [ 2 , 5 ] and we have to find the sum from 1 to 3 .
so following the above approach we have
k1 = 0 ( min of ( 0 , 2 ) )
k2 = 5 ( max of ( 2 , 5 ) )
Now all the values that i can take will lie in this interval only and how many times i can take them is equal to the number of intervals in which that
value lies . Now according to the question k1 minimum value can be 0 and k2 maximum value can be 500 so i can have only 501 distinct numbers for consideration
in worst case
Now the state is ( a , b ) where
a is one of the number belonging to the interval [ N , N + x ]
b is one of the number belonging to interval in [ k1 , k2 ]

Now the transition of the states will be like ( a , b + 1 ) -> ( a , b ) if i am not using the b + 1 in my sum or ( a , b + 1 ) -> ( y , b ) where y
be one of depending on how many b i am considering for the sum .