0
$\begingroup$

Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules:

The first card goes to the top of a stack

For every new card k,or

(i) the k is put on the top of an already existed stack, if the value of the top card of a existed stack is bigger than the value of the card k or

(ii) we create a new stack righter than the other stacks and with the card k.

The game is completed after n rounds when there are no more cards on the first pack of cards.

The problem asks to find the optimal algorithm for minimum stacks and prove that this one is the optimal. Thanks in advance.

$\endgroup$
  • $\begingroup$ Can the algorithm create a new stack even if there is an existing stack whose top card has a larger value than $k$? $\endgroup$ – Steven Oct 31 '19 at 17:26
  • $\begingroup$ No I think there is not such contstrain $\endgroup$ – gewpeg Oct 31 '19 at 17:43
  • $\begingroup$ So.. the algorithm can always create a new stack? Also, are you looking for an online algorithm (only the top card is revealed) or for an offline algorithm (the deck permutation is known beforehand)? In the former case what do you mean by "optimal"? Are you looking to optimize the (expected) competitive ratio? $\endgroup$ – Steven Oct 31 '19 at 19:13
  • $\begingroup$ Only the top card is revealed.By optimal I mean that there is no other algorithm which can create less stacks. My only thought was to create an algorithm which every time checks which top card of every stack has the nearest higher value. When the algorithm finds this card(assume m) , we put the k card on the stack which has the top card m. Of course if we don't find any card we create a new stack with the card k.I can't proof though that this algorithm is the optimal $\endgroup$ – gewpeg Oct 31 '19 at 19:16
  • $\begingroup$ Can you credit the source where you originally encountered this problem? $\endgroup$ – D.W. Oct 31 '19 at 20:56
1
$\begingroup$

Use the following strategy $S$: Put each card $c$ on the stack with the smallest top card $c'$ such that $c' > c$.

Consider a generic strategy $T$, and iteratively simulate $S$ and $T$. Let $s_i = (s^i_1, s^i_2, \dots, s^i_{h_i})$ be the values on the top of the stacks after placing the $i$-th card $c_i$ according to strategy $S$, in increasing order. Define $t_i = (t^i_1, t^i,_2, \dots, t^i_{k_i})$ similarly for strategy $T$.

Claim: $\forall i=1,\dots,n$, we have: i) $h_i \le k_i$ and ii) $s^i_j \ge t^i_j$ for all $j = 1, \dots, h_i$.

The proof is by induction on $i$. For $i=1$ we have $h_1=k_1=1$ and $s^1_1 = t^1_1 = c_1$. For $i>1$ we have two cases.

Case 1) $S$ places $c_i$ in a new stack. Then, by hypothesis we must have $c_i > s^{i-1}_j \ge t^{i-1}_j$ for every $j = 1, \dots, h_{i-1} $. It follows that $k_i \ge h_{i-1} + 1 = h_i$, proving i). Notice that ii) is also verified since, for $j=1,\dots, h_{i-1}$, we have $c_i > s^i_j = s^{i-1}_j \ge t^{i-1}_j = t^i_j$ by induction hypothesis, and $t^i_{h_i} \le c_i = s^i_{h_i}$.

Case 2) $S$ places $c_i$ in an existing stack. Let $\ell$ be the index such that $s^{i}_\ell = c_i$. We clearly have $k_i \ge k_{i-1} \ge h_{i-1} = h_i$, proving i). As far as ii) is concerned, for every $j = 1, \dots, \ell-1$ we have $c_i > s^{i-1}_j \ge t^{i-1}_j$, and hence $s^i_j \ge t^i_j$. Also, $s^i_\ell = c_i = \min\{s^{i-1}_\ell, c_j\} \ge \min\{t^{i-1}_\ell, c_j\} = t^i_\ell$. Finally, for $j=\ell +1, \dots, h_i$, we have: $s^i_j = s^{i-1}_j \ge \max\{c_i, s^{i-1}_j\} \ge \max\{c_i, t^{i-1}_j\} \ge t^i_j$.

Instantiating the claim with $i=n$ yields $h_n \le k_n$, showing that $S$ is minimizing the number of stacks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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