can anybody help me with this one?
http://www.oi.edu.pl/php/show.php?ac=e1 ... a/oi12/dwu
thanks in advance,
another polish problem
Moderator: Board moderators
another polish problem
I'm trying to solve another polish oi problem and I cannot find any solution
can anybody help me with this one?
http://www.oi.edu.pl/php/show.php?ac=e1 ... a/oi12/dwu
thanks in advance,
can anybody help me with this one?
http://www.oi.edu.pl/php/show.php?ac=e1 ... a/oi12/dwu
thanks in advance,
I think this problem can be reduced to coloring a graph with two colors.
Here's my idea.
First, divide the pairs of soldiers into groups, such that if you decide to swap one
pair in a group, you'll have to swap all its pairs eventually.
Two pairs of soldiers, (a,b), (c,d), are in the same group if a=d or b=c.
(Also, note that there can be at most two soldiers with the same height, otherwise, it's impossible to rearrange the soldiers.)
In the problem's example, the groups are:
A={(2,1)}, B={(5,6)}, C={(5,8)}, D={(2,4),(4,3),(3,1)}, E={(7,6)}, F={(7,9),(9,8)}.
These groups are the vertices of the graph you'll have to color. Also, define
the "cost" of a group to be the number of pairs of soldiers in it.
Next, two groups, U and V, are joined by an edge in the graph, if you have to
swap all pairs in one of them to properly set up the soldiers.
Or, more formally, if for some pair (a,b) in U, there exists (a,c) or (c,b) in V.
In the above example, the edges are: {A,D}, {B,C}, {E,F}, {B,E}, {C,F}.
Finally, you need to color this graph with two colors in such a way, that no
two adjacent vertices get the same color.
Define the cost of a coloring to be the sum of costs of all vertices colored in one color (e.g. black).
Then the minimum number of swaps is just the minimum possible cost of coloring (you'll need to swap all pairs in the groups colored black.)
You can find this coloring by doing a DFS on each connected component of the graph.
In the example, the minimum-cost coloring is to color {A,C,E} in black with
the cost |A| + |C| + |E| = 3; it corresponds to swapping the pairs (2,1), (5,8) and (7,6).
That's it. I hope the above algorithm will solve your problem. Feel free to ask any questions.
Here's my idea.
First, divide the pairs of soldiers into groups, such that if you decide to swap one
pair in a group, you'll have to swap all its pairs eventually.
Two pairs of soldiers, (a,b), (c,d), are in the same group if a=d or b=c.
(Also, note that there can be at most two soldiers with the same height, otherwise, it's impossible to rearrange the soldiers.)
In the problem's example, the groups are:
A={(2,1)}, B={(5,6)}, C={(5,8)}, D={(2,4),(4,3),(3,1)}, E={(7,6)}, F={(7,9),(9,8)}.
These groups are the vertices of the graph you'll have to color. Also, define
the "cost" of a group to be the number of pairs of soldiers in it.
Next, two groups, U and V, are joined by an edge in the graph, if you have to
swap all pairs in one of them to properly set up the soldiers.
Or, more formally, if for some pair (a,b) in U, there exists (a,c) or (c,b) in V.
In the above example, the edges are: {A,D}, {B,C}, {E,F}, {B,E}, {C,F}.
Finally, you need to color this graph with two colors in such a way, that no
two adjacent vertices get the same color.
Define the cost of a coloring to be the sum of costs of all vertices colored in one color (e.g. black).
Then the minimum number of swaps is just the minimum possible cost of coloring (you'll need to swap all pairs in the groups colored black.)
You can find this coloring by doing a DFS on each connected component of the graph.
In the example, the minimum-cost coloring is to color {A,C,E} in black with
the cost |A| + |C| + |E| = 3; it corresponds to swapping the pairs (2,1), (5,8) and (7,6).
That's it. I hope the above algorithm will solve your problem. Feel free to ask any questions.
