4 kyu

Candy thieves

10kodejuice
Description
Loading description...
Fundamentals
View
AllIssues3Questions1Suggestions3Show Resolved
  • Please sign in or sign up to leave a comment.
  • K01egA Avatar

    This problem can be reduced to the set cover problem, which is NP-hard, looking at size of tests I can assume that reference solution uses some king of greedy approach, which do not guaranty optimal solution. Example A = [3, 8, 8, 6, 7], B = [2, 2, 3, 5, 6], k = 6. My solution is 3. First thief can take from jars 1 and 4 second from 2, third from 3 and 5

  • lachesism Avatar

    This comment has been hidden.

  • Blind4Basics Avatar

    Hi,

    By reading the description, it looks like you're using the underlying assumption/specification that it's guaranteed that A[i]-B[i] <= k (since you don't talk about what to do if too many candies are stolen from one jar). This should be added to the description one way or another (either saying it out loud, or telling all cases will be solvable, or anything else conveying the idea).
    Or did I misunderstand the rules?

    edit: you should add the typical sizes of the inputs too. And a boundary about the expected time complexity.

    Cheers

  • ozichukwu Avatar

    Nwanne, I think some tests are wrong. I'm raising an issue. Close with reason if it's not one.

    min_count([9, 3, 9, 6, 5], [3, 2, 3, 2, 1], 9)
expected = 4
my_result = 3


a = [9, 3, 9, 6, 5]
b = [3, 2, 3, 2, 1]

1st thief takes 6 from idx (index) 0, 3 from idx 2, total == k == 9

a = [3, 3, 6, 6, 5]

2nd thief takes 1 from idx 1, 4 from idx 3, total == 5 (can't take from anywhere again)

a = [3, 2, 6, 2, 5]

3rd thief takes 3 from idx 2, 4 from idx 4, total == 7 (theft completed)

a = [3, 2, 3, 2, 1]

    What am I getting wrong?

    • ozichukwu Avatar

      Once a thief has removed candy from a jar, no other thief may remove candy from that jar.

      my bad, i guess

      Issue marked resolved by ozichukwu 4 years ago
  • eptaceps Avatar

    typo in the line after "notes" -> "theif" 2 times regarding that line, it may be useful (even though it's quite obvious) specifying that a thief can only take all the missing candies from a jar (or none).

    anyway i enjoyed the kata, thanks :)

  • kichi941 Avatar

    This comment has been hidden.

  • rge123 Avatar

    Looks quite fun - haven't had time to do it yet. There is one thing that I think you could make clearer in the description:

    "Note: More than one thief cannot take candies from a single jar." Mybe try: "Once a theif has removed candy from a jar, no other theif may remove candy from that jar"?