Hello Programmers In this post, you will know how to solve the Crazy Subsequences Codechef Solution. The Problem Code is CRASUB.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.
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 Solutions 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 Solutions in Python
Coming soon
Disclaimer: The above Problem (Crazy Subsequences ) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purpose.
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.