UNONE - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Lakshay Jain
Tester: Felipe Mota
Editorialist: Aman Dwivedi

DIFFICULTY

Simple

PREREQUISITES

Observation

PROBLEM:

The ugliness of a string is defined as the count of two consecutive ones i.e. "11" in the given string. For example, the ugliness of string "10111" is 2.

You are given an array A of N integers and you have to find any ordering of the array such that the ugliness of the concatenated string of the binary representations of the integers (without leading zeros) is minimum.

EXPLANATION:

The first basic observation that we can draw is that if the count of two consecutive ones in number X is Y, then we won’t be able to decrease this count Y because no matter how we arrange the array these ones will always be together.

Now we have an array A of N integers. Let’s say Y_1,Y_2,\dots,Y_N be the count of two consecutive ones in A_1,A_2,\dots,A_N. Then

C_1 = \sum_{i=1}^{N} Y_i

So no matter how we arranges the array in which manner the count of two consecutive ones cannot be less than C_1.

Let us see the what happens during the concatenation of the numbers in binary representation. The count of two consecutive ones will increase in a case which is :

  • At index i we have a number whose least significant bit in binary representation is 1 and,
  • Index i+1 exists and we have a number whose most significant bit in binary representation is 1.

Since we are not considering leading zeroes, therefore the most significant bit of every number in binary representation is 1. Also, the numbers which have least significant bit set in binary representation are odd numbers. Hence we can reframe our conditions as:

  • At index i, we have an odd number and
  • Index i+1 exists.

Since our task is to reduce the count of two consecutive ones, hence our goal is to make any one of the conditions false.

As we are not allowed to change the number hence we won’t be able to make the first condition false. Odd numbers which were present in array A, will be also present at new array at some index i.

Let’s try to make the second condition false. We know that index i+1 exists for every index i of an array except the last index of an array. So if we put an odd number in index N of an array then index N+1 doesn’t exist therefore the count of two consecutive ones won’t increase.

Hence in optimal arrangement of array, index N of an array should be an odd number (if odd number is present in given array), as for this number the index i+1 doesn’t exists and hence the count will not increase. For the remaining odd numbers, no matter where we put them the count of two consecutive numbers will always increase,

If there are O odd number in an array then the count of two consecutive numbers in array which is optimally rearranged as discussed above is:

C = C_1 + (O-1)

We won’t be able to acheive the count less than C. Therefore in optimal arrangement we just need to ensure than index N of an array contains an odd number that’s it and we are done.

TIME COMPLEXITY:

O(N) per test case

SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    int odd = n-1;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if (a[i] & 1){
            odd = i;
        }
    }
    swap(a[odd], a[n-1]);
    for(int i = 0; i < n; i++){
        cout << a[i] << " ";
    }
    cout << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}

Tester
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);

			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = readIntLn(1, TEN(3));
	while(t--){
		int n = readIntLn(1, TEN(3));
		vector<int> a(n);
		for(int i = 0; i < n; i++){
			if(i + 1 < n) a[i] = readIntSp(1, TEN(9));
			else a[i] = readIntLn(1, TEN(9));
		}
		vector<vector<int>> stk(2);
		for(int i = 0; i < n; i++){
			stk[a[i]%2].push_back(a[i]);
		}
		vector<int> ans;
		for(int v : stk[0]) ans.push_back(v);
		for(int v : stk[1]) ans.push_back(v);
		for(int i = 0; i < n; i++)
			cout << ans[i] << " \n"[i + 1 == n];
	}
	return 0;
}

Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
  int n;
  cin>>n;

  int a[n];

  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    if(a[i]%2==0)
      a[i]*=-1;
  }   

  sort(a,a+n);

  for(int i=0;i<n;i++)
    cout<<abs(a[i])<<" ";
  cout<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}
3 Likes

Please provide the algo for unpleasant ones question. I have seen a solution which got AC.

The user just counted even and odd and printed even first then odd. But it does not satisfy me as every even number has a trailing zero which can differ the result if we make 2 vectors one odd and one even then sort even is ascending and odd in descending. Further , if no. of even elements are more then largest even element can be printed first then odd elements at even places.
I think this type of algorithm shuld be used why just print even first and odd at end.
Please clear my doubt.

just check 5 3 2. The answer should be 5 2 3 but according to solution answer is 2 5 3.

1 Like

both are correct
5 → 101
2 → 10
3 → 11

5 2 3 → 101 10 11 // ugliness= 2
2 5 3 → 10 101 11 // ugliness=2

3 Likes

Every no has the MSB set while odd numbers have the LSB set.
Ugliness can increase only if LSB of previous no is 1 which is only possible for odd numbers.
Hence, printing all even numbers first and then odd is always correct.

5 – 101
2 – 10
3 – 11
1010111 (for 2 5 3) has the same ugliness as 1011011 (for 5 2 3).
Therefore both are correct.

You can verify taking more cases I guess

Did anyone get AC with O(nlogn)?

What I did is count all trailing zeroes of each A[i] , and sort in decreasing order of trainling zeroes and just printed.

    lli n;
    cin>>n;
    lli a[n];
    scanarr(a,n);
    vpi vc;
    loop(i,n)
    {
        lli num = a[i];
        lli count=0;
        while(!(num & 1))
        {
            count++;
            num >>= 1;
        }
        vc.pb({count,a[i]});
    }
    
    sort(all(vc));
    reverse(all(vc));
    
    loop(i,n)
        cout<<vc[i].S<<" ";
    cout<<endl;
1 Like

HERE we know that ;
odd, even, odd, even,… pattern won’t work because
11 → 10 → 11 → 10 //ugliness = 4;
but ;
even, even, odd , odd pattern
10 ,10, 11, 11 // ugliness = 3
but why even, odd, even, odd pattern doesn’t work
10 , 11, 10, 11 // ugliness = 3
???

6 Likes

why even odd even odd … pattern of array didn’t work for this question?

2 Likes

I was also using this approach during the contest but now it is clear from the following example:
10 11 10 (even odd even) ugliness = 2
10 10 11 (even even odd) ugliness = 1

3 Likes

ROFL , u create N X N vector , there is no need

similarly as
[5,6,3]=10111011 ugliness=3
[3,6,5]=11110101 ugliness=3

You can make it work, if we do it in reverse order.
something like this.
so on :arrow_left: odd :arrow_left: even :arrow_left: odd :arrow_left: even :arrow_left: odd

while(even.size()!=0 || odd.size()!=0){
	if(odd.size()!=0){
		ans.push_front(odd[0]);
		odd.erase(odd.begin());
	}

	if(even.size()!=0){
		ans.push_front(even[0]);
		even.erase(even.begin());
	}
	
}
for(auto i:ans)
	cout<<i<<" ";
cout<<"\n";

Even odd works if u do it correctly:

https://www.codechef.com/viewsolution/48165344

Hey @cherry0697 , please help.

My Approach:
Sort the array based on the following comparator.

bool compare(int a, int b) {
    string bin_a = bin(a);
    string bin_b = bin(b);
    return count(bin_a + bin_b) < count(bin_b + bin_a);
}

where bin(int n) returns the binary representation of n and count(string s) returns the number of consecutive ones in s.

The Solution
#include <bits/stdc++.h>
using namespace std;

string bin(int n) {
	string b;
	while(n > 0) {
		b.push_back(n % 2 + '0');
		n >>= 1;
	}
	reverse(b.begin(), b.end());
	return b;
}

int count(string& s) {
	int c = 0;
	for(int i = 0; i < s.length() - 1; i++) {
		if(s[i] == s[i + 1] && s[i] == '1') {
			c++;
		}
	}
	return c;
}

bool compare(int a, int b) {
	string bin_a = bin(a);
	string bin_b = bin(b);
	string c1 = bin_a + bin_b;
	string c2 = bin_b + bin_a;
	return count(c1) < count(c2);
}

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto& x: a) {
		cin >> x;
	}
	sort(a.begin(), a.end(), compare);
	for(int i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t = 0;
	cin >> t;
	for(int test = 0; test < t; test++) {
		solve();
	}
	return 0;
}

Unfortunately, the verdict is TLE. I couldn’t come up with a better approach during contest. Can you spot the reason for TLE?

why is this approach not working
no of even >= no of odd
even …even…even…odd…even…odd…even…odd
if no of odd >no of even:
odd…even…odd…even…odd…odd…odd…

please provide a test case where it fails
https://www.codechef.com/viewsolution/48213759

bool cmp(const int &a, const int &b) {
return __builtin_ctz(a) < __builtin_ctz(b);
}
void solve() {

int n;
cin >> n;

vector<ll>v(n);

for (int i = 0; i < n; i++) {
    cin >> v[i];
}

sort(v.begin(), v.end(), cmp);

for (int i = v.size() - 1; i >= 0; i--) {
    cout << v[i];
    if (i != 0) {
        cout << " ";
    }
}
cout << "\n";

}

1 Like

what about this case
1 - 1
3 - 11
7 - 111
2 - 10

as per the solution (even_list+odd_list) it should be 2,1,3,7 = 10 1 11 111 # ugliness = 5
but one optimal solution is 1,3,2,7 = 1 11 10 111 # ugliness = 4

bro ugliness is 5
"1 1" 1 1 0 1 1 1 # pair 1
1 “1 1” 1 0 1 1 1 # pair 2
1 1 “11” 0 1 1 1 # pair 3
1 11 10 “11"1 # pair 4
1 11 10 1
"11”
# pair 5

1 Like

Print Even first and then odd will also work with out sorting it with is O(n) solution why to make O(nlogN) solution.
int main()
{

fio;
ll t;
cin>>t;

while(t--){
    ll n;
    cin>>n;
    vector<ll> even,odd;
    
    
    for(ll i=0;i<n;i++){
        ll x;cin>>x;
        
        if(x%2==1)odd.push_back(x);
        else even.push_back(x);
        
       
    }
     for(auto x: even) cout<<x<<" ";
        for(auto x: odd) cout<<x<<" ";
        
        cout nl;
}

}

why is it showing run time error
can anyone explain

#include<bits/stdc++.h>

using namespace std;
#define int long long
int32_t main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];

    if(a[n-1]%2!=0)
    {
        for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
        cout<<endl;
    }
    else
    {
        int p;
        for(int i=0;i<n;i++)
        {
            if(a[i]%2!=0)
             {
                 p=i;
                 break;
             }
        }
        
        int temp=a[p];
        a[p]=a[n-1];
        a[n-1]=temp;
        
        for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
        cout<<endl;
        
        
    }
}
return 0;

}