Ctrick bit can't understand
http://www.spoj.com/problems/CTRICK/ This is a problem on spoj It states that
The wizard shuffles the small stack of cards, holds it face down, and performs the following procedure:
-
The top card moves to the bottom of the package. The new top card is dealt facing the table. This is the ace of spades.
-
The two cards move one at a time from top to bottom. The next card is dealt facing the table. These are two peaks.
-
Three cards move one at a time ...
-
This continues until the n-th and last cards become pickets.
This impressive trick works if the wizard knows how to properly arrange the cards (and knows how to fake shuffle). Your program should determine the initial card order for a given number of cards, 1 ≤ n ≤ 20,000.
Input
The first line of input contains one positive integer indicating the number of test cases. Each case consists of one line containing an integer n. Output
For each test case, print a string with the correct permutation of values from 1 to n, shared space. First number showing the top card of the pack, etc ... Example
Input: 2
4
five
Output:
2 1 4 3
3 1 4 5 2
Now the only solution I can think of is using a queue and simulating the process. But it will be O (n ^ 2). I read the comments and they suggested using a BIT segment tree. I know both the segment tree and the BIT, but cannot figure out how to implement them in this question. Please suggest some way to do this. Thanx
source to share
I have no idea why this problem should be related to BIT or segment tree, but I solved the problem with a simple "O (N ^ 2)" simulation.
First, there is an 11s
and for this problem N == 20000
. This indicates that a solution O(kN)
might fix the problem. I believe you are thinking this one k
should be N
because it requires simple modeling but can be optimized somehow.
Let's see how we can build a sequence when 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
We can see a nice pattern: for round, i
we have to treat the space as a i
space, starting at the first place after the last position, and format if necessary.
The important step, however, is that after some rounds, the remaining spaces will be less counting space. In this case, we can take mod
to save time!
For example, in the fourth round of the previous example, we only have 2 spaces left, but 4 spaces to count. If you count 4, it's a waste of time. Counting 4 steps is equivalent to counting 4% 2 == 0 mileage, starting from first place after last position . You can check this item yourself :)
Therefore, we can simulate this process using the code:
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;
}
source to share
If you would like to use a Fenwick tree (BIT) to solve this problem, take a closer look at the solution posted by nevets, especially this part (thanks for the bride drawing):
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
Finding the correct free space using the above approach has O (N) time complexity because we need to go through all the spaces (total O (N ^ 2) complexity). Note that we can calculate the next position using:
free(next_pos) = (free(current_pos) + next_number) mod free(total) + 1
where free (x) tells us how many free slots are up to (including) the position. This is not a straightforward formula for next_pos, but it tells us what it needs to satisfy, so we can use this information for a binary search.
All that remains is to do the free space calculations, and this is where BIT comes into play as it gives us O (log N) time complexity for the query and for the update. The time complexity of finding the free space is now O (log ^ 2 N), and the total time complexity is O (N log ^ 2 N).
As for the speed of movement:
- 3.16s for the proposed nevets approach
- 1.18s using a queue to rotate items
- 0.60s using a linked list to rotate
- 0.02 using BIT.
I have to say that I was very surprised by the speed increase :-)
PS If you don't know how to use BIT, initialize by updating all values to +1. When marking a slot taken, just update it to -1 to make it.
source to share