algorithm - Ctrick BIT unable to understand

Question

http://www.spoj.com/problems/CTRICK/ It is a problem on spoj It states that

The magician shuffles a small pack of cards, holds it face down and performs the following procedure:

The top card is moved to the bottom of the pack. The new top card is dealt face up onto the table. It is the Ace of Spades.
Two cards are moved one at a time from the top to the bottom. The next card is dealt face up onto the table. It is the Two of Spades.
Three cards are moved one at a time…</p>
This goes on until the nth and last card turns out to be the n of Spades.

This impressive trick works if the magician knows how to arrange the cards beforehand (and knows how to give a false shuffle). Your program has to determine the initial order of the cards for a given number of cards, 1 ≤ n ≤ 20000.

Input

On the first line of the input is a single positive integer, telling the number of test cases to follow. Each case consists of one line containing the integer n. Output

For each test case, output a line with the correct permutation of the values 1 to n, space separated. The first number showing the top card of the pack, etc… Example

Input: 2

4

5

Output:

2 1 4 3

3 1 4 5 2

Now the only solution i can think of is to use a queue and simulate the process. But that would be O(n^2).I read the comments and they suggested using segment tree of BIT. I know both segment tree and BIT but am unable to understand how to implement them in this question.Please suggest some way to do this. Thanx

score 3 · Accepted Answer

我不知道为什么这个问题应该与 BIT 或段树联系起来，但我使用简单的“O(N^2)”模拟解决了这个问题。

首先这个问题的时间限制是11s和N == 20000。这表明O(kN)解决方案可能会通过问题。我相信您认为这k应该是N，因为简单的模拟需要这样做，但可以通过某种方式对其进行优化。

让我们看看当 N == 5 时如何构造序列：

Round 1, count 1 space starting from first space after last position:        _ 1 _ _ _
Round 2, count 2 spaces starting from first space after last position:       _ 1 _ _ 2
Round 3, count 3 spaces starting from first space after last position:       3 1 _ _ 2
Round 4, count 4 spaces starting from first space after last position:       3 1 4 _ 2
Round 5, count 5 spaces starting from first space after last position:       3 1 4 5 2

我们可以看到一个很好的模式：对于 round i，我们应该i从最后一个位置之后的第一个空格开始计算空格，并在必要时回退。

然而，关键的一步是：经过几轮之后，剩余的空间将小于要计算的空间。在这种情况下，我们可以采取一个mod节省时间！

例如，在上一个示例的第 4 轮中，我们只剩下 2 个空格，但要计算 4 个空格。如果我们数到 4，那就是浪费时间。计数 4 步相当于从最后一个位置后的第一个空格开始计数 4%2 == 0 个空格。您可以自己验证这一点:)

因此，我们可以使用代码来模拟这个过程：

memset(ans, 255, sizeof(ans));
while (cur <= n)
{
    int i, cnt;
    int left = n - cur + 1; // count how many spaces left
    left = cur % left + 1; // this line is critical, mod to save time!

    for (i = pos, cnt = 0; ; ++i) // simulate the process
    {
        if (i > n) i = 1;
        if (ans[i] == -1) ++cnt;
        if (cnt == left) break;
    }

    ans[i] = cur;
    pos = i;

    ++cur;
}

score 2 · Accepted Answer

如果您想使用 Fenwick 树（BIT）来解决这个问题，请仔细查看 nevets 发布的解决方案，特别是这部分（感谢绘图 nevets）：

Round 1, count 1 space  starting from first space after last position:       _ 1 _ _ _
Round 2, count 2 spaces starting from first space after last position:       _ 1 _ _ 2
Round 3, count 3 spaces starting from first space after last position:       3 1 _ _ 2
Round 4, count 4 spaces starting from first space after last position:       3 1 4 _ 2
Round 5, count 5 spaces starting from first space after last position:       3 1 4 5 2

使用上述方法找到正确的空闲空间的时间复杂度为 O(N)，因为我们必须遍历所有空间（总复杂度 O(N^2)）。请注意，我们可以使用以下方法计算下一个位置：

free(next_pos) = (free(current_pos) + next_number) mod free(total) + 1

其中 free(x) 告诉我们有多少空闲空间最多（包括）一个位置。这不是 next_pos 的直接公式，但它告诉我们它需要满足什么，因此我们可以使用这些信息对其进行二分查找。

剩下要做的唯一一件事就是进行可用空间计算，这就是 BIT 发挥作用的地方，因为它为我们提供了 O(log N) 的时间复杂度，用于查询和更新。现在找到空闲空间的时间复杂度为 O(log^2 N)，总时间复杂度为 O(N log^2 N)。

至于运行速度：

nevets 建议的方法为 3.16s
1.18s 使用队列旋转元素
0.60s 使用链表旋转
0.02s 使用 BIT。

我必须说我对速度的提升感到非常惊讶:-)

PS 如果您不确定如何使用 BIT，请通过将所有值更新 +1 来进行初始化。将插槽标记为已占用时，只需将其更新为 -1 即可。

algorithm - Ctrick BIT unable to understand

2 回答 2

Related

Reference