Given a row of length N, and a set of 1D bars having lengths A[1...M], how many ways I can fill the row?
A is an integer array,
the bars are having dimensions $\{1\times A_1,1\times A_1,1\times A_1,..., 1\times A_M \}$
The row can also be considered as $1\times N$ grid.

  1. 2 Bars with equal length has to be considered as 2 distinct bar not 1.
  2. Bars are same from either direction, so just by reversing bars there wont be any new arrangement
  3. A bar can be placed with a maximum of 50% out of grid(on either side of grid) PROVIDED ALL BARS ARE HAVING EVEN LENGTH

Example :
$N=4,\space A=\{2,4\} \\ Answer=6 $


Explanation : consider strings to represent bars are XX and YYYY Now six arrangements will be $$\\ XYYY \\ X\_YY \\ XXYY \\ YYYX \\ YY\_X \\ YYXX \\ $$

Except the last condition rest is already solved here in previous post

  • $\begingroup$ You can probably reduce to the situation described in the previous post. I encourage you to spend a few more days on the problem. $\endgroup$ – Yuval Filmus Jan 15 '17 at 18:55
  • $\begingroup$ Can u plz suggest an 'edit'? <br> I'm not getting u. Pardon $\endgroup$ – pPanda_beta Jan 15 '17 at 19:48
  • $\begingroup$ Please try using the techniques described here: cs.stackexchange.com/tags/dynamic-programming/info, spend some more time on the problem working through the steps suggested there, and then edit the question to show us what progress you've made so far and at what stage you got stuck. $\endgroup$ – D.W. Jan 16 '17 at 4:32
  • $\begingroup$ I asked this question for solution and/or a specific hint, not some "teacher-like" advises, @D.W. $\endgroup$ – pPanda_beta Jan 16 '17 at 17:13

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.