Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

This is a problem from an algorithmic competition from a few years back. It has a very simple description, but I don't see any algorithm to solve it efficiently. I am not looking for an implementation, but a general idea how to solve this problem.

Description: We would like to build a domino chain from all tiles we are given (as in domino two tiles can be joined iff the same number appears on its adjacent sides). This isn't always possible. Therefore we should output the minimum number of tiles it is necessary to add to build the chain.

Input: n pairs of integers in the range [0, 10000] n <= 1000000 (so the algorithm can be O(nlogn) at worst)

Output: How many tiles (at least) should be added.

Example: Input:

2 1  
2 3  
4 5  

Output:

1

Explanation: (1 2) (2 3) ! (4 5) It's impossible to build the chain without adding any tiles. Adding one tile ((3 4)) where "!" stands creates a correct chain containing all tiles, therefore the answer is 1.

share|improve this question
2  
We like questions to show research - what have you tried, what didn't work? Have a look at the faq for hints about how to ask better questions. –  Joris Timmermans May 14 '13 at 8:05
add comment

closed as not a real question by Joris Timmermans, gnat, Bart van Ingen Schenau, Walter, Jalayn May 14 '13 at 12:59

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

up vote 1 down vote accepted

I believe that this is a variant to the eulerian path problem

each number is a vertex and each tile is an edge connecting the two numbers

if the entire graph is not connected then add tiles until they are (connect odd used numbers to other odd used number if possible)

is there are no or exactly 2 numbers that are used an odd number of times then the result is 0

is there are more than 2 numbers used an odd number of times then the result is k/2-1 with k the amount of numbers used an odd amount of times (plus the amount of tiles added to connect the entire graph)

the complexity comes down to the connectivity check plus the O(n) count of how many times each number is used

share|improve this answer
add comment

There is more to the problem than "just the algorithm". You need to think in data structures as well. In this case you have two kinds of structures:

  • Domino tiles - Two integers
  • Domino chains - A list of tiles that are connected to each other

Once you figure out how to build the structures you can go over the actual algorithm. Which you can simply do by dividing the problem to manageable bits.

  • First try to figure out how to add tiles to chains, you can add it to the start or the end of the chain.
  • Then figure out what to do when the tile does not fit to the chain, should a new chain be added? What does that imply?
  • When all the tiles have been added to chains can we add the chains together
  • etc.

Hope this helps.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.