Concluding this condition

[Kalcor]

Now it's time of Olympiads. Vanya and Egor decided to make his own team to take part in a programming Olympiad. They've been best friends ever since primary school and hopefully, that can somehow help them in teamwork.

For each team Olympiad, Vanya takes his play cards with numbers. He takes only the cards containing numbers 1 and 0. The boys are very superstitious. They think that they can do well at the Olympiad if they begin with laying all the cards in a row so that:

there wouldn't be a pair of any side-adjacent cards with zeroes in a row;
there wouldn't be a group of three consecutive cards containing numbers one.
Today Vanya brought n cards with zeroes and m cards with numbers one. The number of cards was so much that the friends do not know how to put all those cards in the described way. Help them find the required arrangement of the cards or else tell the guys that it is impossible to arrange cards in such a way.

Input
The first line contains two integers: n (1 ≤ n ≤ 106) — the number of cards containing number 0; m (1 ≤ m ≤ 106) — the number of cards containing number 1.

Output
In a single line print the required sequence of zeroes and ones without any spaces. If such sequence is impossible to obtain, print -1.

Examples
input
1 2
output
101
input
4 8
output
110110110101
input
4 10
output
11011011011011
input
1 5
output
-1

For this problem above, the solution between printing out the sequence and printing a "-1" resolves around this condition:

((n-1)<=m && m <= 2 * (n + 1))

I don't get the reason why we reached this equation.


Also , here is my code:

#include <bits/stdc++.h>


#define fl(i,n)    for(int i = 0; i < n; i++)

#define ll   long long
#define nl   endl
#define pb   push_back
#define mp   make_pair
#define PII  pair<int,int>

#define EPS  1e-9
#define INF  1e9


using namespace std;

int main()
{
    ll n, m;
    cin >> n >> m;
    string s = "";

    int ones = m, zeros = n, enu = 0;
    bool flag = 1;
    while(ones > 0 || zeros > 0){
        if(!flag || ones > zeros && enu < 2){
            enu++;
            ones--;
            s += '1';
            flag = 1;
        }
        else{
            zeros--;
            enu = 0;
            s += '0';
            flag = 0;
        }
    }
    if(((n-1) <= m && 2*(n+1) >= m)){
        cout << s;
    }
    else cout << -1;


    return 0;
}

I had to change to that "if condition" i mentioned above when I got alot of wrong answers because of it, I also didn't figure the equation out on my own, the editorial for this problem stated that this equation is needed, That's why I am asking how did we conclude it?

[lastchance]

I don't get the reason why we reached this equation.

Suppose you have n zeroes.

Given the conditions of the problem, the MINIMUM number m of ones is when the arrangement is of the form
0 1 0 1 0 1 ..... 0 1 0 1 0
(0 on the outsides, and the minimum numbers of ones between them.) There are then one fewer 'ones' than 'zeros'; i.e.
m = n - 1 for the minimum m.

The MAXIMUM number m of 'ones' is for a pattern of type
1 1 0 1 1 0 1 1 0 ... 1 1 0 1 1 0 1 1
(two 'ones' on the outside and between each of the 'zeroes'.) There is thus a pattern 1 1 0 repeated n times, plus two extra 'ones' at the end, making 2n + 2 'ones'; i.e.
m = 2n+2 = 2(n+1)

So m must lie between n-1 and 2(n+1) inclusive.

AFTER you have done this test, then there are many ways of building up the sequence for legitimate m, n. A systematic way might be:
- if m = mmin = n - 1 then: 0 1 0 1 0 1 ..... 0 1 0 1 0 (pattern 0 1 repeated n times, plus a 0)
- if m = mmin+1 then: 1 0 1 0 1 0 1 ..... 0 1 0 1 0 (pattern 1 0 repeated n times)
- if m = mmin+2 then: 1 0 1 0 1 0 1 ..... 0 1 0 1 0 1 (pattern 1 0 repeated n times, plus a 1)
Then start "doubling up" the 'ones' from the left; successively:
1 0 1 0 1 0 1 ..... 0 1 0 1 0 1
1 1 0 1 0 1 0 1 ..... 0 1 0 1 0 1
1 1 0 1 1 0 1 0 1 ..... 0 1 0 1 0 1
1 1 0 1 1 0 1 1 0 1 ..... 0 1 0 1 0 1
until you reach the limit:
1 1 0 1 1 0 1 1 0 1 1 ..... 0 1 1 0 1 1 0 1 1

I would probably start with a string of (m+n) 'ones' (since 1 tends to occur more times) and then loop through the string turning the appropriate number of elements into 'zero'.

[Kalcor]

Love you @lastchance xP