BDBD - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You’re given a circular binary string and a starting index K.
You must delete all the elements of the string, starting from K and then repeatedly deleting an adjacent element.
On odd-numbered turns, your score increases by the deleted value; on even-numbered turns, it decreases.

Find a scheme that deletes every element while never letting your score fall to 0 or below, or claim that this is impossible.

EXPLANATION:

Let’s call odd-numbered moves “addition moves”, and even-numbered “subtraction moves”.
Further, all indices talked about are implicitly being taken modulo N, since we’re on a circle.

Observe that deleting a 0 doesn’t change our score at all, no matter when it’s done - so in a sense, such a move is ‘free’.
On the other hand, deleting a 1 either increases or decreases our score by 1.

We start with a score of 0, and every move after the first must result in a positive score.
In particular, this means S_K = 1 must hold; since if S_K = 0 then we’ll lose after the very first move.

Now, suppose S_K = 1.
After the first move, our score is 1.
However, the second move is a subtraction move - so if we subtract 1 we’ll just end up back at 0, which is not good.
This means our second move is somewhat forced: specifically, we’re forced to subtract a 0 (and hence leave the score at 1) if we don’t want to lose immediately.
In particular, this means we must have either S_{K-1} or S_{K+1} be equal to 0: if they’re both equal to 1, then we’re forced to subtract 1 and so we lose.

Suppose we haven’t lost after the second move - so, S_K = 1 and at least one of S_{K-1} and S_{K+1} equals 0.
If they’re both 0 we don’t yet know which one to choose, but we’ll get back to that.

What should our third move be?
It’s an addition move, so ideally we want to add a 1 and increase the score further.
Suppose this is possible, and we end up with a score of 2.
There is now a simple strategy to clear out the string!

How?

Suppose our score is currently \ge 2.
Let L and R denote the two elements to our left and right.

Then,

  • If S_L = S_R, simply take S_L and S_R on consecutive moves.
    This will leave the score unchanged after both moves; and after the first move it’ll still be at least 1 so we haven’t lost.
  • If S_L = 0 and S_R = 1 (or vice versa), note that of the next two moves, one is an addition move and one is a subtraction move.
    Pick the 1 on the addition move and the 0 on the subtraction move; which just increases our score by 1.

This way, we can repeatedly keep deleting two elements while the score is always \ge 2, so we never lose.
It also gives an explicit construction of the sequence.

From the above situation, we know that it’s ideal to reach a score of 2.

Luckily, as long as we aren’t forced to lose in the first couple of moves (by the initial checks on S_{K-1}, S_K, S_{K+1} outlined above), we can always achieve this!

  • The first move is forced.
  • On the second move, at least one adjacent zero exists - choose one arbitrarily.
  • Now, consider the third move. There are two cases:
    1. First, there might be a 1 adjacent to us.
      We can simply take it and end up at 2, after which we have a winning strategy already.
    2. Next, it’s possible both adjacent elements are zeros.
      Here, let’s just repeatedly take the 0 to our left, till we reach a 1 to our left.
      If the 1 is reached on an addition move, take it and the score becomes 2.
      If the 1 is reached on a subtraction move, take the 0 to the right first, and then take the 1 to make the score 2, after which we win.
      The only ‘edge case’ is when all elements of S are zeros (other than S_K), in which case it’s impossible to lose anyway.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Tester's code (C++) 
// Har Har Mahadev
#include<bits/stdc++.h>
#define ll long long
// #define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

void operate_front(deque<array<int,2>>& d,vector<int>& ops,int& sm){
    assert(d.size());
    auto res = d.front();
    d.pop_front();
    ops.push_back(res[1]);
    if(ops.size()&1)sm += res[0];
    else sm -= res[0];
    assert(sm > 0);
}

void operate_back(deque<array<int,2>>& d,vector<int>& ops,int& sm){
    assert(d.size());
    auto res = d.back();
    d.pop_back();
    ops.push_back(res[1]);
    if(ops.size()&1)sm += res[0];
    else sm -= res[0];
    assert(sm > 0);
}
 
void solve()
{
    int n, k; cin >> n >> k;
    string s; cin >> s;
    
    k--;
    if(s[k] == '0'){
        cout << "-1\n";return;
    }
    if(s[(k+1)%n] == '1' && s[(k-1+n)%n] == '1'){
        cout << "-1\n";return;
    }

    deque<array<int,2>> d;
    vector<int> op;
    op.push_back(k+1);
    for(int i = k-1;i >= 0;i--)d.push_back({s[i]-'0',i+1});
    for(int i = n-1;i >= k+1;i--)d.push_back({s[i]-'0',i+1});
    int sm = 1;

    if(d.front()[0] == 1){
        operate_back(d,op,sm);
        operate_front(d,op,sm);
    }
    else if(d.back()[0] == 1){
        operate_front(d,op,sm);
        operate_back(d,op,sm);
    }
    else{
        while(d.size() && d.front()[0] != 1){
            operate_front(d,op,sm);
        }
        if(d.size()){
            if(op.size()&1)operate_back(d,op,sm);
            operate_front(d,op,sm);
        }
    }
    while(d.size()){
        while(d.size() && d.front()[0] == 0)operate_front(d,op,sm);
        while(d.size() && d.back()[0] == 0)operate_back(d,op,sm);
        if(d.size())operate_front(d,op,sm);
        if(d.size())operate_back(d,op,sm);
    }
    for(auto &x : op)cout << x << " ";
    cout << "\n";
    
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef NCR
        init();
    #endif
    #ifdef SIEVE
        sieve();
    #endif
    int t; cin >> t;
    while(t--)
        solve();
    return 0;
}
1 Like