SUSSTR - Editorial

[iceknight1093]

PROBLEM LINK:

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

Author: S. Manuj Nanthan
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh

DIFFICULTY:

TBD

PREREQUISITES:

(Optional) Deques

PROBLEM:

Alice and Bob play a game on a binary string S, creating a new string T. They alternate moves, with Alice going first.

• Alice takes the first remaining character of S and moves it to either the start or end of T
• Bob takes the last remaining character of S and moves it to either the start or end of T

Alice tries to (lexicographically) minimize T, while Bob tries to maximize it. What is the final string?

EXPLANATION:

Alice and Bob end up having extremely well-defined moves.

• Since Alice wants to minimize the string, she will always move a 0 to the front and a 1 to the end of T.
• Conversely, Bob will always move a 0 to the back and 1 to the front of T.

This is already enough to solve the problem in \mathcal{O}(N^2) by directly simulating each move:

• Let T be an empty string.
• On Alice’s turn:
  • If the character is 0, insert it to the front of T
  • If the character is 1, insert it to the back of T
• On Bob’s turn:
  • If the character is 1, insert it to the front of T
  • If the character is 0, insert it to the back of T

Finally, print T.

For the limits given in the problem, this is already good enough. However, with the help of data structures, there exists a faster solution.

Knowing the moves, all that needs to be done is to simulate the game quickly. For this, we would like a data structure that allows us to quickly insert elements at both the start and the end. The appropriate structure here is a deque (std::deque in C++, collections.deque in Python).

The final solution is thus:

• Keep a deque T, which is initially empty.
• On Alice’s turn:
  • If the character is 0, push it to the front of T
  • If the character is 1, push it to the back of T
• On Bob’s turn:
  • If the character is 1, push it to the front of T
  • If the character is 0, push it to the back of T

Finally, print T from front to back.

Every operation on T is \mathcal{O}(1), and by choosing the first/last character of S by maintaining two pointers (instead of directly deleting the character) these operations also become \mathcal{O}(1). This leads to a final complexity of \mathcal{O}(N).

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;
        int L = 0, R = n-1;
        deque<char> dq;
        while (L <= R) {
            if (s[L] == '0') dq.push_front('0');
            else dq.push_back('1');
            
            if (L < R) {
                if (s[R] == '1') dq.push_front('1');
                else dq.push_back('0');
            }
            ++L, --R;
        }
        for (auto c : dq) cout << c;
        cout << '\n';
    }
}

[theairo1]

Isn’t a naive solution O(n), instead of O(n^2)?

#include <bits/stdc++.h>
#define ll long long
#define llinf LLONG_MAX
#define llminf LLONG_MIN
#define inf INT_MAX
#define minf INT_MIN
unsigned long int M = 1000000007;

using namespace std;

int main() {
    int t,n;
    cin >> t;
    while (t--) {
        cin >> n;
        string s;
        cin >> s;
        string ans = "";
        for (int i = 0;i<n;i++) {
            if (i%2==0) {
                if (s[i/2]=='1') {
                    ans=ans+'1';
                }
                else {
                    ans='0'+ans;
                }
            }
            else {
                if (s[n-(i/2)-1]=='1') {
                    ans='1'+ans;
                }
                else {
                    ans = ans + '0';
                }
            }
        }
        cout << ans << endl;
    }
}

[drizzle1372]

Why is the second if condition " if ( l < R) " necessary. Please explain.
Thank you.

[anshuman0935]

My solution to this problem is giving WA. Here is the test case that failed.

To me, it seems correct… Can someone please explain this to me.

Here is my code.

#include<bits/stdc++.h>

using namespace std;

int main(){
    int t;
    cin>>t;
    while(t){
        string str,temp;
        int n;
        cin>>n>>str;
        int i =0,j=str.length()-1,ctr=0;
        while(i<=j){
            if(ctr%2){
                if(str[j--] == '1')
                    temp = "1"+temp;
                else
                    temp = temp + "0";
            }
            else{
                if(str[i++] == '0')
                    temp = "0" + temp;
                else
                    temp = temp + "1";
            }
            ctr++;
        }
        cout<<temp<<'\n';
        t--;
    }
    return 0;
}

[anshuman0935]

I guess it is O(n^2) as inserts in the 0th index would be an O(n) operation itself in a string.

[iceknight1093]

In my implementation, that takes care of the case when the string is odd. Without that condition, the middle character would be processed for both Alice and Bob, which is wrong. The condition ensures it’s processed for only Alice.

[iceknight1093]

I’m not sure what you mean, I submitted your code and it gives me AC.

Submission

[klu_2000031509]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(string &s)
{
    ll n = s.length();
    vector<char> v;
    for(ll i=0,j=n-1;i<n/2,j>=n/2;i++,j--) // i position = Alice , j position = Bob
    {
            if(s[i]=='0') // Alice ith position insert , 0 -> begin (make small)
            v.insert(v.begin(),'0');
            else
            v.insert(v.end(),'1');
            if(s[j]=='1')     // Bob jth position insert, 1 -> begin (make large)
            v.insert(v.begin(),'1');
            else
            v.insert(v.end(),'0');
    }
   
    for(auto i:v)
     cout<<i<<"";
    cout<<"\n";
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll testcases;
    cin>>testcases;
    while(testcases--)
    {
       ll n;
       cin>>n;
       string s;
       cin>>s;
       solve(s);
       
    }
}

Problem Link: Problem link Suspense String
Why my code is not passing all testcases? where I made mistake?

[anshuman0935]

Sorry for pasting the wrong code. I was looking for solutions and it was on my clipboard. Here is the one that I submitted.
submission

The case seems correct still marked as WA.

[theairo1]

temp.resize(n); - is wrong in your code.
You resize it to n and then push_back and insert to it.
Better: temp="";
Then it gives AC.

[aayush249]

How am I wrong in this code?
My Solution
I did what was said in the editorial

[iceknight1093]

You don’t handle odd-length strings correctly.

For example, on testcase

1
3
000

you print 0000 which is obviously wrong.

[aayush249]

I see . Thanks