What is the longest possible Parade?

Question

In the card game Parade, the main mechanic has players build a chain of cards (a "parade") from a special deck. I've reproduced a simplified version of the rules below (original rules here).

• The deck consists of $k=6$ suits, with each suit having values ranging from $a=0$ to $b=10$. In total, there are 66 cards.
• Initially, the parade is empty.
• Cards are added to the end of the parade one-by-one. Duplicates are not allowed (as we only have a single deck).
• In order to be able to add a card of value $x$ and suit $s$ to the end of the parade, the following 2 criteria both need to be satisfied:
  • Apart from the last $x$ cards of the parade, no other card can have value less than or equal to $x$.
  • Apart from the last $x$ cards of the parade, no other card can have suit $s$.

In other words, all cards already in the parade that have value $\le x$ or suit $s$ must have been placed in the last $x$ cards. (In the original game, non-matching cards would be removed from the parade. I chose to instead disallow placing cards which would lead to this, in order to simplify the problem.)

Now my question is: what is the longest possible parade we can achieve?

For the original version of the game ($k=6,a=0,b=10$) I have used brute force to arrive at an answer of 25. I am interested in finding an analytical solution, and in particular how it varies for different values of $k,a,b$.

Answer 1

Here's a solution with length $25$ for $k=6,a=0,b=10$, obtained via integer linear programming:

    x  s
 1 10  6
 2 10  3 
 3 10  1
 4  9  3
 5  9  6
 6  8  3
 7  8  6
 8  7  6
 9  7  3
10  7  1
11  8  1
12  9  1
13  9  2
14  8  2
15  7  2
16  4  2
17  5  2
18  4  5
19  6  2
20  5  5
21  3  5
22  6  5
23  0  4
24  3  4
25  2  4

My formulation uses binary decision variables $y_{x,s,p}$ to indicate whether card $(x,s)$ appears in position $p$.

Here are maximum lengths for other instances: \begin{matrix} k & a & b & \text{maximum} \\ \hline 1 & 0 & 10 & 11 \\ 2 & 0 & 10 & 11 \\ 3 & 0 & 10 & 16 \\ 4 & 0 & 10 & 20 \\ 5 & 0 & 10 & 22 \\ 6 & 0 & 0 & 1 \\ 6 & 0 & 1 & 3 \\ 6 & 0 & 2 & 6 \\ 6 & 0 & 3 & 9 \\ 6 & 0 & 4 & 11 \\ 6 & 0 & 5 & 13 \\ 6 & 0 & 6 & 16 \\ 6 & 0 & 7 & 18 \\ 6 & 0 & 8 & 20 \\ 6 & 0 & 9 & 23 \\ \end{matrix}