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
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;
}
Getting RE(SIGSEGV)
whats wrong with the below code?
https://www.codechef.com/viewsolution/48240530
odd