problem link : https://www.codechef.com/problems/CHSTAMP
editorial : https://discuss.codechef.com/questions/76894/chstamp-editorial
I am trying to understand editorial but starting of editorial is somewhat ambiguous. Can anyone explain me first two paragraphs of editorial with an example ?
The problem can be solved using graph approach easily. What you need to do is first keep track of how many days you have. Now iterate over each day offers starting from the last day to beginning. If you are on ith day then for all the offers of that day make a graph. In the graph for each connected component find the maximum you can gain from each conversion. Suppose on 5th day conversions are 1 2 , 3 4, 4 9, 11 19 then in the graph yo will get two connected components and for each connected component you upgrade the maximum value in a particular table i.e. in the first connected component upgrade max of 1,2,3,4 as max of 9 which will be at least 9 and in the second component upgrade max of 11 as max(19) which will be either 19 or greater than that. I am saying it either 19 or greater than that because maybe if you have already seen the 6th day and in that day you upgraded max[19] as 21 then here 11 will become max(19) i.e. 21 .Do comment for any help.