ZEBRA-Editorial

iscsi · September 19, 2021, 9:17am

PROBLEM LINK:

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

Author1: Ashish Gupta
Author2: Utkarsh Gupta
Tester: Anshu Garg
Editorialist: Istvan Nagy

DIFFICULTY:

SIMPLE

PREREQUISITES:

Parity

PROBLEM:

There’s a zebra crossing appearing in the middle of nowhere with N blocks in it. The colors of the zebra crossing is represented by a binary string S, where S_i is 1 if the i-th block from the left is white, and 0 if the block is black.

Chef really wants to play with the zebra crossing. Although the given zebra crossing might not have alternate black and white blocks, Chef wants to follow the alternating white-black color pattern while crossing it.

Initially, Chef stands at block 1. Chef has to jump exactly K times, and in each jump he has to move forward and jump to a different color than that previously occupied by Chef. More formally, suppose that Chef is currently at block i and wants to jump to block j then following conditions should hold:

i < j
S_i \neq S_j

Output the farthest block Chef can reach with exactly K jumps. If Chef cannot jump exactly K times, output -1.

EXPLANATION

Observation: When the colors of the zebra crossing changes less than K times there is no solution.

On every step the Chef has to step on the opposite color as he currently stays on, so
from the information of the starting color and K, we can define the color where Chef will step on the K-th step:

\text{the block color after the $K$-step} = \begin{cases} \text{white if starting color is black and K is odd}\\ \text{white if starting color is white and K is even}\\ \text{black if starting color is white and K is odd}\\ \text{black if starting color is black and K is even} \\ \end{cases}

To calculate the farthest reachable block with exactly K jump we just need to find the farthest appropriate block on the zebra crossing, which has the same color as the above equation gives.

TIME COMPLEXITY:

O(|S|) per test case

SOLUTIONS:

Setter 1's Solution

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 1e5 + 5;
 
int n, k;
string s;
 
int32_t main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
		cin >> n >> k;
		cin >> s;
		int ans = 0;
		int ct = 0;
		for(int i = 1; i < n; i++)
		{
			if(s[i] != s[i - 1])
				ct++;
		}
		if(ct >= k)
		{
			for(int i = n - 1; i >= 0; i--)
			{
				if(k % 2 && s[i] != s[0])
				{
					cout << i + 1 << endl;
					break;
				}
				else if(!(k % 2) && s[i] == s[0])
				{
					cout << i + 1 << endl;
					break;
				}
			}
		}
		else
			cout << -1 << endl;
	}
	return 0;
}

Setter 2's Solution

//Utkarsh.25dec
#include <bits/stdc++.h>
#include
#include
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector
#define vs vector
#define vc vector
#define vl vector
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<’ ‘<<’=‘<<’ ‘<<x<<’\n’
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val) no. of elements strictly less than val
// s.find_by_order(i) itertor to ith element (0 indexed)
typedef vector<vector> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=resa%mod;a=aa%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector adj[N];
void solve()
{
ll n,k;
cin>>n>>k;
string s;
cin>>s;
s=‘$’+s;
int curr=1;
int i;
for(i=2;i<=n;i++)
{
if(k==1)
break;
if(s[i]!=s[curr])
{
curr=i;
k–;
if(k==1)
break;
}
}
if(i==n+1)
{
cout<<-1<<‘\n’;
return;
}
for(int i=n;i>curr;i–)
{
if(s[i]!=s[curr])
{
cout<<i<<‘\n’;
return;
}
}
cout<<-1<<‘\n’;
}
int 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=1;
cin>>T;
int t=0;
while(t++<T)
{
//cout<<“Case #”<<t<<“:”<<’ ';
solve();
//cout<<‘\n’;
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << “ms\n”;
}

Tester's Solution

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

#define ll              long long 
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll>
#define pii             pair<int,int>
#define ld              long double

const int M = 1000000007;
const int MM = 998244353;

template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }

#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2351
#endif

long long readInt(long long l,long long r,char end){
    long long x = 0;
    int cnt = 0;
    int first =-1;
    bool is_neg = false;
    while(true) {
        char g = getchar();
        if(g == '-') {
            assert(first == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if(cnt == 0) {
                first = g - '0';
            }
            ++cnt;
            assert(first != 0 || cnt == 1);
            assert(first != 0 || is_neg == false);
            
            assert(!(cnt > 19 || (cnt == 19 && first > 1)));
        } 
        else if(g == end) {
            if(is_neg) {
                x = -x;
            }
            assert(l <= x && x <= r);
            return x;
        } 
        else {
            assert(false);
        }
    }
}
string readString(int l,int r,char end){
    string ret = "";
    int cnt = 0;
    while(true) {
        char g = getchar();
        assert(g != -1);
        if(g == end) {
            break;
        }
        ++cnt;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}

int sumN = 0;
int _runtimeTerror_()
{
    int N, K;
    N = readIntSp(2, 1000), K = readIntLn(1, N);
    sumN += N;
    assert(sumN <= 5e5);
    string s = readStringLn(N, N);
    for(auto &j:s) {
        assert(j == '0' || j == '1');
    }
    auto rev = [&](char c) {
        return c ^ '0' ^ '1';
    };
    int last = s[0];
    for(int i=1;i<N;++i) {
        if(K == 0) {
            break;
        }
        if(s[i] == rev(last)) {
            last = rev(last);
            --K;
        }
    }
    if(K > 0) {
        cout << "-1\n";
    }
    else {
        for(int i=N-1;i>=0;--i) {
            if(s[i] == last) {
                cout << i + 1 << "\n";
                return 0;
            }
        }
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef runSieve
        sieve();
    #endif
    #ifdef NCR
        initialize();
    #endif
    int TESTS = 1;
    TESTS = readIntLn(1,100000);
    //cin >> TESTS;
    while(TESTS--)
        _runtimeTerror_();
    // assert(getchar() == -1);
    return 0;
}

Editorialist's Solution

#include
#include
#include
#include
#include
#include
#include

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv)
{
int T, N, K;
string s;
cin >> T;
forn(tc, T)
{
cin >> N >> K;
cin >> s;
string sc = s;
sc.erase(unique(all(sc)), sc.end());
if (sc.size() <= K)
{
printf(“-1\n”);
continue;
}
char c = sc[K];
ford(i, s.size())
{
if (s[i] == c)
{
printf(“%d\n”, i + 1);
break;
}
}
}
return 0;
}

If you have other approaches or solutions, let’s discuss in comments.

ajeet_1606 · September 20, 2021, 3:17am

The question statement wasn’t clear to me. What the “jump” word really meant?? Like if there are alternating colors chef can easily move. when the jump is needed when two adjacent blocks have same color. Can anyone explain the question please?

nj_code · September 20, 2021, 3:35am

Solution: 51326043 | CodeChef
Why my solution is giving WA ? Is there any specific test case to check ?

strange_boy_0 · September 20, 2021, 5:35am

The jump word meant like you can jump to the alternating colors.if suppose you are standing at the White Block then you can jump to Black Block similarly the other way round is also possible.The main crux is that you have to jump EXACTLY K TIMES FOLLOWING THIS FASHION:
there were only two condition:

while jumping you can’t move back you must move forward.You even cannot remain in the same position.
other condition is that you have to jump in alternate colors(black → white or white → black)

so chef must follow these two conditions along with exactly k jumps.So we have to find the maximum block till which chef can reach.
INTERESTING NOTE:there is not limit on which how much he can jump.

ayush29azad · September 20, 2021, 6:41am

Can someone tell on which test case my code is failing ???

#include <iostream>
using namespace std;
#include<bits/stdc++.h>
typedef long long ll;

int main() 
{
ios_base::sync_with_stdio(false);
    cin.tie(NULL);

ll t;
cin>>t;
while(t--)
{
ll n,k;
cin>>n>>k;
string s;
cin>>s;
char prev = s[0];
ll cnt=0;
for(ll i=1;i<s.size();i++)
{
    if(prev != s[i])
    {
        cnt++;
        prev = s[i];
    }
   
}
if(cnt<k)
{
        cout<<-1;
}
else
{

ll fone=-1;
ll fzero=-1;
for(int i=n-1;i>=0;i--)
{
    if(s[i]=='1' && fone==-1)
    {
        fone =i+1;
    }
   else if(s[i]=='0' && fzero==-1)
    {
        fzero =i+1;
    }
   else if(fone!=-1 && fzero!=-1)
   {
       break;
   }
   
}

if(k%2==0)  // k even hai
{
   char x = s[0];
   if(x=='1')  
   {
       cout<<fone;
   }
   else
   {
        cout<<fzero;
   }
    
}
else
{
    ll x = s[0];
   if(x=='1')
   {
         cout<<fzero;
   }
   else
   {
        cout<<fone;
   }
}
cout<<"\n";
}
}
}

architk13 · September 20, 2021, 6:43am

#include<iostream>
#include<string>
using namespace std;

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n, k;
		cin >> n >> k;
		string s;
		cin >> s;
		int index = 1;
		char prev = s[0];
		while(k > 1 && index < s.length())
		{
			if(s[index] != prev)
			{
				prev = s[index];
				k--;
			}
			index++;
		}
		int ans;
		if(k == 1)
		{
			
			for(int i = s.length() - 1; i >=0; i--)
			{
				if(s[i] != prev)
				{
					ans = i + 1;
					k--;
					break;
				}
			}
			if(k == 0)
			{
				cout << ans << endl;
			}
			else
			{
				cout << "-1" << endl;
			}
		}
		else
		{
			cout << "-1" << endl;
			continue;
		}
	}
}

getting WA in this code can anyone tell me whats wrong in this code?

ajitg25 · September 20, 2021, 6:48am

This was my approach hope it helps!!

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define ll long long

int main() {
	// your code goes here
	ll test,N,k;
	string s;
	cin>>test;
	while(test--){
	    vector<int> vec;
	    cin>>N>>k;
	    cin>>s;
	    ll length = s.size();
	    int c;
	   // cout<<s[0]<<" "<<s[s.size()-1]<<endl;
	    for (int i=length;i>0;i--){
	        if (s[i]!=s[i-1]){
	            vec.push_back(i);
	        }
	    }
	   // for(auto itr = vec.begin();itr!=vec.end();itr++){
	   //     cout<<*itr<<" ";
	   // }cout<<endl;
	   // cout<<k<< "   "<<vec.size()<<endl;
	    if (vec.size()<=k){
	        cout<<-1<<endl;
	        continue;
	    }
	    if (s[0]==s[length-1]){
	        if (k%2==0){
	            cout<<vec[0]<<endl;
	        }
	        else{
	            cout<<vec[1]<<endl;
	        }
	    }
	    else{
	        if (k%2==0){
	            cout<<vec[1]<<endl;
	        }
	        else{
	            cout<<vec[0]<<endl;
	        }
	    }
	}
	return 0;
}

prashar32 · September 20, 2021, 9:48am

Is there were some wrong test cases?

ajeet_1606 · September 20, 2021, 10:14am

But k is the limit??

prashar32 · September 20, 2021, 2:30pm

What’s wrong in my solution ?
I think testcases were wrong …
Solution
@ashishgup @utkarsh_25dec @anshugarg12 @iscsi

ayush29azad · September 20, 2021, 4:06pm

1
6 2
000001

-1 should be the answer , your code gives 1.

prashar32 · September 20, 2021, 4:19pm

My solution is also giving -1. And that’s the correct answer

ayush29azad · September 20, 2021, 4:34pm

Prashar, this one is giving 2 it should be 6
1
6 1
100000

strange_boy_0 · September 21, 2021, 9:36am

what i really meant was that chef could jump much greater than what we could jump!! I was just kidding . That was it!! Don’t take it seriously.Sorry for conveying it the wrong way.

joy1654 · September 23, 2021, 6:49pm

import java.util.ArrayList;
import java.util.Scanner;

public class ZEBRA {
    public static void main(String[] args) {

        Scanner Input = new Scanner(System.in);
        int Test = Input.nextInt();
        while (Test > 0) {
            int String_Len = Input.nextInt();
            int K_Jumps = Input.nextInt();
            String string = Input.next();
            char digit = string.charAt(0);
            digit = (digit == '0' ? '1' : '0');
            System.out.println(Dp_Optimize(1, K_Jumps, 0, string, digit));
            Test--;
        }

    }

    private static int Dp_Optimize(int Src_end, int k_jumps, int Count, String string, char digit) {
        if (Count == k_jumps) {
            return Src_end;
        } else if (Count > k_jumps || Src_end == string.length()) {
            return -1;
        } else {
            for (int i = string.length() - 1; i >= Src_end; i--) {
                if (digit == string.charAt(i)) {
                    digit = (digit == '0' ? '1' : '0');
                   // Count+=1;
                    int temp = Dp_Optimize(i + 1, k_jumps, Count+1 , string, digit);
                    if (temp != -1) {
                        return temp;
                    }
                    digit = (digit == '0' ? '1' : '0');
                   // Count -= 1;
                }

            }
            return -1;
        }
    }

}

// I used Recursion , Find a test case where my solution fails//``

anon31734764 · May 24, 2022, 7:28am

** Can anyone tell me whats wrong in this code?**

#include<bits/stdc++.h>

#define nline "\n"
#define ll long long
#define pb push_back
#define umap unordered_map
#define mod  1000000007

using namespace std;

//function

int far(string a,char d){
	int n = a.size()-1;
	while(n>0){
		if(d == a[n]){
			return n+1;
		}
		n--;
	}
	return -1;
}

//function end

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

//PreStart



//end
    int t;cin>>t;
    while(t--){
//start

    int n,k;cin>>n>>k;
    string s;cin>>s;
    char d = s[0];
    if(k%2){
    	if(s[0] == '1') d = '0';
    	else d = '1';
    }
    // calculating farthest point according to the pairity of k
    int f = far(s,d);
    if(f == -1) {
    	cout<<-1<<nline;
    	continue;
    }
    //calculating the minimum zeros and ones required for exactly k jumps
    int z = k/2,o = k/2;
    if(s[0]=='1' and k%2==1) z++;
    if(s[0]=='0' and k%2==1) o++; 
    for (int i = 1; i <= f; ++i)
    {
    	if(s[i] == '1') o--;
    	else z--;
    }
    // if zeros and ones are equal or more than thr required than print farthest point else print -1
    if(z<=0 and o<=0) cout<<f<<nline;
    else cout<<-1<<nline;

//end
    }

	return 0;
}