Is $O(n)$ per iteration and $O(n 2^n)$ total acceptable? If so, you can achieve this by using any $O(1)$ insert time heap to store the candidate sets. You start with the empty set on the heap, and then any time you take a set $S$ out, you insert $S \cup \{a\}$ for all $a$ larger than all $s \in S$ back to the heap. en.wikipedia.org/wiki/…

I wrote a small program to search for counterexamples for k = 2, and the shortest it found is (1 8 3 9 5 10 7 2 4 6). The longest increasing sub sequence has length 4. It seems that it's not possible to reduce that length to 2 by a single application of the operation from your question. Of course, my program can be buggy, so I'd appreciate if you could verify this.

How about decomposing the original sequence into decreasing subsequences in a greedy way (you always extend the first possible subsequence)? For example, (5 6 1 2 4 3 0) decomposes into (5 1, 6 2 0, 4 3). You then distribute these subsequnces into your k=2 queues in any "balanced" way without splitting any of those subsequences, for example 5 6 1 2 4 3 0 -> (5 6 1 2 0, 4 3) or (5 1 4 3, 6 2 0). Then you "mergesort" the k=2 queues into (5 6 4 3 1 2 0) or (6 5 2 1 4 3 0). After one more iteration you get (6 5 4 3 2 1 0). I think this should work, are there any counterexamples?

github.com/kimwalisch/primesum

Say you decrease the radius of each circle by the same amount, and move all lines (including triangle edges) to maintain tangency with the circles. As this operation would merely replace each line with a parallel line, the new triangle will be similar to the original one, and the "equilateral triangle" property will be preserved. By taking the radius decrease to be the radius of the smallest circle, it seems that if there's a solution, then there's always a solution in which one of the circles has radius 0. Trying to find such a solution may be simpler than the original problem.