StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
11384510
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
2
CommunityOwnedDate
CreationDate
2012-07-08T15:55:02.337
FavoriteCount
0
LastActivityDate
2012-07-12T22:19:10.227
LastEditDate
2012-07-12T22:19:10.227
LastEditorUserId
1190354
OwnerUserId
1190354
ParentId
11382189
PostTypeId
2
Score
13
ViewCount
0
LastEditorDisplayName
text
Body
The question is essentially asking us to count permutations of <code>1 2 ... N</code> such that <code>i</code> and <code>i+1</code> are not adjacent for <code>1 <= i <= N-1</code>. Additionally, we have a prefix constraint. We should count only those permutations which start with <code>pos_1 pos_2 ... pos_k</code>. If it were not for the prefix constraint, you can find the answer in O(N) time using the formula from <a href="http://oeis.org/A002464" rel="noreferrer">OEIS</a>. That is if <code>N</code> is not too large. The number of digits in the answer grows as Θ(N log N), so multiplication and addition would incur additional overhead. Or you could compute the answer modulo some number. This question was asked in the <a href="http://www.spoj.pl/problems/FLWRS/" rel="noreferrer">Egyptian Olympiad in Informatics (2009)</a>. With the prefix constraint, I have an O(N2) dynamic programming solution. However, since N is as small as 16, using a polynomial time algorithm is overkill. There exists an easier dynamic programming solution running in time O(2NN2). Although this algorithm would probably take longer to code than the previous solution, its much faster to think of. The backtracking solution would, however, take somewhere between 20 to 100 hours (on an ordinary desktop/laptop) to run in the worst case. There are <code>2806878055610</code> solutions alone to visit for N = <code>16</code>. In addition to that, there would probably be a heavy cost of visiting non-solution dead-ends. <h2>O(2NN2) Solution</h2> This solution can be generalized to finding the number of Hamiltonian paths in a graph. Our state would be a pair <code>(S, i)</code>; where <code>S</code> is a subset of <code>{1,2...N}</code> and <code>i</code> is an element of <code>S</code>. Let the cardinality of <code>S</code> be <code>M</code>. Define <code>F(S,i)</code> to be the number of ways to place the the elements <code>1, 2, ..., M</code> in the positions specified in <code>S</code>; respecting the constraint that <code>k</code> and <code>k+1</code> never appear together; and the element <code>M</code> being placed in position <code>i</code>. The base case is <code>F(P,pos_k) = 1</code> where <code>P = {pos_1, pos_2 ... pos_k}.</code> It is straightforward to compute <code>F(S,i)</code> for all <code>S</code> and <code>i</code> in time O(2NN2). The final answer is <code>F([N],1) + F([N],2) + ... + F([N],N)</code> where <code>[N] = {1,2...N}</code>. C++ code follows. <a href="http://en.wikipedia.org/wiki/Mask_%28computing%29" rel="noreferrer">Bitmasks</a> were used to represent subsets of <code>{1,2...N}</code>. <pre><code>const int MAXN = 18; long long DP[1 << MAXN][MAXN]; void solve() { int n, k; cin >> n >> k; int pmask = 0, p; for(int i = 0; i < k; i++){ cin >> p; pmask |= (1<<p); } // base cases if(k > 0) { DP[pmask][p] = 1; } else { for(int i = 0; i < n; i++) DP[1<<i][i] = 1; } long long ans = 0; for(int bitmask = pmask; bitmask < (1<<n); bitmask++) { for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if((bitmask & (1<<j)) or abs(i-j) == 1) continue; DP[bitmask | (1<<j)][j] += DP[bitmask][i]; } if(bitmask == ((1<<n) - 1)) ans += DP[bitmask][i]; } } cout << ans << endl; } </code></pre> <h2>O(N2) Solution</h2> This solution is pretty difficult to think of if you have not come across the idea before. First, let's tackle the problem without the prefixes. The idea is to 'build' all valid permutations by placing the elements 1, 2 .. N one by one. Let's start with an illustration. Suppose we are building a permutation, of say, 1 2 .. 5. First, we place 1. After placing 1, we also insert a placeholder element to be filled in by later numbers. More precisely, each state is a class of permutations where the placeholder <code>x</code> is replaced by a non-empty sequence of elements. Our permutation, after inserting 1, looks like one of the 3 cases: <ul> <li><code>1 x</code> - 1 is the first element. The placeholder <code>x</code> would contain all the elements 2,3,4,5 in some order.</li> <li><code>x 1</code> - 1 is the last element. </li> <li><code>x 1 x</code> - 1 is neither the first element or last element.</li> </ul> Next, we place 2. It has to belong to one of the placeholders in one of the previous 3 classes. <ul> <li>Suppose it belongs to the only placeholder in <code>1 x</code>. Since 2 cannot be adjacent to 1, after placing 2 we must insert another placeholder between them. This results in the state <code>1 x 2</code>. Additionally, we need to account for the permutations when 2 isn't the last element. We also spawn a state <code>1 x 2 x</code>.</li> <li>For <code>x 1</code>, we analogously create states <code>2 x 1</code> and <code>x 2 x 1</code>.</li> <li>For <code>x 1 x</code>, we have two choices of placeholders to place 2 in. Like the previous cases, we create states <code>2 x 1 x</code>, <code>x 2 x 1 x</code>, <code>x 1 x 2</code>, <code>x 1 x 2 x</code>. But notice, for example, in <code>x 2 x 1 x</code> the last placeholder is different from the other two - in that 3 can occur in it without a need to create another barrier! We record this by using a different symbol for the placeholder. That is we use <code>x 2 x 1 o</code> and <code>o 1 x 2 x</code> states instead.</li> </ul> Suppose next, we are inserting 3 in <code>x 2 x 1 o</code>. If we place 3 in an <code>x</code>, like before, we have to create a barrier placeholder. But, we do have a choice between creating or omitting a placeholder in the direction opposite to the barrier placeholder. If we place 3 in an <code>o</code> placeholder, we have choices between creating or omitting placeholders in both directions. Additionally, we must also 'promote' the <code>x</code> placeholders that are not used to <code>o</code> placeholders. This is because, the old <code>x</code> placeholders do not offer a constraint for the next element, 4, like they did for 3. We can already start guessing the developing pattern. In the general case, while inserting i: <ul> <li>First of all, we have to choose in which placeholder to place i. </li> <li>Next, suppose we place i in an <code>x</code> placeholder. We must build a barrier placeholder. And we have a choice whether to build a placeholder in the other direction.</li> <li>If we are using an <code>o</code> placeholder, we have choices to build additional placeholders in both directions. That is, a total of 4 choices.</li> <li>We must update the <code>x</code> placeholders we did not use, to <code>o</code> placeholders.</li> </ul> The final observation that turns this idea into an efficient algorithm is that we can bunch together permutation classes that have the same number of placed elements and the same number of <code>x</code> and <code>o</code> placeholders. This is because, for two different classes sharing all three of these parameters, the number of permutations they represent are equal. To prove this claim rigorously, it is enough to observe that the classes we are enumerating are exhaustive and non-overlapping. <h3>Prefixes</h3> A little thought reveals that in the prefix problem, we just have to count permutations which begin with a certain element, (call this b); and some of the constraints between <code>i</code> and <code>i+1</code> are not applicable anymore. The second modification is easy to fix: If the constraint between i-1 and i are not applicable, then before inserting i, update all the <code>x</code> placeholders to <code>o</code> placeholders. For the first modification, we should ensure that there is always a placeholder at the beginning until <code>b</code> is placed. While placing <code>b</code> we cheerfully place it into the beginning placeholder, and don't add any placeholder before it. <h3>Implementation</h3> Let <code>DP[i][no][nx]</code> be the number of ways to build the class where the first <code>i</code> elements have been placed, and there are <code>no</code> and <code>nx</code> placeholders of type <code>o</code> and <code>x</code> respectively. At any state, the number of <code>x</code> placeholders is between 0 and 2. So the state space is O(N^2). State transitions are constant time, exactly as described above. <h2>O(N) solution for the problem without the prefix constraint</h2> According to OEIS, An = (n+1)An-1 - (n-2)An-2 - (n-5)An-3 + (n-3)An-4; where An is the number of permutations where <code>i</code> and <code>i+1</code> are never consecutive. We can compute the sequence An in O(n). (That is, assuming we compute An modulo a reasonably small number.) Here is a derivation of the formula: Define auxiliary sequences: <ul> <li>Bn = Number of permutations of <code>1 2 ... N</code> such that exactly one of the <code>N-1</code> adjacency constraint is violated.</li> <li>Cn = Number of permutations of <code>1 2 ... N</code> such that only the adjacency constraint involving the element <code>N</code> is violated. That is <code>N-1</code> and <code>N</code> would be adjacent to each other in these permutation; and all other adjacency constraints are satisfied.</li> </ul> We now look for recurrences for the sequences A, B and C. Recurrence for An Suppose we remove the element <code>n</code> from a valid permutation <code>P</code>, where <code>i</code> and <code>i+1</code> are never adjacent. The resulting permutation <code>Q</code> of <code>1 .. n-1</code> must satisfy exactly one of the following two cases: <ul> <li>No adjacent numbers from <code>1 ... n-1</code> are adjacent in <code>Q</code>. That is, <code>Q</code> is one of the permutations accounted for in An-1. </li> <li>Exactly one pair <code>(i,i+1)</code> appear consecutively in <code>Q</code>, and <code>i+1 =/= n-1</code>. That is, <code>Q</code> is a permutation from Bn-1 - Cn-1.</li> </ul> In the first case, element <code>n</code> can be inserted in exactly <code>n - 2</code> positions. Two of the positions are blocked by the element <code>n - 1</code>. In the second case, there is only one choice for the position of <code>n</code> - between the consecutive elements. We get the recurrence: An = (n - 2)An-1 + Bn-1 - Cn-1. Recurrence for Bn Let Bn,k be the number of permutations where <code>k</code> and <code>k+1</code> occur consecutively. We can coalesce <code>k</code> and <code>k+1</code> together to a single element, and consider a permutation <code>Q</code> of <code>n-1</code> elements, preserving the relative ordering. <ul> <li>If neither <code>k-1</code> and <code>k+2</code> (original labels) appear next to the coalesced <code>(k,k+1)</code> element, then <code>Q</code> contributes <code>2</code> permutations to Bn,k - they correspond to the arrangements <code>k k+1</code> and <code>k+1 k</code> within the coalesced element. The number of such <code>Q</code> is An-1.</li> <li>If one of <code>k-1</code> or <code>k+2</code> appear next to the <code>(k,k+1)</code> element, then <code>Q</code> contributes <code>1</code> permutation. The number of such <code>Q</code> is Bn-1,k-1 + Bn-1,k.</li> <li>If both <code>k-1</code> and <code>k+2</code> appear next to the <code>(k,k+1)</code> element, then <code>Q</code> contributes <code>1</code> permutation. The number of such <code>Q</code> is Bn-2,k-1.</li> </ul> We have Bn,k = 2An-1 + Bn-1,k-1 + Bn-1,k + Bn-2,k-1. (Some terms vanish when <code>k = 1 and k = n-1</code>). Summing over <code>k</code>, we get the recurrence: Bn = 2(n-1)An-1 + 2Bn-1 + Bn-2. Recurrence for Cn Well, Cn is just Bn,n-1. From the previous results, it follows that Cn = 2An-1 + Cn-1. Putting it all together We should be able to eliminate B and C to get a recurrence in A alone. It is left as an exercise. :-)
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. PONumber of ways to place kings on chess board
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USbloops
UserOwnerUserId
1. USbloops
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. PONumber of ways to place kings on chess board
 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
 VTUndeletion
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. COCan you explain me how he got to this formulae a(n) = (n+1)*a(n-1)-(n-2)*a(n-2)-(n-5)*a(n-3)+(n-3)*a(n-4) in the link https://oeis.org/A002464
 singulars
 PostPostId
 PO
 UserUserId
 USRakesh12
2. CO@Rakesh Answer updated.
 singulars
 PostPostId
 PO
 UserUserId
 USbloops

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.