StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
14464764
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
1
CommunityOwnedDate
CreationDate
2013-01-22T17:42:04.047
FavoriteCount
0
LastActivityDate
2013-01-22T17:42:04.047
LastEditDate
LastEditorUserId
0
OwnerUserId
2001049
ParentId
14462401
PostTypeId
2
Score
5
ViewCount
0
LastEditorDisplayName
text
Body
<ol> <li>Yes it can.</li> <li>You can see the description of the data structure below, here I'll just hint how to use it in the given problem. The population we're representing is obviously the circle of stones. We start with all of the N stones being alive, and at each step kill the appropriate stone in our tree. Only need to know which element we're currently at (I think it's appropriate to call it m). The high-level algorithm (I leave the details to you) is as follows (P is our data structure): <pre><code>While P.size > 1: P.toggle(m) // remove the m-th stone m = P.kth(next stone to be killed) </code></pre> P.size in the code above is simply the number of all remaining stones. In the description below, it corresponds to tree[1]. Note: The symbol k used in the data structure is different from the one in the problem input that represents jump distance.</li> <li>Pretty much. I haven't seen that name before, but the code looks the same as what I've seen people call a population tree. The population tree is a simple way to use the segment tree. You have N elements each having two possible states: 1 for alive and 0 for dead. The tree supports two operations: <ul> <li>Toggle the state of element numbered i.</li> <li>Return the index of the k-th (in size of its index) living element. </li> </ul> To clarify the second operation let's say that the set of living elements is {1, 2, 4, 7}. If N = 8, that corresponds to the state array 01101001 (element 0 is dead, element 1 is alive, element 3 is alive, and so on). So, how to implement this? As usual, leafs of the tree correspond to the array. That is, the i-th leaf has value 1 if the i-th element is alive, and 0 otherwise. Each internal node remembers the sum of the values of its children. To toggle the state of an element, we toggle the value of the corresponding leaf, and then fix on the path from that leaf to the root: <pre><code>const int size = 1 << 18; // 2^17 elements, the rest are internal nodes int tree[size]; // number of living elements in the subtree of a node void toggle(int i) { tree[i + size / 2] ^= 1; // toggle the leaf for (i /= 2; i > 0; i /= 2) tree[i] = tree[2 * i] + tree[2 * i + 1]; } </code></pre> Note: a common way of labeling nodes is to have the root equal to 1, and recursively, the children of a node n are 2n and 2n+1. To find the k-th living element we can think recursively: We're currently at node n, and are looking for the k-th living element its subtree (the subtree of a node is the tree rooted at that node). If n's left child 2n has k or more living elements, set n = 2n. Otherwise, we'll obviously go to the right child, that is set n = 2n+1. In that case, we're no longer looking for the k-th living element of the subtree. Because we skipped all the living elements of the left child, we subtract that count from k. Here we're looking at the living elements 1-based, for simplicity. The basic thinking here might be recursive, but the description hints that doing it iteratively should also be quite simple: <pre><code>int kth(int k) { ++k; // because this method looks at elements 1-based int current_node = 1; // start at the root while (current_node < size / 2) { if (tree[2 * current_node] >= k) current_node = 2 * current_node; // descend into the left child else { k -= tree[2 * current_node]; // fix k current_node = 2 * current_node + 1; // descend into the right child } } } </code></pre> These two functions are what makes that segment tree a population tree.</li> </ol> This was a data structure question, so the described idea uses a data structure. However, I'd like to mention that the problem is known as the Josephus problem, and has alternative solutions, so you might be interested in looking it up.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POUVA - 1394 : And There Was One Algorithm
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USgus
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POUVA - 1394 : And There Was One Algorithm
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. COi had somewhat formed this idea ( finding next element is in left or right child and then recursing) but it was cloudy...and thnx A LOT for the referrance to josephus problem...i would have given a +2 if possible...
 singulars
 PostPostId
 PO
 UserUserId
 USjemmanuel

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.