# A card game with a long path

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?

-
add comment

## 1 Answer

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.

-
add comment