traynmslf's blog

Doubt regarding this problem : http://codeforces.com/problemset/problem/194/A

By traynmslf, history, 8 years ago, In English

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://codeforces.com/problemset/problem/194/A

I was looking at the editorial here — http://codeforces.com/blog/entry/4673 I don't understand the logic behind "3n-k" being used.

Can anyone please help?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That makes sense. Thanks :) . When you explained that, it became obvious :) .....

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Np, good luck solving problems :)

          → Reply