Colorful Holi - Editorial

About the Problem

Setter(s) Vichitr Gandas
Tester(s) Aswin Ashok
Difficulty Cakewalk
Topics Adhoc
Practice Link
Contest Link

Solution Idea

Let the number of distinct colors used be d . So we will have n-d houses to be recolored. Also let there be z distinct colors which appear from the range [x,y] so we can use (y-x+1-z) left our colors from the range [x,y]. We have only k number of moves allowed. Hence total number of houses which can be recolored would be r = min(n-d, y-x+1-z, k) . So maximum number of distinct colors after recoloring would be r + d.

Complexity Analysis:

  • Time Complexity: O(nlogn)
  • Space Complexity: O(n)

Codes

Setter's Code
/***************************************************

@author: vichitr
Compiled On: 27 Mar 2021

*****************************************************/
#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define int long long
// #define double long double
#define pb push_back
#define pf pop_front
#define mp make_pair
#define ip pair<int, int>
#define F first
#define S second

#define loop(i,n) for(int i=0;i<n;i++)
#define loops(i,s,n) for(int i=s;i<=n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ip, null_type, less_equal<ip>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

const ll MOD = 1e9+7;
const ll SZ = 107;
const ll N = 1e5+7;
const ll M = 1e4+7;

ll pwr(ll x, ll y)
{
    ll r = 1LL;
    while(y)
    {
        if(y&1)
            r = (r * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return r;
}

int inv(int x)
{
    return pwr(x, MOD-2ll);
}

int sum_n = 0;

void solve(){
    int n, x, y, k; cin>>n>>x>>y>>k;
    assert(n >= 1 and n <= 1e5);
    assert(x >= 0 and x <=y and y <= 1e9);
    assert(k >=0 and k <= n);
    int c[n];
    loop(i, n) cin>>c[i];
    int ans = 0, p = 0;
    map<int, bool> M, C;

    for(int i=0;i<n;i++){
        if(c[i] < x or c[i] > y){
            if(C[c[i]])
                p++;
            else{
                C[c[i]] = 1;
            }
        }
        else if(M[c[i]])
            continue;
        else{
            M[c[i]] = 1;
        }
    }
    p = n - M.size() - C.size();
    ans = min({p, k, (int)(y-x+1-M.size())});
    ans += M.size() + C.size();
    cout << ans << '\n';
    assert(ans > 0 and ans <= n);
}

signed main()
{
    // fast;
    
    int t=1;
    cin >>t;
    assert(t <= 1e5);
    for(int i=1;i<=t;i++)
    {
        // cout<<"Case #"<<i<<": ";
        solve();
        
    }
    return 0;
}
Setter's Code 2
/***************************************************

@author: vichitr
Compiled On: 27 Mar 2021

*****************************************************/
#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define int long long
// #define double long double
#define pb push_back
#define pf pop_front
#define mp make_pair
#define ip pair<int, int>
#define F first
#define S second

#define loop(i,n) for(int i=0;i<n;i++)
#define loops(i,s,n) for(int i=s;i<=n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ip, null_type, less_equal<ip>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

const ll MOD = 1e9+7;
const ll SZ = 107;
const ll N = 1e5+7;
const ll M = 1e4+7;

ll pwr(ll x, ll y)
{
    ll r = 1LL;
    while(y)
    {
        if(y&1)
            r = (r * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return r;
}

int inv(int x)
{
    return pwr(x, MOD-2ll);
}

int sum_n = 0;

void solve(){
    int n, x, y, k; cin>>n>>x>>y>>k;
    assert(n >= 1 and n <= 1e5);
    assert(x >= 0 and x <=y and y <= 1e9);
    assert(k >=0 and k <= n);
    sum_n += n;
    assert(sum_n <= 5e5);
    int c[n];
    loop(i, n) cin>>c[i];
    int ans = 0, p = 0;
    set<int> v1, v2;
    for(int i=0;i<n;i++){
        if(c[i]>=x and c[i] <= y)
            v1.insert(c[i]);
        else
            v2.insert(c[i]);
    }
    ans = min({(int)(n-v1.size()-v2.size()), k, (int)(y-x+1-v1.size())});
    ans += v1.size() + v2.size();
    
    cout << ans << '\n';
    assert(ans > 0 and ans <= n);
}

signed main()
{
    // fast;
    
    int t=1;
    cin >>t;
    assert(t <= 1e5);
    for(int i=1;i<=t;i++)
    {
        // cout<<"Case #"<<i<<": ";
        solve();
        
    }
    return 0;
}
Tester's Code
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n,x,y,k;
    cin>>n>>x>>y>>k;
    set<int> dxy;
    set<int> d;
    for(int i=0;i<n;++i)
    {
        int c;
        cin>>c;
        if(c>=x and c<=y)
            dxy.insert(c);
        d.insert(c);
    }
    int options = y-x+1-dxy.size();
    int total_dup = n - d.size();
    int total_to_change = min(k,total_dup);
    int ans = d.size() + min(total_to_change,options);
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--)
        solve();
}

If you have used any other approach, share your approach in comments!
If you have any doubts, ask them in comments!

2 Likes

i didn’t understand this line :
Also let there be ‘z’ distinct colors which appear from the range [x,y] so we can use (y-x+1-z) left colors from the range [x,y].
pls explain this

There are total of y-x+1 colors in the range [x, y]. And out of which z are already used hence left out colors which can be used are total - already used which is y-x+1-z.

2 Likes