# DISTNEIGH - Editorial

**URL:** <https://discuss.codechef.com/t/distneigh-editorial/103812>\
**Category:** editorial\
**Tags:** combinatorics, editorial, start63\
**Created:** [November 2, 2022, 12:20pm UTC](https://discuss.codechef.com/t/distneigh-editorial/103812 "2022-11-02T12:20:27Z")\
**Posts on this page:** 1\
**Showing post:** 2

<div class="post-metadata">

**Author:** ![shivanshj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivanshj/32/24644_2.png) [@shivanshj](https://discuss.codechef.com/u/shivanshj)\
**Post date:** [November 2, 2022, 7:14pm UTC](https://discuss.codechef.com/t/distneigh-editorial/103812/2 "2022-11-02T19:14:56Z")

</div>

I solved it with slightly different method 🙂  
The idea is to imagine the array with all 3's removed. There would be blocks of 1's and 2's. Since a[1] = 1 and a[n] = 1, the array would look like this: 11..1 \; 22..2 \; 11..1 \; 22..2 \; 11..1. Clearly no. of blocks will be odd with alternating 1's and 2's. Now imagine adding 3's. To “fix” a block of size s you need to use 3 exactly s-1 times. For example, to fix 11111 you need to use 3 four times (to get 131313131).

So, if there are k blocks, you require at least x+y-k threes to fix, Now there are additional (n-x-y ) - (x+y-k) threes left, there are also k-1 borders between 1's and 2's in which we have to insert these additional 3's. So, we gotta select (n+k-2x-2y) spaces among total of k-1 spaces. There are \binom{k-1}{n+k-2x-2y} ways to do so!

Now, to form blocks, note that total size of blocks of 1's is exactly x, let w\_{i} be the length of the i^{th} block of 1's. Also, there are ceil(k/2) blocks of 1's and floor(k/2) blocks of 2's We need to find positive integral solutions of -

w\_{1} + w\_{2}...+w\_{ceil(k/2)} = x.  
This is simply, \binom{x-1}{ceil(k/2)-1}. Similar result for no. of ways of making blocks of 2's is \binom{y-1}{floor(k/2)-1}.

So finally the answer would be to sum \binom{x-1}{ceil(k/2)-1}\binom{y-1}{floor(k/2)-1}\binom{k-1}{n+k-2x-2y} for all odd k from 1 to n.

Link for my submission: [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/78976625)  
🙂

---

_[View the full topic](https://discuss.codechef.com/t/distneigh-editorial/103812)._