 # Help me understand the output

hey guys , i’m a beginner in competitive programming can you please help me understand the 2nd line of output in this problem in codeforces https://codeforces.com/contest/4/problem/B

Second line of output is the number of hours spend on corresponding days.
Input
2 \,5 \\ 0\, 1 \\ 3\, 5

Output

YES \\1 \,4

Number of hours spend on studying biology on day 1 is 1.
Number of hours spend on studying biology on day 2 is 4

Which amounts to total 5 hours which is needed sumTime.

Hope it helps.

i understand that but how can i calculate if a test case is like this
Input
4 22
3 5
6 7
3 7
1 3

Output

??

Your input is wrong. There should be 4 lines after your 1st line as the value of d given is 4

yeah sorry for the mistake i updated it please take a look

I haven’t done this question yet but it can be solved as follows -
you have to make the combination of hours of days in such that it will add upto sumTime. The minimum hours total you have to spend can be obtained by adding minimum of each day. The maximum hour you can put can be obtained by adding maximum of each day. So this minSum \leq sumTime \leq maxSum. This should suffice.

i already had done that bro its for the first output . i cant get the logic how to add up hours from the ith day to calculate the no of hours he spent for preparation

Input
4 22
3 5
6 7
3 7
1 3

Output

YES
5 7 7 3

Take another example for better understanding.
Input :
4 20
3 5
6 7
3 10
1 3

Output :
YES
5 7 7 1

Here you have to apply greedy approach. Greedy in the sense that take all the minimum hours required to study each days and sum them. i.e. adding each day’s min hours. This is the minimum number of hours you have to spend in total. Lets say this variable is curr Now you have to see how much hours we can get by studying maximum and adding to it. i.e. add max_i - min_i (represents how much more hour in a day you can spend) as much as possible. you have to see that the sum does not cross the total studying hours. When it can surpass the total then you have to realize that we cannot take maximum over there so we have to choose how much we are far away from total. So we take the difference left. And for the rest take the minimum number of hours.

For above example add all the min hours you’ll get curr = 13 now you have to take maximum number of remaining hours as much as possible. For first day you can spend 2 hours more (5 - 3) so now our curr = 15 and print the maximum hour 5 for second one you can take 1 hour more so curr = 16 and print the maximum hour taken 7 now for third one you cannot take all 10 - 3 = 7 hours. You can only take 4 hours out of them so you have to take minimum hour 3 and sum it to remaining hour you can take 4 i.e. print 3+4 = 7, now you can simply print remaining minimum hours (which were already taken) i.e. 1
I hope you understand. Otherwise you can refer to my code https://pastebin.com/tLE794Mj

1 Like

thanks for your help no need of your code i can do it now 