Just trying to solve the second part of a question with two parts. First part was to prove that you can't add decrement method to a standart binary counter without hurting the amortized complexity and change it to be more than O(1). This part i have done with no problems.
Solution in a nutshell - after some method you are going to be in a dead end when you have a number like this: 100...0 so when you decrease by 1 you will get 0111...1 and then when you will increase by 1 you will get again 100...0 and those decreasment and increament are cost n and you will do them m times so its not O(1) amortized.
The second part, is to tell how you can change the structure such that it will support decreament and increase methods and the amortized complexity will stay O(1). I never saw something like this and it really confusing me what they want me to do. Their solution is that anytime you want to change 0 to 1 you change it to minus 1. Problem is, i can't understand what they meant, i mean, on which stracture you are inserting this change and how does it improved the complexity (if you change to -1 you stil going to the same dead end).