Hi Everyone,
I'm a newbie here.I just started solving Div 2 A problems. I solved the following problem using a brute force approach. http://mirror.codeforces.com/problemset/problem/194/A
I was looking at the editorial here — http://mirror.codeforces.com/blog/entry/4673 I don't understand the logic behind "3n-k" being used.
Can anyone please help?
If k > 3*n the sum is big enough such that we can only use exams with value > 3 which means that we won't resit any exam.
Otherwise, we'll consider all the exams as having value 3 and decrease their value by 1 from left to right by 1 until their sum is equal to k also adding 1 to a counter.
ex: n = 4, k = 8 -> 3 3 3 3 ( sum 12 ) we'll need to decrease all the values by 1 in order for their sum to be 8.
So the question because how many times do you need to decrease the sum ( 3n ) in order to make it equal to k which is by definition equal to their difference.
Hi There. Thanks for the response. I understand the case for k<=3*n. If k>3*n, isn't there a possibility of having to resit an exam. For eg., n =5,k= 18 .Here k>3*n. We could use 4 4 4 4 2. I understand that, here the ideal solution would be to use 4 4 4 3 3. What I am trying to understand is, why is it that there will always be a solution without the need for a '2' when k>3*n. Is there something that I am missing in the question or may be there is some trivial proof?
If k > 3*n we can set all the values to 3 and still have some of the sum left.
ex: n = 5, k = 18
First we set all of the values to 3: 3 3 3 3 3 ( sum = 3*n = 15 ) Then we increase them from left to right until we reach the sum k since all the values are already > 2 we'll never have to resit an exam.
That makes sense. Thanks :) . When you explained that, it became obvious :) .....
Np, good luck solving problems :)