Expert.
Put your skills to the test.

Problem summary

Rearrange every bit of the given string exactly once to obtain the largest binary value divisible by three with no adjacent ones. Print the resulting full-length bit string, or NO if impossible. Leading zeros are allowed.

Constraints

Input length ≤ 2000.

Worked example

Official sample, transcribed with whitespace restored from the PDF.

0101

1001

Solution analysis

1. Only the counts Z and O of zero and one bits matter. Let dp[z][o][p] be a three-bit mask: bit r indicates that some suffix with z zeros and o ones has value r modulo three, when its preceding bit is p. The empty suffix has residue zero for either p.
2. A leading zero is permitted when z>0 and leaves dp[z−1][o][0] unchanged. A leading one is permitted only when p=0 and o>0; it adds 2^(z+o−1) modulo three to each residue in dp[z][o−1][1]. Combine these two possibilities. Powers of two modulo three alternate between one and two, and storing just three-bit masks keeps the quadratic table small.
3. If residue zero is feasible initially, construct the answer left to right. Try one before zero; for the prospective prefix residue q and L remaining bits, the suffix must have residue −q·2^L modulo three. Accept a bit only if the appropriate table mask contains this residue. For two zeros and two ones, the maximal feasible result is 1001, whose value is nine.

Why it works

Induction on z+o proves each mask exactly describes feasible suffixes: every suffix begins with zero or one, and the transition accounts for its leading positional weight and adjacency restriction. During reconstruction, the residue equation is equivalent to divisibility of the completed number. Trying one first chooses the largest feasible next bit; by induction the entire output is the lexicographically largest feasible full-length string, hence has maximum binary value.

Watch out. A one’s contribution depends on its position parity. Preserve all input zeros, including leading zeros when needed. NO is distinct from an all-zero valid output.

An independently written complete program with standard headers.

// Key idea: Induction on z+o proves each mask exactly describes feasible suffixes: every suffix begins
// with zero or one, and the transition accounts for its leading positional weight and adjacency
// restriction. During reconstruction, the residue equation is equivalent to divisibility of the
// completed number.
#include<iostream>
#include<string>
#include<vector>
#include<array>
using namespace std;
int powerTwo(int exponent){
    return exponent%2?2:1;
}
int main(){
    string input;
    cin>>input;
    int zeros=0,ones=0;
    for(char c:input){
        (c=='0'?zeros:ones)++;
    }
    int width=ones+1;
    vector<array<unsigned char,2>>dp((zeros+1)*width,{0,0});
    auto state=[&](int z,int o)->array<unsigned char,2>&{
        return dp[z*width+o];
    };
    state(0,0)={1,1};
    for(int z=0;z<=zeros;++z){
        for(int o=0;o<=ones;++o){
            if(z+o==0){
                continue;
            }
            int zeroMask=z?state(z-1,o)[0]:0;
            int oneMask=0;
            if(o){
                int suffixMask=state(z,o-1)[1];
                int weight=powerTwo(z+o-1);
                for(int r=0;r<3;++r){
                    if(suffixMask&(1<<r)){
                        oneMask|=1<<((r+weight)%3);
                    }
                }
            }
            state(z,o)[0]=static_cast<unsigned char>(zeroMask|oneMask);
            state(z,o)[1]=static_cast<unsigned char>(zeroMask);
        }
    }
    if(!(state(zeros,ones)[0]&1)){
        cout<<"NO\n";
        return 0;
    }
    string answer;
    int prefix=0,previous=0;
    while(zeros+ones){
        for(int bit=1;bit>=0;--bit){
            if((bit&&(previous||!ones))||(!bit&&!zeros)){
                continue;
            }
            int z=zeros-(bit==0);
            int o=ones-bit;
            int nextPrefix=(prefix*2+bit)%3;
            int needed=(3-nextPrefix*powerTwo(z+o)%3)%3;
            if(state(z,o)[bit]&(1<<needed)){
                answer.push_back(char('0'+bit));
                zeros=z;
                ones=o;
                prefix=nextPrefix;
                previous=bit;
                break;
            }
        }
    }
    cout<<answer<<'\n';
}