Tags: directed-graphs, hamiltonian paths..
Today, I will talk about a problem from Atcoder.
You are given 2 arrays A,B. You need to tell the minimum no of moves to convert A into B. In each move, you replace any A[i] by the xor of all elements in A. If its not possible to convert A to B, print -1.
Let us use 1-based indexing.
Now, place xor(A) at position 0. Then the move is basically swapping numbers at position 0 and some arbitrary position i.
So answer will only exist if both multisets of A, B (after including the xor of whole array) are same.
You can refer to editorial given at AtCoder, but I find my approach a bit easier to understand, though they are more or less the same thing.
So, in each move we swap a number $x$ at position $0$ with a number $y$ at position $i$.
Let this be represented by a directed edge from $x$ to $y$. Then, in next move, we will swap $y$ with some $z$, then $z$ with blabla... and finally swap some blabla with $b[0]$.
Isn't this a Hamiltonian Path from $a[0]$ to $b[0]$?
Note that a directed edge from $x$ to $y$ means that the correct position of $x$ is actually the position of $y$ in $A$.
$x→y$ means $x$ is at 0 position, and we place it at position of $y$, and bring $y$ to position $0$.
So an edge represents putting $x$ into its correct position, and then bringing $y$ to position $0$ so that we can place it in its correct position, and so on.
Consider an example,
A: [1, 3, 2]
B: [2, 1, 3]
Now using the available move option of swapping any element with first element, we need to transform array $A$ into $B$.
We perform 1→3 , $A$: [3,1,2]
We perform 3→2, $A$: [2,1,3]
You can see that the set of collection of edges denoting our operations are same as the set of collection of edges {b[i]→a[i] , 0 $\le i \le n$}
This is because for given $a[0]$, and let its position in $B$ be $i$, then we basically swap the numbers at position $0$ and $i$. Thus, the edge $a[0]→a[i]$ is exactly represented by $b[i]→a[i]$.
Now, $B$ is nothing but a permutation of $A$, and our edges are $b[i]→a[i]$. This is a standard thing that we often see in the world of competitive programming. The resultant graph is basically a forest of cycles.
Now since we want a hamiltonian path from $a[0]$ to $b[0]$, we obviously need connectivity. For all cycles that aren't a part of $a[0]$ we will have to break down and re-edit their edges a little bit so that those cycles will also contain $a[0]$ as an element in it.
If you didn't understand what I said above, try converting [1,3,2,7,8,9] to [2,1,3,9,7,8] by using move operation of swapping elements at position 0 and some arbitrary position $i$.
In terms of math, let $C$ be a cycle that doesn't yet have $a[0]$ as a member in it. (For eg: in above example, $7→8→9→7$ is a cycle that doesn't include a[0] i.e 1). Pick two consecutive edges from $C$, $x→y$ and $y→z$.
This means that when $x$ comes at pos $0$, we put it at position of $y$,
and then put $y$ at position of $z$.
Now see what happens when we swap $a[0]$ with $y$. Now $y$ comes at position $0$, and its destination position is still the position of $z$.
But destination position of $x$ is now the position of $a[0]$ after swap as it took the place of $y$.
And finally $a[0]$ has to come back to position $0$ , so destination position of $a[0]$ now becomes position of $y$.
So the new edges are $x→a[0]$, $a[0]→y$ and $y→z$. So $a[0]$ is successfully inserted into the cycle $C$ at the cost of one additional edge.
NOTE:
Bringing $a[0]$ into the cycle was necessary because our move operation allows us to swap any number with the number at position $0$. So once we get $a[0]$, we can apply the operation again and again i.e traverse the edges until the cycle is completed and all numbers are placed at their correct position.
I hope this opens up your mind a bit. You now have the tools needed. I will recommend you to play around with it, consider a few examples, make the graphs, see how things are functioning.
Finally here is the AC code.
Today, I will talk about a problem from Atcoder.
You are given 2 arrays A,B. You need to tell the minimum no of moves to convert A into B. In each move, you replace any A[i] by the xor of all elements in A. If its not possible to convert A to B, print -1.
Let us use 1-based indexing.
Now, place xor(A) at position 0. Then the move is basically swapping numbers at position 0 and some arbitrary position i.
So answer will only exist if both multisets of A, B (after including the xor of whole array) are same.
You can refer to editorial given at AtCoder, but I find my approach a bit easier to understand, though they are more or less the same thing.
So, in each move we swap a number $x$ at position $0$ with a number $y$ at position $i$.
Let this be represented by a directed edge from $x$ to $y$. Then, in next move, we will swap $y$ with some $z$, then $z$ with blabla... and finally swap some blabla with $b[0]$.
Isn't this a Hamiltonian Path from $a[0]$ to $b[0]$?
Note that a directed edge from $x$ to $y$ means that the correct position of $x$ is actually the position of $y$ in $A$.
$x→y$ means $x$ is at 0 position, and we place it at position of $y$, and bring $y$ to position $0$.
So an edge represents putting $x$ into its correct position, and then bringing $y$ to position $0$ so that we can place it in its correct position, and so on.
Consider an example,
A: [1, 3, 2]
B: [2, 1, 3]
Now using the available move option of swapping any element with first element, we need to transform array $A$ into $B$.
We perform 1→3 , $A$: [3,1,2]
We perform 3→2, $A$: [2,1,3]
You can see that the set of collection of edges denoting our operations are same as the set of collection of edges {b[i]→a[i] , 0 $\le i \le n$}
This is because for given $a[0]$, and let its position in $B$ be $i$, then we basically swap the numbers at position $0$ and $i$. Thus, the edge $a[0]→a[i]$ is exactly represented by $b[i]→a[i]$.
Now, $B$ is nothing but a permutation of $A$, and our edges are $b[i]→a[i]$. This is a standard thing that we often see in the world of competitive programming. The resultant graph is basically a forest of cycles.
Now since we want a hamiltonian path from $a[0]$ to $b[0]$, we obviously need connectivity. For all cycles that aren't a part of $a[0]$ we will have to break down and re-edit their edges a little bit so that those cycles will also contain $a[0]$ as an element in it.
If you didn't understand what I said above, try converting [1,3,2,7,8,9] to [2,1,3,9,7,8] by using move operation of swapping elements at position 0 and some arbitrary position $i$.
In terms of math, let $C$ be a cycle that doesn't yet have $a[0]$ as a member in it. (For eg: in above example, $7→8→9→7$ is a cycle that doesn't include a[0] i.e 1). Pick two consecutive edges from $C$, $x→y$ and $y→z$.
This means that when $x$ comes at pos $0$, we put it at position of $y$,
and then put $y$ at position of $z$.
Now see what happens when we swap $a[0]$ with $y$. Now $y$ comes at position $0$, and its destination position is still the position of $z$.
But destination position of $x$ is now the position of $a[0]$ after swap as it took the place of $y$.
And finally $a[0]$ has to come back to position $0$ , so destination position of $a[0]$ now becomes position of $y$.
So the new edges are $x→a[0]$, $a[0]→y$ and $y→z$. So $a[0]$ is successfully inserted into the cycle $C$ at the cost of one additional edge.
NOTE:
Bringing $a[0]$ into the cycle was necessary because our move operation allows us to swap any number with the number at position $0$. So once we get $a[0]$, we can apply the operation again and again i.e traverse the edges until the cycle is completed and all numbers are placed at their correct position.
I hope this opens up your mind a bit. You now have the tools needed. I will recommend you to play around with it, consider a few examples, make the graphs, see how things are functioning.
Finally here is the AC code.
No comments:
Post a Comment