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
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’
The key to solve this problem is to make the first observation
#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.
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
/*
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;
}
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
The logic I used is below:
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
got it bro
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.
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
#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<<' ';
}
}
}
}
oh.got it bro
This looks interesting, can you explain your code a little?