BITBLEND - Editorial

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. :pray:

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

@akshitm16 i did not find any case for solution :expressionless:
https://www.codechef.com/viewsolution/57872965