NOCHANGE - Editorial

Thank you @tmwilliamlin for writing such a detailed and explanatory editorial.

I tried to solve the problem during contest but ended up with WA

Can someone please have a look and give me some test cases so that I can understand where I am getting it wrong?
https://www.codechef.com/viewsolution/29666614

https://www.codechef.com/viewsolution/29611613
why only subtask 1 is failing???
subtask 2 and 3 are giving AC
PLEASEEEEEEEE SOMEONE HELPP MEEEEEEEEE

Try this case: yrcjkg - Online C++ Compiler & Debugging Tool - Ideone.com

The following code fails all the tests. but when I replace the line number 27 “ans[i] = P//D[i] -1” with “P -= D[i+1]; ans[i] = P//D[i] + 1”
all the tests pass. Please suggest me the test case when above two code lines will produce different results.

https://www.codechef.com/viewsolution/29800962

https://www.codechef.com/viewsolution/29676712
plzzz tell me where i am wrong

https://www.codechef.com/viewsolution/29615237
I don’t know why I was wrong in the 1st test case ? Someone helps me, please

You have not followed the editorial exactly, though.

Test case

1
2 20
4 10

Thank you for providing a helpful test case. That may have been one of the test cases I generated, but it would not have been immediately apparent to me that the answer the code resulted in was wrong. That’s why we need to see the test cases after the contest.

You made the same error I did. See the test case that tmwilliamlin sent to me.

With denominations [1,5] and P as 10, it is impossible to create a combination where we are overpaying.

If you take example such as
1*7 + 5*1 = 12
Here, you are deliberately overpaying (non optimised combination) to reach to ticket price.
We can instead go with
1*6 + 5*1 = 11

But in this scenario we can remove a 1 coin and reach the exact ticket price.

Hence, there exist no such scenario where we can overpay.

@tmwilliamlin Can you help me here? @violetval @anon37213765

Try

Test Case

1
2 20
4 10

Try

Test Case

1
2 20
4 10

1 Like

Thanks.

Try

Test Case

1
3 15
3 4 5

thankyou soooo muchhhh

I m sorry for the late reply, but even 61,15 is also a way of deliberately over paying… how does that work then?

Agreed. There is no possible way to overpay.
Hence the answer is NO

In the case of 2 35 and 7 5… how does the combination work then?

Suppose you have 4 $7 and 2 $5 coins. With these coins, or any subset of these, it is not possible to tender exact change of $35.

Hence this case is an example of overpaying.
Denominations are entered in increasing sequence in input i.e. 5 7
YES 2 4

1 Like