You are not logged in. Please login at www.codechef.com to post your questions!

×

ACMICL5 - Editorial

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 .

This question is marked "community wiki".

asked 25 Mar '15, 00:12

f2012086's gravatar image

2★f2012086
14
accept rate: 0%

edited 23 Apr '15, 17:12

admin's gravatar image

0★admin ♦♦
19.0k348495531

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,366
×1,754
×1,206
×40

question asked: 25 Mar '15, 00:12

question was seen: 1,130 times

last updated: 23 Apr '15, 17:12