XYSTR - Editorial

PROBLEM LINK:

Contest Link

Author: Raja Vardhan Reddy
Tester: Felipe Mota
Editorialist: Rajarshi Basu

DIFFICULTY:

Simple

PREREQUISITES:

Implementation, logic

PROBLEM:

There are N \leq 10^5 students standing in a row and numbered 1 through N from left to right. You are given a string S with length N, where for each valid i, the i-th character of S is ‘x’ if the i-th student is a girl or ‘y’ if this student is a boy. Students standing next to each other in the row are friends.

The students are asked to form pairs for a dance competition. Each pair must consist of a boy and a girl. Two students can only form a pair if they are friends. Each student can only be part of at most one pair. What is the maximum number of pairs that can be formed?

EXPLANATION:

We do a linear traversal of the array, and whenever we see that the i^{th} and (i+1)^{th} characters are different, we increase our counter cnt by 1, and skip over that next element to ensure that the chosen pairs are all disjoint. Choosing pairs in this greedy approach is optimal, since our chosen pairs are more “towards the left” and thereby freeing up more space “towards the right” to choose possible more pairs.

I write those in quotes, since they are not mathematically rigorous statements but more of the intuition and the “feel” for the solution.

Since we just do a linear traversal, the time complexity is O(n)

SOLUTIONS:

Setter's Code
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
 
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t,t1;
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin>>t;
	while(t--){
		int i,ans=0,prev_taken=0;
		string s;
		cin>>s;
		//cout<<rng()<<endl;
		prev_taken=0;
		f(i,1,s.length()){
			if(prev_taken){
				prev_taken=0;
				continue;
			}
			if(s[i]!=s[i-1]){
				ans++;
				prev_taken=1;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
} 
 
Tester's Code
t = int(raw_input())
while t > 0:
    s = raw_input()
    p, res = 0, 0
    while p + 1 < len(s):
        if s[p] != s[p + 1]:
            res += 1
            p += 1
        p += 1
    print res
    t -= 1 
Editorialist's Code
#include <stdio.h>     
#include <stdlib.h>    
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
#define ld long double
//#define int ll
//#define int short
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<iii,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
//#define mp make_pair
#define vv vector
#define endl '\n'
 
using namespace std;
 
const int MAXN = 200*1000 + 5;
const int MAXT = 263*1000;
 
void solve(){
	string s;
	cin >> s;
	int n = s.size();
	int dp[n];
	dp[0] = 0;
	FOR(i,n){
		if(i == 0)continue;
		else if(i == 1){
			if(s[i] == s[i-1])dp[1] = 0;
			else dp[1] = 1;
		}else{
			if(s[i] == s[i-1]){
				dp[i] = dp[i-1];
			}else{
				dp[i] = max(dp[i-1],dp[i-2]+1);
			}
		}
	}
	cout << dp[n-1] << endl;
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--)solve();
	return 0;
} 

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

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

int main() {
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        int l = s.size(),ans = 0;
        
        for(int i=0;i<l;i+=2){
            if(s[i]!=s[i+1])ans++;
        }
        
        cout << ans << '\n';
    }
}

Can you tell what is the problem with this approach?

public static void main(String []args){

    int t,ans;
    char temp, last='z';
    
    Scanner scan= new Scanner(System.in);    
    t = scan.nextInt(); 
    scan.nextLine();
    
    while(t-- > 0) {
        ans=0;
        
        String str= scan.nextLine(); 
        
        for(int i=0; i< str.length(); i+=1){
            
            temp = str.charAt(i);
            if(temp == 'x') {
                if(last == 'y') {
                    ans++;
                    last = 'z';
                } else {
                    last= 'x';
                }
            } else {
                if(last == 'x') {
                    ans++;
                    last = 'z';
                } else {
                    last = 'y';
                }
            }   
        }
        
        System.out.println(ans);
    }
 }

cakewalk

Don’t know why its has DP tag.

DP is overkilling, when simple traversal is suffucient

i j k l m:

if (i,j) forms a pair we can expect (k,l) to form other pair
else next probable pair would be (j,k)

https://www.codechef.com/viewsolution/34196632

1 Like

June long challenge editorial beginner friendly video explanation and code

Delicious cake (CONTAIN) : https://youtu.be/tXD2yEVA0pM
Tom and jerry (EOEO) : https://youtu.be/ZWI5n0Ogir0
Even matrix (EVENM) : https://youtu.be/KA8WoO7jCg8

Python Solution Using ASCII Value of x and y:

T = int(input())
for _ in range(T):
	s = str(input())
	p = i =0
	while i < len(s)-1:
		if abs(ord(s[i])-ord(s[i+1])) == 1:
			p += 1
			i += 1
		i += 1
	print(p)
1 Like

can anyone explain this in setter’s code?
if(prev_taken){
prev_taken=0;
continue;
}

prev_taken is a flag.

if this is active means the last element is already paired with the second last element otherwise we can choose to pair with it.

last ???

video Explanation>>>>

PYTHON code of chef and string…
for _ in range(int(input())):
arr = input()
count = 0
i = 0
while i < len(arr)-1:
if (arr[i] == “x” and arr[i+1] == “y”) or (arr[i]==“y” and arr[i+1]==“x”):
count+=1
i+=1
i+=1
print (count)

2 Likes

char last = ‘z’ declare in while loop
because every test cases last will be initially ‘z’ but in your case last may be ‘x’, ‘y’ or ‘z’

Thanks

bro is anything wrong with dis concept

Can you tell me the problem in this code?
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–){
string s;
cin>>s;
int flag=0,flag1=0,result,len;
len=s.length();
for(int i=0;i<len;i++){
if(s[i]==‘x’)
flag++;
if(s[i]==‘y’)
flag1++;
}
result=min(flag,flag1);
cout<<result<<endl;
}
return 0;
}

Can you please tell me what’s the problem in this approach it’s giving a WA-
https://www.codechef.com/viewsolution/34515962

Test string “xxxxyyyy”, your code gives 4. Expected is 1.

Also you have to put a “\n” or endl after printing the result. (For every question, on any CP website).

[EDIT]: Also, flags are generally used to check some condition. If your variable is counting something it’s better to name it countx and county. Naming it flag is not wrong, but it’s just easier for others to understand your code if you use the conventional meaning of flag and count.

1 Like

Ok, I understood what the problem with my code is and I have also made flag as countx and county. Thank you so much.

1 Like

Can you please also check what’s wrong in this code? I get the correct outputs during custom run but it shows runtime error
https://www.codechef.com/viewsolution/34532525