NOCHANGE - Editorial

suraj_kr1729 · February 17, 2020, 10:58am

Which one will be the output for following input
1
7 36
1 2 3 4 5 6 7
option…
a> 0 0 0 0 0 0 6
b> 0 1 0 0 0 0 5
Please explain…

pshrimal000 · February 17, 2020, 11:05am

There may be multiple output, as long as you don’t violate given conditions.Both options are correct.

bugs_bunny_001 · February 17, 2020, 11:09am

@tmwilliamlin
I had a n^2 code basically which gave AC. The testcases were weak. I realized it later, but due to AC didn’t want to optimize it.
https://www.codechef.com/viewsolution/29365605

suraj_kr1729 · February 17, 2020, 11:21am

I think option B is optimum. In case B one will pay Rs 37 only (which is strictly greater than required fair) but in case of A one will Pay Rs 42 (and there is no upper limit it can be any 6,7,8,…and so on).
Since both option is correct for which option i should program ??

pshrimal000 · February 17, 2020, 12:07pm

You should code for option A since it is efficient to find.

sekai_no_owari · February 17, 2020, 12:21pm

i guess this did the trick (O(n))
https://www.codechef.com/viewsolution/29466191

swaraj2129 · February 17, 2020, 12:52pm

Ftlacv - Online C++ Compiler & Debugging Tool - Ideone.com hepl me with this where i am wrong

shravan660 · February 17, 2020, 1:18pm

How in [3,4] for P=12 it’s impossible to use only one set? I can use 3*4 to get the required… and even if I remove one 3 … I can get < 12. Please help someone

anon37213765 · February 17, 2020, 2:03pm

The Problem Statement say that you should find if it is possible to pay more than P. So in this case you should pay at least 13.

codebugger1199 · February 17, 2020, 2:18pm

option a, b both are correct upon removing coin of specified denomination we will get the sum strictly less then the p provided in the question.

shravan660 · February 17, 2020, 2:20pm

Welcome to the community man. Thanks for the reply

shravan660 · February 17, 2020, 2:22pm

2 10
1 5… then it should be atleast 11 here… but the answer is “NO”… how?

anon37213765 · February 17, 2020, 2:22pm

Thanks, you are welcome.

shravan660 · February 17, 2020, 2:27pm

I have asked one more… please help xD

anon37213765 · February 17, 2020, 2:42pm

You can’t construct 11 without violating the rules described in the problem statement.If you subtract one from 11 it will be 10 which is equal to P(but it should me more than P), and you can’t construct 11 only with 5’s. So the answer is NO.

shravan660 · February 17, 2020, 2:53pm

To construct 11… I can have 6 ones and 1 5… So if I remove 5 from it… 11 becomes 6… is it like… if you remove any coin from the combination… you should not get 10…?like 6 ones and 1 5… if I remove 1 from the ones… I get 10… our result from all the possible must be less than 10 after removing?

anon37213765 · February 17, 2020, 3:06pm

If you remove any element from your multiset the sum of the elements should be less than P.

violetval · February 17, 2020, 3:20pm

I implemented a solution based on the editorial, but I’m still getting a WA. I tried several random test cases, but can’t find one that causes my code to fail. Can anyone help me find a test case with which my code fails? CodeChef: Practical coding for everyone

avi_9314 · February 17, 2020, 3:23pm

see this at around 12:00 it will clear the doubt … mostly we did this as we have the denominations in ascending order .
CodeChef February Long Challenge 2020- No Change Required (NOCHANGE) - YouTube

shravan660 · February 17, 2020, 4:13pm

Broooooo thanks a lot