Crazy Subsequences Codechef Solution

Hello coders, today we are going to solve Crazy Subsequences Codechef Solution whose Problem Code is CRASUB.

As you already know that this site does not contain only the Codefchef solutions here, you can also find the solution for other programming problems. I.e. LeetcodeC programsC++ Programs SolutionsPython ProgramsWeb Technology, Data StructuresRDBMS Programs and Java Programs Solutions.

Crazy Subsequences Codechef Solution

Problem

Chef has a binary string S. He can modify it by choosing any subsequence of length 3 from it and deleting the first and last character of the subsequence.

For example, if S = \textcolor{red}{11}01\textcolor{red}{0}1S=110101, Chef can choose the subsequence marked in red and delete its first and last characters, obtaining the string S = 1011S=1011.

Chef wonders what is the lexicographically largest string he can obtain by modifying the original string using a finite number of operations. Please help Chef in this task.

Note: A binary string AA is said to be lexicographically larger than another binary string BB if:

  • BB is a proper prefix of AA (for example, 101101 is lexicographically larger than 1010); or
  • There exists an index ii such that A_1 = B_1, A_2 = B_2, \ldots, A_{i-1} = B_{i-1}A1​=B1​,A2​=B2​,…,Ai−1​=Bi−1​ and A_i \gt B_iAi​>Bi​.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases.
  • Each test case consists of a single line of input containing the original binary string SS.

Output Format

For each test case, output on a new line the lexicographically largest string Chef can obtain.

Constraints

  • 1 \leq T \leq 2\cdot 10^41≤T≤2⋅104
  • 3 \leq |S| \leq 10^53≤∣S∣≤105
  • SS is a binary string, i.e, only contains the characters 00 and 11 in it
  • The sum of |S|∣S∣ over all test cases won’t exceed 3\cdot 10^53⋅105.

Sample 1:

Input

4
101
1010
0000
0001

Output

101
11
0000
0

LinkedIn Skill Assessment Answers

Coursera Quiz Answers

Explanation:

Test case 11: It is optimal to not perform any moves.

Test case 22: In one move, by choosing the subsequence 1\textcolor{red}{010}1010, the string can be made into 1111, which is the lexicographically largest possible.

Test case 33: It is optimal to not perform any move.

Crazy Subsequences Codechef Solution in CPP

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#include <stdio.h>
int even() {
  int n;
  cout << "Enter an integer: ";
  cin >> n;
  if ( n % 2 == 0)
    cout << n << " is even.";
  else
    cout << n << " is odd.";
  return 0;
}
string dragon(string animal){
    string zebra;
    if(animal.size()>=3&&animal[animal.size()-1]=='1'&&animal[animal.size()-2]=='1'){
        animal[animal.size()-1]='$';
        for(ll i=0;i<(ll)animal.size();++i)
        if(animal[i]=='0'){
            animal[i]='$';
            break;
        }
        for(ll i=0;i<(ll)animal.size();++i)
            if(animal[i]!='$')
            zebra+=animal[i];
            return zebra;
    }else return animal;
}
ll crow(string strand){
    vector<ll> esla;
    for(ll i=0;i<strand.size();++i){
        if(strand[i]=='0') esla.push_back(i);
    }
    if(esla.size()==1) return 1;
    if(esla[esla.size()-1]==esla[esla.size()-2]) return 1;
    for(ll i=esla[0];i<esla[esla.size()-2];++i)
    if(strand[i]=='1') return 1;
    return 2;
}
void summary(){
    string sand,animal;
    ll tea=0,parrot=0;
    cin>>sand;
    for(ll i=(ll)sand.size()-1;i>=0;--i)
    if(sand[i]=='1'){
        for(ll j=0;j<=i;++j)
        animal+=sand[j];
        break;
    }else tea++;
    if(tea==(ll)sand.size()){
        cout<< sand<<"\n";
        return;
    }
    sand=animal;
    for(ll i=0;i<(ll)sand.size();++i)
    if(sand[i]=='0') parrot++;
    if(parrot==0){
        cout<<sand;
        for(ll i=0;i<tea;++i) putchar('0');
        putchar('\n');
        return;
    }
    if(parrot%2==0){
        ll land=2147482647,rat=-2147483648;
        for(ll i=0;i<(ll)sand.size();++i)
        if(sand[i]=='0'){
            land=min(land,i);
            rat=max(rat,i);
        }
        for(ll i=land;i<=rat;++i)
        if(sand[i]=='1'){
            for(ll j=0;j<(ll)sand.size();++j)
            if(sand[j]=='1') putchar('1');
            for(ll i=0;i<tea;++i) putchar('0');
            putchar('\n');
            return;
        }
        if(tea>=2){
            for(ll i=0;i<(ll)sand.size();++i)
            if(sand[i]=='1') putchar('1');
            for(ll i=0;i<tea-2;++i) putchar('0');
            putchar('\n');
            return;
        }
        if(tea==1){
            animal="";
            for(ll i=(ll)sand.size()-1;i>=0;--i)
            if(sand[i]=='0'){
                sand[i]='$';break;
            }
            for(ll i=0;i<(ll)sand.size();++i)
            if(sand[i]=='$') animal+='0'; else
            if(sand[i]=='1') animal+='1';
            sand=animal;
            cout<<dragon(sand)<<"\n";
            return;
        }
        if(tea==0){
            ll _=0;animal="";
            for(ll i=(ll)sand.size()-1;i>=0;--i)
            if(sand[i]=='0'){
                sand[i]='$';
                _++;
                if(_==2)
                break;
            }
            for(ll i=0;i<(ll)sand.size();++i)
            if(sand[i]=='$') animal+='0'; else
            if(sand[i]=='1') animal+='1';
            sand=animal;
            cout<<dragon(dragon(sand))<<"\n";
            return;
        }
    }
    ll esla=0,L=crow(sand);animal="";
    for(ll i=sand.size()-1;i>=0;--i)
    if(sand[i]=='0'){
        esla++;
        if(esla==L) sand[i]='$';
    }
     //         cin>>   for(long long i=0;i<x;i++)
	   // {
	   //     for(long long j=0;j<y;j++)
	   //     {
	   //         cin>>b[i][j];brr[r++]=b[i][j];s1.insert(b[i][j]);
	   //         m[b[i][j]].push_back(k);
	   //         k++;
	   //     }
	   // }r=0;
	   //  for(int i=0;i<x;i++)
	   // {
	   //     for(int j=0;j<y;j++)
	   //     {a[i][j];arr[r++]=a[i][j];s.insert(a[i][j]);
    for(ll i=0;i<(ll)sand.size();++i)
    if(sand[i]=='1') animal+='1';
    else if(sand[i]=='$') animal+='0';
    sand=animal;
    if(tea!=0){
        for(ll i=0;i<(ll)sand.size();++i)
        if(sand[i]=='1') putchar('1');
        for(ll i=0;i<tea-1;++i)
        putchar('0');
        putchar('\n');
        return;
    }
    cout << dragon(animal) <<"\n";
}
int main() {
  // your code goes here
  ll t;
  cin>>t;
  while(t--)
 {
      summary();
  }
  return 0;
}

Crazy Subsequences Codechef Solution in JAVA

/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		int t;
  Scanner scanner = new Scanner(System.in);
  t = scanner.nextInt();
  scanner.nextLine();
  char[] s;
  int count;
  while (t-- > 0) {
   count = 0;
   s = scanner.nextLine().toCharArray();
   for (int i = 0; i < s.length; i++) {
    if (s[i] == '0')
     count++;
   }
   int i = s.length - 1;
   while (i >= 0 && s[i] == '0')
    i--;
   if (count == 0 || count == s.length)
    System.out.println(s);
   else if (s.length - 1 - i > 1) {
    solvelastzeroes(s, i);
   } else if (count % 2 == 0)
    solveven(s, s.length);
   else
    solveodd(s);
  }
 }
 static void displayone(int x) {
  while (x-- > 0)
   System.out.print(1);
 }
 static int countone(char[] s, int x, int y) {
  int count = 0;
  for (int i = x; i < y; i++) {
   if (s[i] == '1')
    count++;
  }
  return count;
 }
 static int countzeroes(char[] s, int x, int y) {
  int count = 0;
  for (int i = x; i < y; i++) {
   if (s[i] == '0')
    count++;
  }
  return count;
 }
 static void checkone(char[] s) {
  int i = s.length - 1;
  int j = i;
  while (s[i] != '0')
   i--;
  while (s[j] == '0')
   j--;
  if (i > j) {
   displayone(countone(s, 0, s.length));
   System.out.println(0);
  } else if (j > i && s[j] != s[j - 1]) {
   displayone(countone(s, 0, s.length) - 1);
   System.out.println("01");
  } else {
   displayone(countone(s, 0, s.length) - 1);
   System.out.println();
  }
 }
 static void checkthree(char[] s) {
  int i = s.length - 1;
  int j = i;
  while (s[i] != '0')
   i--;
  while (s[j] == '0')
   j--;
  if (i > j) {
   displayone(countone(s, 0, s.length));
   System.out.println(0);
  } else if (j > i && s[j] != s[j - 1]) {
   displayone(countone(s, 0, s.length) - 1);
   System.out.println("01");
  } else {
   displayone(countone(s, 0, s.length) - 1);
   System.out.println();
  }
 }
 static void checktwo(char[] s, int countof1, int countof2) {
  int i = s.length - 1;
  int j = i;
  while (s[i] != '0')
   i--;
  while (s[j] == '0')
   j--;
  if (j > i && s[j] == s[j - 1]) {
   displayone(countone(s, 0, s.length) - 1);
   System.out.println();
  } else if (countof1 > 1 && countof2 > 1) {
   checkthree(s);
  } else {
   if (countof1 == 1) {
    checkthree(s);
   } else {
    i = 0;
    while (s[i] != '0')
     i++;
    displayone(countone(s, 0, i));
    if (countone(s, i, s.length) > 1) {
     displayone(countone(s, i, s.length) - 1);
    } else {
     System.out.print(0);
     displayone(countone(s, i, s.length));
    }
    System.out.println();
   }
  }
 }
 static void solveodd(char[] s) {
  int i = 0;
  int countof1 = 0;
  int countof2 = 0;
  while (i < s.length && s[i] != '0')
   i++;
  while (i < s.length && s[i] == '0') {
   i++;
   countof1++;
  }
  while (i < s.length && s[i] != '0')
   i++;
  int x = i;
  while (i < s.length && s[i] == '0') {
   i++;
   countof2++;
  }
  while (i < s.length && s[i] != '0')
   i++;
  if (x == s.length) {
   checkone(s);
  } else if (i == s.length) {
   checktwo(s, countof1, countof2);
  } else {
   checkthree(s);
  }
 }
 static void solveven(char[] s, int n) {
  int i = 0;
  int x = i;
  while (i < n && s[i] == '1')
   i++;
  x = i;
  while (i < n && s[i] == '0')
   i++;
  int y = i;
  while (i < n && s[i] == '1')
   i++;
  if (i == n) {
   displayone(countone(s, 0, x));
   if (countone(s, y, n) <= 1) {
    System.out.print("00");
    displayone(countone(s, y, n));
   } else if (countone(s, y, n) == 2) {
    System.out.print(0);
    displayone(countone(s, y, n) - 1);
   } else {
    displayone(countone(s, y, n) - 2);
   }
   System.out.println();
  } else {
   displayone(countone(s, 0, n));
   System.out.println();
  }
 }
 static void solvelastzeroes(char[] s, int i) {
  displayone(countone(s, 0, i + 1));
  if(countzeroes(s, 0, i + 1) % 2 == 1) {
   for (int j = i + 1; j < s.length - 1; j++)
    System.out.print(s[j]);
  } else {
   int k = i;
   while (k >= 0 && s[k] != '0')
    k--;
   while (k >= 0 && s[k] == '0')
    k--;
   while (k >= 0 && s[k] != '0')
    k--;
   if (countzeroes(s, 0, i + 1) == 0) {
    for (int j = i + 1; j < s.length; j++)
     System.out.print(s[j]);
   } else if (k == -1) {
    for (int j = i + 1; j < s.length - 2; j++)
     System.out.print(s[j]);
   } else {
    for (int j = i + 1; j < s.length; j++)
     System.out.print(s[j]);
   }
  }
  System.out.println();
 }
	}

Crazy Subsequences Codechef Solution in Python

Coming soon

Disclaimer: The above Problem (Crazy Subsequences ) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.

Finally, we are now, in the end, I just want to conclude some important message for you

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Please share our posts on social media platforms and also suggest to your friends to Join Our Groups. Don’t forget to subscribe. 

Leave a Comment