I did my code according to the editorial, still the wrong answer. If anyone could debug my code or provide some corner test cases, I would be grateful. Here, is my code:
My Code
// Problem: Bitwise BlendCodeChef: Practical coding for everyone https://cpeditor.org )
#include <bits/stdc++.h>
#define ll long long#define dd double#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define ld long double#define rep(i,a,b) for(ll i=a;i<b; i++)#define ff first#define ss second#define mp make_pair#define vl vector#define mll map<ll,ll>#define setbits(x) __builtin_popcountll(x)#define zrbits(x) __builtin_ctzll(x)#define pb push_back#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()#define ps(x,y) fixed<<setprecision(y)<<x#define mk(arr,n,type) type *arr=new type[n];
const ll mod=1e9+7;
#define yes cout<<“YES\n”;#define no cout<<“NO\n”;
void solve(){
int main(){
pika_1
February 7, 2022, 1:22pm
20
Consider this input
1
6
1 1 2 5 2 4
Your code outputs -1, while it’s definitely possible to make the sequence \text{tasty} .
1 Like
Sorry, but I didn’t get it. I mean what is meant by order here. In any order we do operations, won’t I get the same sequence at last? Can you be a little more specific.
Try this-
1
9
1 0 1 1 0 1 0 1 1
Also i \neq j for a valid operation.
If the whole sequence is odd … we just need to make the numbers at odd indices even so just chose one odd number at an even index and xor the odd indexed numbers with that number … so minimum number of operations would be n/2.
1 Like
dark_11
February 7, 2022, 2:53pm
27
can anyone tell whats wrong with this code
#include
if (((arr[j] & arr[j + 1]) % 2) != ((arr[j] | arr[j + 1]) % 2))
{
c = true;
}
else
{
d = false;
}
}
if (c && d)
{
return 1;
}
else
{
return -1;
}
}
int main()
Any one can run my code and tell me why my code is note accepted
#include <bits/stdc++.h>
using namespace std;
string str1(100009, '0');
string str2(100009, '0');
int main() {
for (int i = 0;i < 100000;i++) {
if (i % 2 == 0)
str1[i] = '1';
else
str2[i] = '1';
}
int t;cin >> t;
while (t--) {
int n;cin >> n;
int flag1 = 0;
vector<int> j;
string str(n, '0');
for (int i = 0;i < n;i++) {
int x;cin >> x;
if (x & 1) {
flag1 = 1;
str[i] = '1';
j.push_back(i);
}
}
int m1 = 0, m2 = 0;
map<int, int> mp1;
map<int, int> mp2;
if (flag1 == 1)
for (int i = 0;i < n;i++) {
if (str[i] != str1[i]) {
m1++;
if (i != j[0])
mp1[i] = j[0];
else if (i != j[1] && j.size() > 1)
mp1[i] = j[1];
}
if (str[i] != str2[i]) {
m2++;
if (i != j[0])
mp2[i] = j[0];
else if (i != j[1] && j.size() > 1)
mp2[i] = j[1];
}
}
if (flag1 == 1) {
if (m1 >= m2) {
cout << mp2.size() << endl;
for (auto& it : mp2)
cout << it.first + 1 << " " << it.second + 1 << endl;
}
else
{
cout << mp1.size() << endl;
for (auto& it : mp1)
cout << it.first + 1 << " " << it.second + 1 << endl;
}
}
else cout << -1 << endl;
}
return 0;
}
Consider this input:
1
7
0 5 4 3 3 6 1
Your Output
3
5 7
6 7
7 5
Performing those operations:
After Op1: [0, 5, 4, 3, 2, 6, 1]
After Op2: [0, 5, 4, 3, 2, 7, 1]
After Op3: [0, 5, 4, 3, 2, 7, 3]
After performing all the operations, the resulting sequence is [0, 5, 4, 3, 2, 7, 3]. This is not \text{tasty} since parity(A_6 \& A_7) == parity(A_6 | A_7) .
1 Like
The same goes for you too.
Consider this input instead.
1
7
3 2 0 5 3 1 2
Your Output
3
1 4
2 1
5 1
After performing the operations, the sequence will be [6, 4, 0, 5, 5, 1, 2].
This is not \text{tasty} since parity(A_1\&A_2) == parity(A_1 | A_2) , parity(A_2\&A_3) == parity(A_2 | A_3) , parity(A_4\&A_5) == parity(A_4 | A_5) and parity(A_5\&A_6) == parity(A_5 | A_6) .
Oh understood it. Thanks.
thank you so much sir due to your help i was able to code it successfully and removed all extra coinciding cases.
2 Likes
C++ solution
#include <bits/stdc++.h>
using namespace std;
void print(vector<pair<int,int>> &op)
{
cout << op.size() << endl;
for(auto &it : op)
{
cout << it.first+1 << " " << it.second+1 << "\n";
}
}
void solve()
{
int n;
cin >> n;
int arr[n], oddPos = -1, evenPos = -1;
bool oddPresent = false, odd = false, even = false;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
if(arr[i] & 1)
{
oddPresent = true;
// check odd element at odd position
// why we are checking only odd element?
// because, to convert odd -> even (or) even -> odd, we need to xor with odd element only
if(i & 1)
{
odd = true;
oddPos = i;
}
// check odd element at odd position
else{
even = true;
evenPos = i;
}
}
}
if(!oddPresent)
{
cout << "-1";
return;
}
vector<pair<int,int>> oddEven, evenOdd;
// checking odd, even, odd, even, ..
if(odd)
{
for(int i = 0; i < n; i++)
{
// If cur element not at correct position
// even position, odd ele
if((!(i&1) && arr[i] & 1) ||
// odd position, even ele
(i&1 && !(arr[i] & 1)))
oddEven.push_back({i, oddPos});
}
}
// checking even, odd, even, odd
if(even)
{
for(int i = 0; i < n; i++)
{
// even position, even ele
if((!(i&1) && !(arr[i] & 1)) ||
// odd position, odd ele
(i&1 && (arr[i] & 1)))
evenOdd.push_back({i, evenPos});
}
}
int n1 = oddEven.size(), n2 = evenOdd.size();
if(odd && even)
{
if(n1 < n2) print(oddEven);
else print(evenOdd);
}
else if(odd) print(oddEven);
else print(evenOdd);
}
int main() {
int t;
cin >> t;
while(t--)
{
solve();
cout << endl;
}
return 0;
}
Hi, I spent quite a lot time trying to get this solution submitted. But it seems to be failing for all test c ases. Can anyone help me with the test case I am missing. The code can be found here .
I basically converted the input into a parity string, i.e. 0110 what ever according to the input. Now I compare them with the two possible answer strings 0101… and 1010… the one having minimum difference will give the minimum answer. I am getting WA, pls help
My code :
string ansString(int n,bool flg)
{
string ans;
for(int i = 0;i < n;i++)
{
if(i%2)
{
if(flg) ans.push_back('1');
else ans.push_back('0');
}
else
{
if(flg) ans.push_back('0');
else ans.push_back('1');
}
}
return ans;
}
int getDiff(string s,string t)
{
int cnt = 0;
for(int i = 0;i < s.size();i++)
{
if(s[i] != t[i]) cnt++;
}
return cnt;
}
// flg -> 01
int getIdx(string str,bool flg)
{
int oIdx = -1,eIdx = -1;
for(int i = 0;i < str.size()-1;i++)
if(str[i] != str[i+1])
{
if(flg)
{
if(str[i] == '0')
{
oIdx = i+1;
eIdx = i;
}
}
else
{
if(str[i] == '1')
{
oIdx = i;
eIdx = i+1;
}
}
i++;
}
return oIdx;
}
int main()
{
int t;
cin >> t;
while(t--)
{
ll n;
cin >> n;
ll arr[n];
string str = "";
int ocnt = 0, ecnt = 0;
for(int i = 0;i < n;i++)
{
cin >> arr[i];
arr[i] %= 2;
arr[i] ? ocnt++ : ecnt++;
str.push_back(arr[i] ? '1' : '0');
}
if(ecnt == n) cout << -1 << endl;
else
{
string s1 = ansString(n,1);
string s2 = ansString(n,0);
int a = getDiff(str,s1); //01
int b = getDiff(str,s2); //10
int ans = min(a,b);
string ansStr = ans == a ? s1 : s2;
bool flg = (ans == a);
int idx = getIdx(str,flg);
if(idx == -1) idx = getIdx(str,!flg);
if(ocnt == n)
{
for(int i = 0;i < n;i++)
if(ansStr[i] == str[i])
idx = i;
}
cout << ans << endl;
for(int i = 0;i < n;i++)
{
if(str[i] != ansStr[i])
cout << i+1 << " " << idx+1 << endl;
}
// cout << endl << flg << " " << str << endl;
}
}
return 0;
}
Consider this input:
1
6
8 2 6 7 1 4
Your output
3
1 4
3 4
4 2
The resulting sequence after performing moves is [15, 2, 1, 5, 1, 4], which is not \text{tasty}
Input
1
5
9 1 6 6 1
Your Output
2
2 2
3 2
Resulting sequence: [9, 0, 6, 6, 1] which is not \text{tasty}
