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
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:
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;
}
odd