Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I recently played an online card game in which the cards were spread on the table. The goal was for me to pick up as many as possible, subject to the following rule:

After picking up the first card, every subsequent card had to be 1 higher or 1 lower than the previous pick. So if the cards were three 1s, three 2s and three 3s, I could go 1→2→3→2→1→2→3, but then I wouldn't be able to pick up the last 1 and 3.

I generalized this to a multiset of natural numbers, from which I generated a graph with an edge between i and j if |i-j|=1. This is of course NP-Easy by reduction to the longest path problem; but is it hard?

share|improve this question
add comment

1 Answer 1

It's easy; there's a dynamic program. NP-hard problems often become easy on trees (more generally, graphs of bounded treewidth).

Suppose that we have two valid games for the same set of cards. Suppose further that, for some number x, both games have the same number of moves x→x-1 and the same number of moves x-1→x, and either both start on numbers ≥x or both start on numbers ≤x-1. We can splice these two games by taking the moves ≤x-1 from the first game and the moves ≥x from the second. This means that, given our assumptions about the games, the moves ≤x-1 and the moves ≥x each have optimal substructure, which is the prerequisite for DP.

More generally, a DP subproblem is specified by a range of card numbers, together with counts for how many times the range is exited and entered on each end, and whether the first card is internal to the range. Two solutions to disjoint but contiguous subproblems can be combined if and only if they agree on the choice of the first card and number of entries and exits for the boundary between them. The subproblems are polynomial in number, so the DP is polynomial-time.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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