The sweet program

hi

im new to programming!

my problem:

n children numbered 1 to n are sitting in a circle. starting at child 1, a sweet is passed. after m passes the child holding the sweet is eliminated. if child x gets eliminated he gives the sweet to child x+1 and leaves the ring. that does not count far a pass. the children in the circle close ranks and the game continues with the child who was sitting after the eliminated child,taking the sweet. assume m is constant for each elimination.
write a program that will determine which child would get the sweet in the end.

I'm totally confused please help!!!!!!
How would i go about solving such a problem?

regards
warren

Get a pencil and paper and work and through a few examples. You will then see the process in action and will be able to write out (in English or whatever your first language is, but not code) the sequence of actions to get from say 5 children to a winner. Now look at your sequence of actions to find the repetitions, if there are any these are your loops. Now think about which data structure allows items to be easily removed from it at any point.

Now you are ready to convert your sequence into code.

Quote:

---

Originally Posted by wdaniels

I'm totally confused please help!!!!!!
How would i go about solving such a problem?

---

If you're familiar with a data structure called a circular linked list it's very easy. The problem translates almost one-to-one on such a data structure.

You put all children (or rather their numbers) into the nodes of a circular linked list. You also introduce a pointer which always points at the node of the child holding the sweet.

Now the algorithm: Advance the sweet-pointer M nodes forward and then advance it one node further and remove the previous node. Repeated this until there's just one node left, the winner of the sweet.

Implementing a circular linked list is easy but you really only need to know how it works because then you can quite easily use an ordinary array as if it were a circular linked list. This has pros and cons. For example "advance the sweet pointer" can be done in just one arithmetic operation in the array case. On the other hand "remove the previous node" is more expensive than in the linked list case.

Note that if M >= N you will be doing (at least one but potentially many) full cycles around the circle of children. That's not necessary so "advance M nodes" should really read "advance M modulo N nodes".

In addition to my previous post:

Both the array and the linked list approaches lead to an O(N*N) algorithm. I was thinking maybe that could be improved.

In both approaches all N children must be considered so O(N) is a minimum. Then in the array approch to remove a child is an O(N) operation and the M advancement is O(1). In the linked list approch it's the other way around. Child removal is O(1) whereas M advancement is O(N) (it's really O(M) so if M is small it tends towards O(1) but if M is big it tends towards O(N) so that's the worst case).

The traditional way to strike an approximation between an array and a linked list is to use a deque. This would probably improve the actual complexity (for large N) but theoretically it would still be O(N*N).

So is there a way to get a better theoretical complexity? I think so. I think O(N * log N) is possible. The idea is to find a data structure where both child removal and M advancement are O(log N). This would give a total complexity of O (N * log N) (like for example a sort of N elements)

What would this data structure look like? It would be an array supported by a binary tree. I call it a Binary Tree Array because I think this idea may be novel. At least I haven't heard of it before.

To avoid confusing child as a participant in the game, with child as a child node in the binary tree, I'm going to call the former 'game participant' from now on.

The array holds the N game participant's identification numbers. When these are entered into the array the binary tree is built at the same time in an O(N) operation. The tree leaves hold the array indexes. In addition each tree node holds the number of children. A leaf is considered to have one child (the array index if you will).

A game participant is never actually removed from the array. Instead the corresponding tree leaf is set to have no children (instead of one). This is an O(log N) operation on the binary tree.

The M advancement doesn't take place on the array itself. Instead it takes place in the binary tree. To skip M game participants becomes a question of going up a binary tree from a leaf and then going down the tree again to a leaf M leaves away. This is also an O(log N) operation.

So the Binary Tree Array gives both O(log N) removals and O(log N) M advancements which together result in an overall O(N * log N) algorithm.

I've posted a reference to here in the Algorithms & Data Structures forum,

http://www.codeguru.com/forum/showthread.php?t=517099