Codeforces round 608#division 2 problem of past contest?

i could’t found what logic should i use for this ,it was a beautiful math question .pls share your views .one more thig how to develop good logic thinking for solving questions like this…

problem link:- https://codeforces.com/contest/1271/problem/B

Which Problem?

sorry forgot to provide link .now its there check it out

Let w=number of ‘W’ and b=number of ‘B’

  1. If w and b are both odd print -1
  2. Else iterate from 0 to length of str and print(i) if str[i]==‘B’(or ‘W’, either way its correct)

The key to solve this problem is to make the first observation

3 Likes
#include <bits/stdc++.h>

using namespace std;

#define ull unsigned long long

#define P (int)(1e9+7)

#define ceil(x, y) (x%y==0? (x/y) : (x/y+1))

#define FOR(i, N) for(int i = 0; i < N; ++i)

#define FOR1(i, N) for(int i = 1; i <= N; ++i)

#define vi vector <int>

#define pii pair <int, int>

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

#define mset(a, v) memset(a, v, sizeof(a))

#define all(v) (v).begin(), (v).end()

#define INF 2e9

#define EPS 1e-9

int main() {

    // your code goes here

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int T=1;

    //cin>>T;

    while(T-->0)

    {

        int N; cin >> N;

        string s; cin >> s;

        vi ans;

        for(int i = 1; i+1 < s.length(); i++){

            

            if(s[i] == s[i-1]) continue;

            ans.pb(i+1);

            if(s[i] == 'B') s[i] = 'W';

            else s[i] = 'B';

            if(s[i+1] == 'B') s[i+1] = 'W';

            else s[i+1] = 'B';

        }

        

        if(s[N-1] != s[N-2]){ //if by simulation we weren't able to convert

            //there are 2 types of cases

            //if length of string is even, the substring excluding last character is odd and thus can't be transformed into last character

            if(N % 2 == 0){

                cout << -1; return 0;

            }

            else{ //the substring excluding last character is even in length and it's so easy to transform it into last character

                for(int i = 0; i <= s.length()-2; i+=2) ans.pb(i+1);

            }

        }

        cout << ans.size()<<'\n';

        for(int v : ans) cout << v << " ";

    }

    return 0;

}

Does codeforces publish editorials of problems from past contests?

Simply try to do what is asked by simulation. When you flip, the character kind of travels to the right. In the end either all characters will be converted to same letter or 1 will be left out as rightmost. Key observation is the edge case when simulation is not able to make the conversion; but still answer exists due to being able to convert to the other character. Refer comments.
PS I am also waiting for official editorial for better explanation.

1 Like

there is 3N time we can suffle if loop is from 0 to length of string then it will not do AC on input which require upto 3N suffles

I just solved it, here is my solution, i’ve added comments so u can understand :slightly_smiling_face:

/*
	Author : SummerPark ~ 2019	
*/

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

int32_t main(){
    int n;cin>>n;
    string a;cin>>a;
    // Count of B and W
    int B_count=0,W_count=0;


    // We'll count occurance of B and W in string
    for(int i=0;i<n;i++){
    	if(a[i]=='B'){
    		B_count++;
    	}else{
    		W_count++;
    	}
    }

    // Now a small observation, if both are odd at the same time
    // you can't really make 'em equal.
    // You can prove this by mathematical inducution ;)
    
    if(B_count&1 && W_count&1){
    	cout<<-1<<endl;
    }else{
        
        //This is to store my result of indexes
    	vector<int> res;
    	
    	// So here is my exhaustive approach
    	// If B is less in number, I'll try to make everything B
    	
    	if(B_count<W_count){
    	    
    	    // So i try to make everything B
    		for(int i=0;i<n;i++){
    			if(a[i]=='W' && a[i+1]=='B'){
    				res.push_back(i+1);
    				swap(a[i],a[i+1]);
    			}else if(a[i]=='W' && a[i+1]=='W'){
    				res.push_back(i+1);
    				a[i]='B';
    				a[i+1]='B';
    			}
    		}
    		
    		// Now it's possible that i might have a single W left
    		// like in WBW kind of case
    		// So i'll first check if the string has single characters only
    		
    		bool doit=true;
    		if(count(a.begin(),a.end(),'W')==0){
    			doit=false;
    		}
    		
    		// If not, i'll try to make everything W this time
    		for(int i=0;i<n && doit;i++){
    			if(a[i]=='B' && a[i+1]=='W'){
    				res.push_back(i+1);
    				swap(a[i],a[i+1]);
    			}else if(a[i]=='B' && a[i+1]=='B'){
    				res.push_back(i+1);
    				a[i]='W';
    				a[i+1]='W';
    			}
    		}
    	}else{
    	    
    	    // I'll follow  the same approach, if i have less W
    		for(int i=0;i<n;i++){
    			if(a[i]=='B' && a[i+1]=='W'){
    				res.push_back(i+1);
    				swap(a[i],a[i+1]);
    			}else if(a[i]=='B' && a[i+1]=='B'){
    				res.push_back(i+1);
    				a[i]='W';
    				a[i+1]='W';
    			}
    		}
    		bool doit=true;
    		if(count(a.begin(),a.end(),'B')==0){
    			doit=false;
    		}
    		for(int i=0;i<n && doit;i++){
    			if(a[i]=='W' && a[i+1]=='B'){
    				res.push_back(i+1);
    				swap(a[i],a[i+1]);
    			}else if(a[i]=='W' && a[i+1]=='W'){
    				res.push_back(i+1);
    				a[i]='B';
    				a[i+1]='B';
    			}
    		}
    	}
    	cout<<res.size()<<endl;
    	for(int x:res){
    	    cout<<x<<" ";
    	}
    	cout<<endl;
    }
    return 0;
}

4 Likes

yep there is ,but i could’t got it from there so i asked it here

comments helped a lot in quickly understanding it thanks bro

1 Like

The logic I used is below:

  1. If both B and W counts are odd there is no solution; ELSE move to 2
  • Case 1: when count of W is odd and B is even - flip all BW in string i.e. str[i] = ‘B’ and str[i+1] = ‘W’ to str[i] = ‘W’ and str[i+1] = ‘B’; and the BB to WW

  • Case 2: when count of B is odd and W is even - flip all WB in string i.e. str[i] = ‘W’ and str[i+1] = ‘B’ to str[i] = ‘B’ and str[i+1] = ‘W’ and the WW to BB

  • Case 3: If both count of W and B is even, and W is less than B’s count; flip the WB’s and WW (same as case 1); else if B’s count is greater flip BW and BB

this can be done much simpler way, but hope you get it!
My contest submission

1 Like

got it bro :smiley:

Great approach!!!

This worked for me. A simple approach and a short code.

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	string s;
	cin >> n >> s;
	int arr[n], tmp[n] = {};
    for(int i = 0 ; i  < n ; i++) arr[i] = (s[i]=='B');
    for(int j = 0 ;  j < 2 ; j++) {
    	for(int i = 0 ; i  < n ; i++)  tmp[i]=arr[i];
    	vector<int> res;
    	for(int i = 0 ; i  < n-1 ; i++)
			if(tmp[i]!=j)
				tmp[i+1]^=1 , res.pb(i+1);
		if(tmp[n-1]==j) {
			cout << res.size() << endl;
			for(auto i : res) cout << i << ' ' ;
			return 0;
		}
    }
    cout << -1 ;
}

Yes @anon2040365
Herein I have taken initial array of 1’s(B) and 0’s(W). Next we know that at the end either all elements are 0 or 1. For each case we run a loop from 1 to n and wherever the said element isn’t what we desire it to be, we flip the next element and the given element (not done actively in code as it doesn’t effect the solution). If at the end the last element is what we desired the array to be, we are done. Else no solution exists and hence we must print -1.
@anon73162591 Hope it helps.

2 Likes

Wow thats so elegant and clean.
You just bruteforced what the task wanted to do.
No thinking of cases odd, even…

These type of problems cannot be solved through practice . The only key is observation skills and ability to come to a claim with a proof of correctness and is only possible if you are good in math.

Btw here is my approach :slight_smile:

#include<iostream>
#include<bits/stdc++.h>
#define int long long
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int32_t main()
{
	fast;
	int n;
	cin >> n;
	string s;
	cin >> s;
	int b = 0,w = 0;
	for(int i = 0 ; i < n ; i++ ){
		if(s[i]=='B'){
			b++;
		}
		else
		{
			w++;
		}
	}
	if(b%2==1 && w%2==1){
		cout<<"-1";
	}
	else
	{
		char x = s[0];
		vector<int>res;
		for(int i = 1 ; i < n-1 ; i++ ){
			if(s[i]!=x){
				res.push_back(i+1);
				s[i] = x;
				if(s[i+1]=='B'){
					s[i+1]='W';
				}
				else{
					s[i+1]='B';
				}
			}
		}
		set<char>ss;
		for(int i = 0 ; i < n ; i++ ){
			ss.insert(s[i]);
		}
		if(ss.size()==1){
			cout<<res.size()<<'\n';
			for(auto p : res){
				cout<<p<<' ';
			}
		}
		else
		{
			for(int i = 0 ; i < n-1 ; i+=2 ){
				res.push_back(i+1);
			}
			cout<<res.size()<<'\n';
			for(auto p : res){
				cout<<p<<' ';
			}
		}
	}
}
1 Like

oh.got it bro

1 Like

This looks interesting, can you explain your code a little? :slightly_smiling_face: