4

Probably incorrect example in problem 279 Two Buckets Advanced

 2 years ago
source link: https://www.codeabbey.com/index/forum_topic/e97886dc33aa1e224e3b6e6911412add
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Probably incorrect example in problem 279 Two Buckets Advanced

Back to General discussions forum

Alexandr Milovantsev     2022-05-19 08:07:00

For the third dataset of provided example my code returns a different solution. My code returns 1200284759738 and in the example there 1200284759740 is given. Because my code is quite straitforward, I can not figure out why it fails on the 1 dataset of 8 datasets processed, including sets from the simple version of this problem. Could somebody check what value gives their code on that dataset? I suspect that there could be an error in example creeped in.

CSFPython     2022-05-20 11:21:58

I have only just spotted this thread and wanted to add some comments.

First I would like to explain why I prefer to comment in a public rather than a private thread. I quite agree that we don't want to tell others how to solve a problem in a public thread. However, I think that certain elements of problem discussion should be perfectly acceptable in a public thread. I think that most of us are capable of judging what is reasonable and what is not. Comments in a public thread are likely to give other users the interest and encouragement to tackle problems that they would not otherwise have attempted. My comments on this problem (see below) are deliberately designed to be readily understood by those who have already solved it (because they will almost certainly have had similar thoughts themselves). For someone who has not given any thought to the problem my comments will make little sense and be of no real use. For someone who is prepared to put in the necessary effort to understand the problem these comments might be sufficient encouragement for them to explore the ideas behind the problem in order to discover for themselves what is going on. If this leads to them solving the problem then we have achieved a successful (and well-deserved) solution which might not otherwise have happened.

My comments which are relevant to the initial ideas in the thread are as follows:

There are two repetitive sequences of moves in this problem. Following either of them results in a cycle of positions which eventually returns to the starting point. Following the other repetitive sequence simply follows the same cycle but in reverse order. The cycle contains every possible target value so these can be reached by going around the cycle in either direction. Clearly one of these directions will be shorter than the other for a particular target. The "special cases" referred to by Mathias are reasonably common. They come about because some target values can be achieved in either bucket while others can be achieved in only the larger bucket. If we follow the cycle in one direction we find that, for a target value that fits into both buckets, we hit this target value 4 times in a consecutive sequence of 4 moves. It occurs first on two moves in the larger bucket. This is followed by two moves where the target is in the smaller bucket. When we consider targets which cannot fit into the smaller bucket we clearly cannot see the same group of 4 moves containing the target value. Only the first 2 of these, with the target in the larger bucket, occur. When following the cycle in this direction we hit the target in the larger bucket first so the location of the first hit is in the same relative position for all targets.

When following the cycle in the opposite direction we have a difference, determined by whether or not the target will fit into the smaller bucket. If the target does fit into the smaller bucket we will first hit it in that bucket. The next move sees the target again in the smaller bucket. After that we have two moves with the target in the larger bucket. For targets which do not fit into the smaller bucket we will first hit the target in the larger bucket. This is two moves further into the cycle than the position where we would expect to meet a smaller target. It is this difference of two moves which causes the apparent discrepancy. The fact that it applies only to one of the two directions of travel around the cycle has probably added to the potential for confusion.

I see that Alexandr has now added a private thread on this topic. As I have not yet submitted a solution to the problem I am not able to check what has been posted. If I have just repeated what is already there then I apologise to those who have already solved the problem. However, for those who are yet to solve it, I hope that these ideas are sufficient encouragement for you to explore it for yourself in greater detail.


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK