I have a doubt in Q-C today’s AtCoder Contest. Can someone please explain why this solution works. Thank you !!
Statements are not in english but you can see the code.
Code Link : https://img.atcoder.jp/abc099/editorial.pdf
Question link : https://abc099.contest.atcoder.jp/tasks/abc099_c
The code becomes more understandable when you write it like this…
N is divided into two parts, i and N-i.
c1 is the number of transactions required to withdraw i using only 1 and 6^k.
c2 is the number of transactions required to withdraw N-i using only 1 and 9^k.
Required answer = min value of c1+c2 for all values of i between 0 and N.
Yeah it is more clearer and easy to understand this way but can you explain why did this worked. I mean let’s say 12 now clearly ans is 2 times 6 but in the code we divide by t by 6 and then add t%6 until t is 0. So what is the idea behind this solution.
I can see this working but cannot understand the reason.Thanks for reply 
@vijju123 would be glad if u too have a look at this.
My laptop is broken since last Sunday, so its tough to resolve queries for some time 
. Will try having a look tomorrow
Yeah sure
Okay so whenever you do a coin change using these denominations its always of the form 6^k1+6^k2+…+6^kp+9^m1+9^m2+…9^ml+c right? And what is c? c is because of the 1’s.
So we can treat c as the left out parts that can’t be completed by the 6’s and 9’s. So divide c like c1+c2 such that c1 is the change that couldn’t be completed by the set of 6’s and c2 is the change that couldn’t be completed by the set of 9’s. I hope this is quite clear that we choose c to be as low as possible, it’s always better to take a 6^k or 9^m than 6^k 1’s . So now at first we assume N is completely made up of 1s. Now we choose some i, and try making i with 6^ki’s and 1’s only and rest by 9. See we always will get the optimal partition sometime that is there always exists such an i such that, i=6^k1+6^k2+…+6^kp+c1 and rest is made by 9’s. And the combination of 9’s will also be the same.(I guess this is very clear). So we can calculate the optimal ans even like this. Hope this makes sense?
I used an alternate approach to solve this. One observation is that there are less than log(N) many 6’s and 9’s terms. So we can do a normal coin change in N*log(N)
Yes this made perfect sense. Actually i was not getting what was reason for adding modulo but with your answer i realized that when we keep on dividing by 6 we will get the number of coins we want for denomination 6^i for max i
possible.
Your alternate approach would have been a better option to think during contest i guess. Sorry can’t up vote you but thank you !!
*** Sorry can’t up vote you but thank you !! *** --> Sorry can’t up vote you now, thank you and will do the job later on:) !!
xD @aryan403. np @vishesh345 happy to help. anyways sorry i am not good at formatting stuffs so… xD
Is the query resolved now? Or you want me to look into it?
Yes query is resolved now, thanks for asking