arrays - Finding the number of unique positions occupied by every node after sequence of swaps

Question

You have N (N <= 50000) nodes on a line, with node i in position i on the line. You are given a sequence of M different swaps (M <= 20000), that is written in the from (a1, b1) (a2, b2) …. (aM, bM). In every unit of time i = 1…M, the nodes at positions ai and bi swap. Then, the same M swaps happen again in minutes M + 1….2M, and then for 2M + 1…3M, and so on, continuing a cyclic fashion for K units of time (K < 10^18).

So for example,

At unit of time 1, nodes at positions a1 and b1 swap.

At unit of time 2, nodes at positions a2 and b2 swap.

…

At unit of time M, nodes at positions aM and bM swap.

At unit of time M + 1, nodes at positions a1 and b1 swap.

At unit of time M + 2, nodes at positions a2 and b2 swap.

And so on…

For every node, you are asked to determine the number of unique positions that it will occupy.

Example:

6 nodes, M = 4 (sequence consists of 4 swaps), and K = 7 (total units of time is 7).

Sequence:

(1, 2) (2, 3) (3, 4) (4, 5)

Simulation:

Time 0: {1, 2, 3, 4, 5, 6}

Time 1: {2, 1, 3, 4, 5, 6}

Time 2: {2, 3, 1, 4, 5, 6}

Time 3: {2, 3, 4, 1, 5, 6}

Time 4: {2, 3, 4, 5, 1, 6}

Time 5: {3, 2, 4, 5, 1, 6}

Time 6: {3, 4, 2, 5, 1, 6}

Time 7: {3, 4, 5, 2, 1, 6}

Answer:

Node 1 reaches positions {1, 2, 3, 4, 5}, so 5 positions.

Node 2 reaches positions {1, 2, 3, 4}, so 4 positions.

Node 3 reaches positions {1, 2, 3}, so 3 positions.

Node 4 reaches positions {2, 3, 4}, so 3 positions.

Node 5 reaches positions {3, 4, 5}, so 3 positions.

Node 6 doesn’t move, so it reaches position {6}, so 1 position.

One way of solving this could be by treating the nodes as a graph. Then, you could treat each of the swaps as connections, and then use a graph algorithm to calculate how you move between the nodes.

How can I successfully incorporate a graph algorithm into this problem?

EDIT: I’ve spent a few more hours thinking about this problem, and wanted to incorporate Ehsan’s idea into the solution. To find the possible nodes that will be in each position, you can use a recursive function like the one Ehsan is proposing (F(F(...(F(original_order))). Then, you can do this for every step in K. However, this would be an NK solution, which my be too slow as the largest number of operations I can perform is 10^9. How can I optimize my current idea?

question from:https://stackoverflow.com/questions/65867561/finding-the-number-of-unique-positions-occupied-by-every-node-after-sequence-of

Answer 1

You doesn't need graph for this. They key point is reducing k

Lemma: assume from original node list {n1,n2,n3,...,nN} after series of step {s1,s2,.....,st} you reach to new order of nodes like {n_i1,...,n_iN} and also you have a unique visited list for each node as {n1_v1,...,n1_vn1},...,{nN_v1,...,nN_vnN}

then if you perform the same series of steps again, you can find the new order list of nodes and also unique visited list in O(n) with help of previous step. so it's kind of dynamic programing. by this approach the complexity of your algorithm could be as O(n*log(k/m)+m)