# Tag Info

2

Every such arrangement of 15 balls to 21 boxes corresponds, in a one-to-one fashion, to a string of the form *|**||||...|*, where there are a total of 35 symbols in the string, exactly 15 stars and 20 bars. (Think of each * as a ball, and each | as a divider between two boxes.) These, in turn, correspond to the set of binary strings of length 35 that ...

1

Brute force If you want something easy to implement, brute force might be fast enough, assuming at least one round has been completed. There are $8! = 40320$ possible permutations of the athletes, so in any round, there are 40320 possible rankings. Assuming the first round has been completed, there are only $40320^2 \approx 1.6 \times 10^9$ possible ...

2

Let's first describe a notation for our partitions. Let $p_i$ represent the $i$th partition which is made up of $|S|/2$ disjoint pairs of $S$. We can represent $p_i$ as $$p_i=b_{i,1},b_{i,2},...b_{i,S/2}$$ In order to ensure uniqueness of partitions, we will enforce a sorting on each partition. For each partition $p_i$, each pair in $p_i$ must be sorted. ...

2

No. Intuitively, the problem gets harder if we take out the restrictions on the input values, since the restricted instances are a subset of the instances of the general problem. However, the article says, even if you introduce this restriction the problem does not get easier and it is still strongly NP-complete. On the other hand, exhaustive search is not ...

Top 50 recent answers are included