Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). Denote the indices of bins having balls as $x_1, \cdots, x_{2k}$ in ascending order ($x_1 < x_2 < \cdots < x_{2k}$). We define the score of a configuration as $\oplus_{i=1}^{k}(x_{2i}-x_{2i-1}-1)$, where $\oplus$ is "bitwise exclusive or", or "xor". I'd like to count for each possible score, how many configurations are there?

Range: $n \leq 10^5, k \leq 50$. I've tried dynamic programming: let $f[i][j][s]$ be the number of configurations with $i$ bins, $2j$ balls, $s$ scores, but the time complexity is too high. I was wondering whether we may count the configuration more efficiently.

  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. Showing your progress so far often helps people give better answers. You might find this page helpful in improving your question. $\endgroup$ – D.W. Nov 19 '18 at 3:42
  • $\begingroup$ The table you mention isn't so big. Are you using a fast enough language? $\endgroup$ – Yuval Filmus Nov 19 '18 at 6:28
  • $\begingroup$ The number of all possible scores is $O(n)$, but direct dynamic programming runs in $O(n^3\cdot k)$ which is too slow. $\endgroup$ – Hang Wu Nov 19 '18 at 6:31
  • $\begingroup$ It should be possible to calculate each cell in $O(1)$. As a simplification, it is better to consider $j$ rather than $2j$ balls. $\endgroup$ – Yuval Filmus Nov 19 '18 at 7:53
  • $\begingroup$ @Apass.Jack I didn't imply such a thing. $\endgroup$ – orlp Nov 19 '18 at 7:54

Your Answer

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

Browse other questions tagged or ask your own question.