daihan's blog

CSACADEMY : Socks Pair help please
By daihan, 7 years ago, In English

Hello codeforces forum , I am getting WA on test 9 and 11 . Tried many times to find the bug , but failed . Can you please provide me some test case which my code give WA .

problem link : https://csacademy.com/contest/archive/task/socks-pairs/statement/

My code : http://paste.ubuntu.com/25060704/

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

3 4

3 4 4

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    Thank you for your kind reply .

    For

    4 5

    2 4 6 8

    how ans is 13 ? Ans should be 12 . shouldn't it? If ans is 12 , in which case it will worng ? I can not find it .

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      your idea is not correct.

      What would be worst case, for above example?

      Take 1 from color 1, 3 from color 2, 5 from color 3, 3 from color 4. We got 4 pair of socks until now, and sum 1 + 3 + 5 + 3 = 12. Now you can take 1 more sock from color 1, obtain sum 13 and have 5 pairs.

      In general, worst case is when we choose odd number of socks from each color at first, until we get maximum number of pairs,smaller than k. And then we add more socks to reach k.

      → Reply