ZEBRA-Editorial

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
  1. //Utkarsh.25dec
  2. #include <bits/stdc++.h>
  3. #include
  4. #include
  5. #define ll long long int
  6. #define ull unsigned long long int
  7. #define pb push_back
  8. #define mp make_pair
  9. #define mod 1000000007
  10. #define rep(i,n) for(ll i=0;i<n;i++)
  11. #define loop(i,a,b) for(ll i=a;i<=b;i++)
  12. #define vi vector
  13. #define vs vector
  14. #define vc vector
  15. #define vl vector
  16. #define all(c) (c).begin(),(c).end()
  17. #define max3(a,b,c) max(max(a,b),c)
  18. #define min3(a,b,c) min(min(a,b),c)
  19. #define deb(x) cerr<<#x<<’ ‘<<’=’<<’ ‘<<x<<’\n’
  20. using namespace std;
  21. #include <ext/pb_ds/assoc_container.hpp>
  22. #include <ext/pb_ds/tree_policy.hpp>
  23. using namespace __gnu_pbds;
  24. #define ordered_set tree<int, null_type,less, rb_tree_tag,tree_order_statistics_node_update>
  25. // ordered_set s ; s.order_of_key(val) no. of elements strictly less than val
  26. // s.find_by_order(i) itertor to ith element (0 indexed)
  27. typedef vector<vector> matrix;
  28. 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;}
  29. ll modInverse(ll a){return power(a,mod-2);}
  30. const int N=500023;
  31. bool vis[N];
  32. vector adj[N];
  33. void solve()
  34. {
  35. ll n,k;
  36. cin>>n>>k;
  37. string s;
  38. cin>>s;
  39. s=’$’+s;
  40. int curr=1;
  41. int i;
  42. for(i=2;i<=n;i++)
  43. {
  44. if(k==1)
  45. break;
  46. if(s[i]!=s[curr])
  47. {
  48. curr=i;
  49. k–;
  50. if(k==1)
  51. break;
  52. }
  53. }
  54. if(i==n+1)
  55. {
  56. cout<<-1<<’\n’;
  57. return;
  58. }
  59. for(int i=n;i>curr;i–)
  60. {
  61. if(s[i]!=s[curr])
  62. {
  63. cout<<i<<’\n’;
  64. return;
  65. }
  66. }
  67. cout<<-1<<’\n’;
  68. }
  69. int main()
  70. {
  71. #ifndef ONLINE_JUDGE
  72. freopen(“input.txt”, “r”, stdin);
  73. freopen(“output.txt”, “w”, stdout);
  74. #endif
  75. ios_base::sync_with_stdio(false);
  76. cin.tie(NULL);
  77. int T=1;
  78. cin>>T;
  79. int t=0;
  80. while(t++<T)
  81. {
  82. //cout<<“Case #”<<t<<":"<<’ ';
  83. solve();
  84. //cout<<’\n’;
  85. }
  86. cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << “ms\n”;
  87. }
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.

4 Likes

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?

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

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:

  1. while jumping you can’t move back you must move forward.You even cannot remain in the same position.
  2. 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. :laughing:

1 Like

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";
}
}
}
1 Like
#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?

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;
}
1 Like

Is there were some wrong test cases?

But k is the limit??

1 Like

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

1
6 2
000001

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

1 Like

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

1 Like

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

1 Like

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.:grin:

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//``