Tuenti Challenge 6: Bricks and Bridges write-up

Posted on 6/13/2016 by José María Pérez, Software Engineer

Hello again! I'm the author of problem 19, Bricks and Bridges (as well as of problems 6 and 15). Here is the write-up of this problem:
 

In this challenge, I tried to create a misleading problem in which things that seem easy are hard and things that seem hard are easy (in the end).

When you encounter the problem, the first thing you find is the requirement to go through all the nodes on the graph, and the fact that you have to bring down all of the bridges. In order to bring them down, you have to cross them, so instead of finding a hamiltonian path, you need to find a eulerian path (with some quirks).

So, for each level, it is possible to solve it if, and only if:

  • All nodes are connected
  • A eulerian path exists (there are a maximum of two odd-degree nodes)

How do you find out the degree of the nodes?

x[1] * STEPFORCE[1] + x[2] * STEPFORCE[2] + ... + x[n] * STEPFORCE[n] = BRIDGE_TOUGHNESS with x >= 0 and then BRIDGE_DEGREE = sum(x)
(It could be interesting to use some papers but dynamic programming is more than enough for this task).


We are only looking for a single even-sum solution and/or a single odd-sum solution (to see if the node degree could be odd and/or even).

There are 3 possible outcomes of this step for each bridge:

  • It has no solution (all solutions include a negative x or gcd(stepforces) does not divide its toughness): The level is impossible. For example, a bridge with toughness 3 which only has a stepforce of 2, or the same bridge with stepforces 5 and 2.
  • All solutions have an even OR odd BRIDGE_DEGREE. Add the corresponding degree to each node the bridge connects (it really only matters if it’s even or odd)
  • It has solutions with an even AND odd BRIDGE_DEGREE. (We’ll call this bridge a ‘BOTH bridge’).

Once you reach this point, you can try to solve the problem. To do this, you can check all possible combinations of oddness for each BOTH bridge, and just apply the eulerian path rule:

  • There are 2 nodes with an odd degree, the path goes from one of those to the other.
  • There are 0 nodes with an odd degree, the path goes from any node to itself.
  • There are more than 2 nodes with an odd degree, the path does not exist.

(Remember that it’s impossible to have an odd number of odd degree nodes, as, in this case, there would be a bridge going nowhere)

Unfortunately, there is a big problem with this solution. Its complexity is exponential for the number of BOTH bridges, as you need to check each possible oddness (even or odd): 2*2*2*2*…*2 = 2^(number of BOTH bridges).
Taking into account the sheer amount of BOTH bridges, this is not feasible. Thankfully, however, there is a shortcut:

Shortcut:

After processing the diophantine equations, you mark all the bridges in the graph with EVEN, ODD or BOTH tags regarding each diophantine solution. To solve the problem, you need to count the degree of each node and then count the nodes that have an odd degree (EVEN bridges add 0 to its connected nodes, ODD bridges add 1, and BOTH bridges add 0 or 1, whichever you want)

If you remove the EVEN and ODD bridges, you get a graph consisting of nodes with a partial degree connected by the remaining bridges (those with the BOTH tag; remember that there could be several connected subgraphs) and nodes with a fully calculated degree, which are not connected to any other node.

At this point, you have to minimize the count of odd degree nodes and check that there are no more than two of them (if there are more than 2 odd-degree fully calculated nodes, you can stop now, as the scenario cannot be solved).

In order to minimize the count of odd-degree nodes for all the partial-degree connected subgraphs, you just need to add each subgraph’s partial degrees together and check if this is EVEN or ODD for each of the subgraphs, which is O(n).
This is the proof for each connected subgraph:

Problem: Fully connected graph with nodes tagged with either 0 or 1, all arcs could add 0 or 1 to both ends, minimize the count of odd-degree nodes.
Solution: sum(degrees) % 2

Proof 1:

  • A 0-arc leaves both ends as they are
  • A 1-arc switches both ends (from 0 to 1 and from 1 to 0)
  • You can 'move' a 1-node around by fixing 1-arcs, and when it's directly connected to another 1-node, you can turn both of them to 0-nodes with a 1-arc
  • In this way, you can turn 1-nodes into 0-nodes by pairs

Proof 2:
You can fuse two nodes together by adding their degrees and removing all the bridges that connect them directly:

  • If both of them were 0, you would use a 0-arc, thus maintaining the number of 0-nodes
  • If both of them were 1, you would use a 1-arc, thus reducing the number of 1-nodes by 2
  • If one were 0 and the other were 1, you would use a 0-arc or a 1-arc, depending on where you would like the 1-node to be, but maintaining the number of 1-nodes

To answer your unspoken question, yes, I tried to place the problem in Alice in Wonderland’s world, but it felt too forced.

And so ends my contribution to this year’s Tuenti Challenge. I hope you liked it :)

Follow us