Guys, please answer this, it won't take much time for those who have already solved this.
http://mirror.codeforces.com/contest/552/problem/C
In this problem, if X ≤ wk for where k is the largest possible, then we don't need to use all coins that have higher power than k + 1, i.e. coins wk + 2, wk + 3, ...wn will not be used.
To start with the proof, I will take wk + 2 first.
I need to prove that wk + 2 is not used in all of the valid solutions which means, wk + 2 doesn't occur either on the left or right side of the equation shown at the top. Now, if I could somehow prove that using wk + 2 in left side or right side, I cannot arrive at a solution I would be complete with my proof. I will first put wk + 2 in the left (along with X) and see. I have X + wk + 2 on the left, I also know that X ≤ wk. I can't work any further.
I am not able to prove how.
Ok, guys I got it!!!! (someone helped me). Here's a more easy proof.
Lets think a different way. What are the coin changes that I can make using wk + 2. What is the smallest such change? The smallest change is equal to when we put wk + 2 on the left and all smaller weights on the right i.e.
wk + 2 - wk + 1 - wk - .... - w0
wk + 2 — (wk + 2 - 1) / (w - 1)
But this amount is greater than wk.
Thus, if we use wk + 2, the change must be greater than wk. But, X ≤ wk. So, we can't make any such X. Proof is complete.
Auto comment: topic has been updated by bhikkhu (previous revision, new revision, compare).
Auto comment: topic has been updated by bhikkhu (previous revision, new revision, compare).
One thing to notice in the question is that you have exactly 1 weight of each power (k from 0 to 100.) suppose we place w^(k+2) on the left side along with the weight X. Now to counter-balance this on the right side even if you take all lower powers (that is from w^0 to w^(k+1) it wont be enough to match w^(k+2) , (this comes by the GP summation formula), and definitely not w^(k+2)+X. so we have to take w^(k+3) on the right side. Now balancing left side will be a problem . How? Suppose you place all weights of all lower available powers on left pan (w^0 to w^(k+1)). Now as X<= w^k, further summation of all weights from i=0 to i=k-1 will be less than w^(k)(Again by GP summation). if to this we add X we have a currentsum< w^(k+1) , along with this we are still left with w^(k+1) and w^(k+2). to current sum if we add w^(k+1) new current sum will be less than w^(k+2),and we are left with w^(k+2) on adding this to current sum we can say that the final sum on left pan will be less than w^(k+3)(Similar argument as for w^(k+2)). So we will have to take assistance of w^(k+4) on left pan to counter right pan. You can notice by induction that it will be a never ending procedure and as limit of k is finite(100),if we don't arrive at a solution with powers<=k+1 , we will never arrive at the solution. Hope it helps. (Sorry it went that long) :).
What I have found is that, if there is a solution using wk + 2 or higher coins, then there will be a solution without using wk + 2 or higher coins. So, if i use the coin to arrive at a solution(if there is a solution using that coin), i could have not used the coin and arrived at the solution too.
It is not the case that you won't have solution using wk + 2 or higher coins.
I don't know if I am correct on this.
Auto comment: topic has been updated by bhikkhu (previous revision, new revision, compare).