Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Alternative Sufferings CodeChef Solution
Problem -Alternative Sufferings CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Alternative Sufferings CodeChef Solution in C++17
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll t, n, k, i, j;
string a;
cin>>t;
for(;t--;)
{
cin>>n>>k;
ll left[n], right[n];
cin>>a;
for(i=0; i<n; i++) left[i]=right[i]=10000000000;
j=-1;
for(i=0; i<n; i++) {
if(a[i]=='1') j=i;
else if(j!=-1) left[i]=i-j;
}
j=-1;
for(i=n-1; i>=0; i--) {
if(a[i]=='1') j=i;
else if(j!=-1) right[i]=j-i;
}
j=-1;
for(i=0; i<n; i++) {
if(a[i]=='0') j=i;
else if(j!=-1) left[i]=i-j;
}
j=-1;
for(i=n-1; i>=0; i--) {
if(a[i]=='0') j=i;
else if(j!=-1) right[i]=j-i;
}
for(i=0; i<n; i++) {
if(a[i]=='0') {
j=min(left[i], right[i]);
if(j<=k) {
int dis=k-j+1;
if((dis%2)==1) a[i]='1';
}
} else {
j=min(left[i], right[i]);
a[i]='0';
if(j<=k-1){
int dis=k-j;
if((dis%2)==1) a[i]='1';
}
}
}
for(i=0; i<n; i++) cout<<a[i];
cout<<endl;
}
}Alternative Sufferings CodeChef Solution in C++14
#include<bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#define maxv 9223372036854775807
#define minv -9223372036854775808
#define int long long
#define add push_back
int mod = (int)1e9+7;
using namespace std;
// Tips
// Try Easy Ones in Order
// For hard Ones if one questions repeated WA
// then Choose Next Question
// some time question is not always what it seems, some time you dont
// just need whole process, its all about ans, example char count, some
// time its not about steps but its about ans.
int GCD(int a,int b)
{
if(b>a)
{
return GCD(b,a);
}
if(b==0)
{
return a;
}
return GCD(b,a%b);
}
int pow1(int a, int b)
{
int x = 1;
while(b)
{
if (b & 1)
{
x = (x * a) % mod;
}
a = (a * a) % mod;
b = b >> 1;
}
return x;
}
int pow2(int a, int b)
{
int one=1;
int x = one;
while(b)
{
if (b & one)
{
x = (x * a);
}
a = (a * a);
b = b >>one;
}
return x;
}
int max3(int a, int b, int c)
{
if (a >= b && a >= c)
{
return a;
}
if (b >= a && b >= c)
{
return b;
}
return c;
}
int min3(int a, int b, int c)
{
if (a <= b && a <= c)
{
return a;
}
if (b <= a && b <= c)
{
return b;
}
return c;
}
int nc2(int n)
{
int d=(n*(n-1))/2;
return d;
}
int maxar(int ar[], int n)
{
int k = ar[0];
for (int i = 1; i < n; i++)
{
if (k < ar[i])
{
k = ar[i];
}
}
return k;
}
int minar(int ar[],int n)
{
int k=ar[0];
for(int i=1;i<n;i++)
{
if(ar[i]<k)
{
k=ar[i];
}
}
return k;
}
void swap(int *a, int *b)
{
int c = *a;
*a = *b;
*b = c;
}
void yes()
{
cout << "Yes\n";
}
void no()
{
cout << "No\n";
}
int mulmod(int a, int b, int m)//It returns true if number is prime otherwise false
{
int x = 0,y = a % m;
while (b > 0) {
if (b % 2 == 1) {
x = (x + y) % m;
}
y = (y * 2) % m;
b /= 2;
}
return x % m;
}
int modulo(int base, int e, int m) {
int x = 1;
int y = base;
while (e > 0) {
if (e % 2 == 1)
x = (x * y) % m;
y = (y * y) % m;
e = e / 2;
}
return x % m;
}
bool Miller(int p, int iteration) {
if (p < 2) {
return false;
}
if (p != 2 && p % 2==0) {
return false;
}
int s = p - 1;
while (s % 2 == 0) {
s /= 2;
}
for (int i = 0; i < iteration; i++) {
int a = rand() % (p - 1) + 1, temp = s;
int mod = modulo(a, temp, p);
while (temp != p - 1 && mod != 1 && mod != p - 1) {
mod = mulmod(mod, mod, p);
temp *= 2;
}
if (mod != p - 1 && temp % 2 == 0) {
return false;
}
}
return true;
}
int XOR(int n)
{
if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;
return 0;
}
const int N=1e6;
vector<int>spf(N+1,1);
void solve(int t1)
{
int n,k;
cin>>n>>k;
string s;
cin>>s;
int o=0,z=0;
for(char i:s)
{
if(i=='1')
{
o++;
}
else
{
z++;
}
}
if(o==0)
{
cout<<s<<"\n";
return;
}
else if(z==0)
{
for(int i=0;i<n;i++)
{
cout<<"0";
}cout<<"\n";
return;
}
vector<int>f(n),b(n),dis(n);
int prevz=-1,prevo=-1;
for(int i=0;i<n;i++)
{
if(s[i]=='1')
{
if(prevz==-1)
{
f[i]=n+1;
}
else
{
f[i]=i-prevz;
}
prevo=i;
}
else
{
if(prevo==-1)
{
f[i]=n+1;
}
else
{
f[i]=i-prevo;
}
prevz=i;
}
}
prevz=-1,prevo=-1;
for(int i=n-1;i>=0;i--)
{
if(s[i]=='1')
{
if(prevz==-1)
{
b[i]=n+1;
}
else
{
b[i]=prevz-i;
}
prevo=i;
}
else
{
if(prevo==-1)
{
b[i]=n+1;
}
else
{
b[i]=prevo-i;
}
prevz=i;
}
}
for(int i=0;i<n;i++)
{
dis[i]=min(f[i],b[i]);
}
for(int i=0;i<n;i++)
{
if(s[i]=='1')
{
int d=dis[i];
if(d>k)
{
cout<<"0";
}
else
{
int dif=d-k;
if(dif&1)
{
cout<<"1";
}
else
{
cout<<"0";
}
}
}
else
{
int d=dis[i];
if(d>k)
{
cout<<"0";
}
else
{
int dif=d-k;
if(dif&1)
{
cout<<"0";
}
else
{
cout<<"1";
}
}
}
}
cout<<"\n";
}
/* FOR STRINGS WHOLE LINE INPUT UISNG
string s;
getline(cin,s)+;
*/
/* IF AMOUNT OF DATA IS UNKNOWN THEN
while(cin>>x)
{
// CODE
}
*/
/* RANGE OF INT
-2 power 31 to 2 power 31 -1
RANGE OF LONG LONG
power 63
*/
// x=(x+m)%m;
// to compare double
/* if(abs(a-b)<1e-9)
{
equal
}
*/
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
for(int i=1;i<=t;i++)
{
solve(i);
}
}
/*
1
7
248 496 781 86 859 868 821
*/Alternative Sufferings CodeChef Solution in PYTH 3
for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
t = [0]*n
for i in range(n):
if s[i] == '0':
continue
t[i] = 0
if i > 0 and s[i-1] == '0':
t[i-1] = 1
if i+1 < n and s[i+1] == '0':
t[i+1] = 1
k -= 1
dist = [n+1]*n
prv = -1
for i in range(n):
if t[i] == 1:
prv = i
if prv != -1:
dist[i] = i - prv
prv = -1
for i in reversed(range(n)):
if t[i] == 1:
prv = i
if prv != -1:
dist[i] = min(dist[i], prv - i)
ans = ''
for i in range(n):
first = dist[i]
if first == n+1 or first > k:
ans += '0'
else:
if (k-first)%2 == 0:
ans += '1'
else:
ans += '0'
print(ans)
Alternative Sufferings 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
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int n = sc.nextInt();
int k = sc.nextInt();
String s = sc.next();
int [] left = new int[n];
int [] right = new int[n];
int one = -1,zero = -1;
for(int i = 0;i < n;i++){
if(s.charAt(i) == '0'){
left[i] = one;
zero = i;
}else{
left[i] = zero;
one = i;
}
}
one = -1;
zero = -1;
for(int i = n-1;i >= 0;i--){
if(s.charAt(i) == '0'){
right[i] = one;
zero = i;
}else{
right[i] = zero;
one = i;
}
}
StringBuilder str = new StringBuilder();
for(int i = 0;i < n;i++){
int l = left[i] == -1? Integer.MAX_VALUE:i - left[i];
int r = right[i] == -1? Integer.MAX_VALUE:right[i] - i;
int m = Math.min(l,r);
int k0 = k;
if(s.charAt(i) == '0'){
if(k0 < m){
str.append('0');
}else{
k0 -= m;
if(k0 % 2 == 0){
str.append('1');
}else{
str.append('0');
}
}
}else{
k0--;
if(k0 < m){
str.append('0');
}else{
k0 -= m;
if(k0 % 2 == 0){
str.append('1');
}else{
str.append('0');
}
}
}
}
System.out.println(str);
}
}
}Alternative Sufferings CodeChef Solution in PYPY 3
test=int(input())
while test:
n,k=map(int,input().split())
s=input()
s="x"+s+"x"
t=[0]*(n+2)
a=[0]*n
k-=1
for i in range(n+2):
t[i]=s[i]
for i in range(1,n+1):
if s[i]=="1":
t[i]="0"
if s[i-1]=="0":
t[i-1]="1"
if s[i+1]=="0":
t[i+1]="1"
s=t[1:n+1]
temp=float('inf')
for i in range(n):
if s[i]=="1":
temp=0
a[i]=temp
temp+=1
temp=float('inf')
for i in range(n-1,-1,-1):
if s[i]=="1":
temp=0
a[i]=min(a[i],temp)
temp+=1
for i in range(n):
if a[i]>k:
print("0",end="",sep="")
elif (k-a[i])%2==0:
print("1",end="",sep="")
else:
print("0",end="",sep="")
print()
test-=1Alternative Sufferings CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
var buf bytes.Buffer
tc := readNum(reader)
for tc > 0 {
tc--
_, k := readTwoNums(reader)
s := readString(reader)
res := solve(s, k)
buf.WriteString(fmt.Sprintf("%s\n", res))
}
fmt.Print(buf.String())
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' || s[i] == '\r' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
const INF = 1 << 30
func solve(s string, k int) string {
buf := []byte(s)
n := len(buf)
var cnt int
for i := 0; i < n; i++ {
cnt += int(buf[i] - '0')
}
if cnt == 0 {
// all 0, no change
return s
}
if cnt == n {
return all_zero(n)
}
for i := 0; i < n; i++ {
if s[i] == '1' {
buf[i] = '0'
if i > 0 && s[i-1] == '0' {
buf[i-1] = '1'
}
if i+1 < n && s[i+1] == '0' {
buf[i+1] = '1'
}
}
}
k--
if k == 0 {
return string(buf)
}
left := make([]int, n)
for i := 0; i < n; i++ {
if buf[i] == '1' {
left[i] = i
} else if i > 0 {
left[i] = left[i-1]
} else {
left[i] = -1
}
}
right := make([]int, n)
for i := n - 1; i >= 0; i-- {
if buf[i] == '1' {
right[i] = i
} else if i+1 < n {
right[i] = right[i+1]
} else {
right[i] = n
}
}
for i := 0; i < n; i++ {
first := INF
if buf[i] == '1' {
first = 0
} else {
if left[i] >= 0 {
first = i - left[i]
}
if right[i] < n {
first = min(first, right[i]-i)
}
}
if first > k {
buf[i] = '0'
} else {
if (k-first)&1 == 0 {
buf[i] = '1'
} else {
buf[i] = '0'
}
}
}
return string(buf)
}
func min(a, b int) int {
if a <= b {
return a
}
return b
}
func all_zero(n int) string {
buf := make([]byte, n)
for i := 0; i < n; i++ {
buf[i] = '0'
}
return string(buf)
}Alternative Sufferings CodeChef Solution Review:
In our experience, we suggest you solve this Alternative Sufferings CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Alternative Sufferings CodeChef Solution.
Conclusion:
I hope this Alternative Sufferings CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
