Proficient.
Put your skills to the test.

Problem summary

Choose binary strings of length five with prescribed counts of strings having 1,2,…,5 ones. Arrange them to minimize the total number of shared one positions across adjacent strings.

Constraints

1 ≤ b1+…+b5 ≤ 10000.

Worked example

An independently prepared example for this explanation.

3 1 4 2 1

3

Solution analysis

1. If neighboring strings contain x and y ones, their minimum possible overlap is c(x,y)=max(0,x+y−5). Once the previous string is fixed, put ones in its zero positions first, then in its one positions. Thus these pairwise minimum costs can all be attained along any chosen order.
2. The remaining multiset path problem has convex sum costs. Sort the one-counts. Fill the exposed right end with the largest remaining value and immediately inward with the smallest; then do the same at the exposed left end, alternating ends until finished. This alternating-extremes arrangement minimizes the sum of c over adjacent values.
3. For counts 3,1,4,2,1, one resulting count order is 4,1,3,2,3,3,3,1,4,1,5. Only three adjacent sums exceed five, each by one, so the minimum is three. The task asks only for this score, so actual bit strings need not be constructed.

Why it works

For any pair, inclusion-exclusion forces overlap at least max(0,x+y−5); choosing new one positions greedily attains it independently of earlier pairs. For the ordering use the alternating-extremes path lemma for increasing convex sum costs: for a≤b and c≤d, c(a,c)+c(b,d)≥c(a,d)+c(b,c). This follows by comparing the nondecreasing increments of the convex function max(0,t−5). Uncrossing the two connections of the largest and smallest unplaced entries using this inequality places them together at an exposed end without increasing cost; repeat at the opposite end. Induction leaves exactly the constructed path, so its cost is minimal.

Watch out. Strings with equal contents may be repeated: only the counts of ones matter. Minimize the arrangement before summing overlaps; arbitrary alternating high/low orders need not be optimal.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: If neighboring strings contain x and y ones, their minimum possible overlap is
// c(x,y)=max(0,x+y−5).
using namespace std;
int main(){
    vector<int>sorted;
    for(int ones=1;ones<=5;++ones){
        int count;
        cin>>count;
        for(int copy=0;copy<count;++copy){
            sorted.push_back(ones);
        }
    }
    int n=static_cast<int>(sorted.size());
    vector<int>order(n);
    int low=0,high=n-1,left=0,right=n-1;
    bool fromRight=true;
    while(low<=high){
        if(fromRight){
            order[right--]=sorted[high--];
            if(low<=high){
                order[right--]=sorted[low++];
            }
        }
        else{
            order[left++]=sorted[high--];
            if(low<=high){
                order[left++]=sorted[low++];
            }
        }
        fromRight=!fromRight;
    }
    int answer=0;
    for(int i=1;i<n;++i){
        answer+=max(0,order[i-1]+order[i]-5);
    }
    cout<<answer<<'\n';
}