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.
It fails on this-
1
5
1 1 1 0 1
Link to your submission?
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
can anyone tell whats wrong with this code
its showing TLE
#include
using namespace std;
int parityCheck(int N, int arr[])
{
bool c = false, d = true;
for (int j = 0; j < (N - 1); j++)
{
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()
{
int T;
scanf("%d", &T);
while (T–)
{
int N, C, G = 0;
scanf("%d", &N);
int arr[N], I[N], J[N];
for (int i = 0; i < N; i++)
{
scanf("%d", &arr[i]);
}
C = parityCheck(N, arr);
if (C == 1)
{
printf("%d\n", G);
}
else
{
for (int i = 0; i < N; i++)
{
if (i != (N - i - 1))
{
G++;
arr[i] = (arr[i] ^ arr[N - i - 1]);
I[i] = i + 1;
J[i] = (N - i);
C = parityCheck(N, arr);
if (C == 1)
{
break;
}
}
}
if (C == 1)
{
printf("%d\n", G);
for (int k = 0; k < G; k++)
{
printf("%d %d\n", I[k], J[k]);
}
}
else
{
printf("-1\n");
}
}
}
return 0;
}
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.
thanks i got it
thank you so much sir due to your help i was able to code it successfully and removed all extra coinciding cases.
And my code was submitted successfully thanks a lot with all due respect. 
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}
I made changes to my getIdx() function and got AC, Thanks @suman_18733097
changes
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 s,string t)
{
int oIdx = -1;
for(int i = 0;i < s.size();i++)
{
if(s[i] == t[i] && s[i] == '1')
oIdx = 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;
int idx = getIdx(str,ansStr);
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;
}
1 Like
