MODEQUAL - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author & Editorialist: Vichitr Gandas
Tester: Aryan Choudhary

DIFFICULTY:

EASY

PREREQUISITES:

Basic Maths

PROBLEM:

You are given N non-negative integers A_1,A_2,\ldots,A_N. You are allowed to perform following operation any number of times:

  • Choose any valid index i (1≤i≤N) and a positive integer M>0 and replace A_i with A_i \mod M.
  • M does not need to be same between different operations.

Find the minimum number of operations to make all the array elements equal.

EXPLANATION

Upper Bound: Upper bound on answer is N by taking mod with 1 we can make all the numbers 0.

Idea: We will try to make all the numbers equal to minimum because we can’t increase by taking mod. Also we can convert any number X to K only if X> 2 \cdot K . So just check if we can make all the numbers equal to minimum.
Also if we can convert a number X to minimum then we can also convert all the numbers >=X. Hence checking for only second minimum number is enough.

Find the count of numbers cnt which are not equal to minimum. If above suggested condition holds for second minimum number then ans is cnt. Otherwise ans is N.

TIME COMPLEXITY:

O(N) per test case

SOLUTIONS:

Setter & Editorialist's Solution
/*
 * @author: vichitr
 * @date: 25th July 2021
 */

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);

void solve() {
	int n; cin >> n;
	int A[n];
	for (int i = 0; i < n; i++)
		cin >> A[i];

	sort(A, A + n);
	int i = 0;
	while (i < n and A[i] == A[0])
		i++;
	int cnt = i;
	while (i < n) {
		if (A[i] <= A[0] * 2) {
			cout << n << '\n';
			return;
		}
		i++;
	}
	cout << n - cnt << '\n';
}

signed main() {
	fast;

#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	int t = 1;
	cin >> t;
	for (int tt = 1; tt <= t; tt++) {
		// cout << "Case #" << tt << ": ";
		solve();
	}
	return 0;
}
Tester's Solution
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

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,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

lli gcd(lli x,lli y){
    if(x==0||y==0)
        return x+y;
    return __gcd(x,y);
}

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,1e4);
lli sumN=0;
while(T--)
{
    n=readIntLn(1,1e5);
    sumN+=n;
    assert(sumN<=1e6);
    a=readVectorInt(n,0,2e9);

    auto solve=[&](){
        lli mn=INF,cnt=0;
        for(auto x:a){
            if(x>mn)
                continue;
            if(x!=mn)
                cnt=0;
            cnt++;
            mn=min(mn,x);
        }

        for(auto x:a){
            if(mn<x&&x<=2*mn)
                return n;
        }
        return n-cnt;
    };
    cout<<solve()<<endl;
}   aryanc403();
    readEOF();
    return 0;
}

If you have other approaches or solutions, let’s discuss in comments.If you have other approaches or solutions, let’s discuss in comments.

5 Likes

#include<bits/stdc++.h>
#define endl “\n”
#define INF 1e10
#define ll long long int

using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t; cin >> t;
while(t--)
{
	int n; cin >> n;
	map<ll, ll> m;
	ll val, minval = INF;
	for(int i = 0; i < n; i++)
	{
		cin >> val;
		m[val]++;
		minval = min(val, minval);
	}
	ll gcdval = 0;
	for(auto a : m)
		gcdval = __gcd(a.first - minval, gcdval);
	if(gcdval != 1)cout << n - m[minval] << endl;
	else cout << n << endl;
}
return 0;

}

I think this should work properly. But could you help me to understand why is it not working?

Did you consider the case where A_i = 0.

1 Like

man , how do you approach , do you have strong mathematical background ? .
can you give some problems to practice that require observaions like this problem
@vichitr please guide . :pray:

Do you have a proof?

@sonukumar03xt Haha, maths was my favourite but only until I studied the Engineering Mathematics in first semester of my college. :stuck_out_tongue:

Story behind coming up with this problem:
There was a need to balance the Cook-Off problem set and Ashish asked me if I can help. Hence I randomly created a problem which turned out to be interesting so I shared it with Ashish and he liked it. Though original problem was harder version of it and I don’t have any solution of that version yet. But we modified to a solve-able version which can fit in as an easy. As a result I created this problem.

This problem is more about thinking and kinda ad-hoc. So I don’t have any practice problems. You can try ad-hoc problems which are usually like this.

My approach to solve this problem was:

  • Find an upper bound for answer.
  • Make observations if we can make any progress from upper bound.
  • Observed that we can convert a number to X if its > 2 \cdot X.
  • Used the observation to find the final answer.
1 Like

You are the best.
I appreciate your help so much

1 Like

Can u provide the proof for this X>2⋅K ?

try to calculate x mod a for every ‘a’ less than ‘x’ you will come to conclusion that it always results the numbers in the range [0 ,ceil(x/2) - 1].
Which proves that if we want to convert ‘X’ to ‘K’ then ‘K’ must lie in range 0 to ceil(X/2)-1 or X>2*K

I know this is quite late to talk about this but I read the editorial and wrote this Solution: 49906326 | CodeChef.

void solve(int testcase) {
  int n;
  cin >> n;
  vi a(n);
  iter(x, a) cin >> x;

  if (n < 2) {
    cout << n << '\n';
    return;
  }

  sort(ALL(a));
  int first_min = a[0];
  int fm_count = count(ALL(a), first_min);

  if (fm_count == n) {
    cout << 0 << '\n';
    return;
  }

  int second_min = a[fm_count];

  if (second_min <= 2 * first_min) {
    cout << n << '\n';
    return;
  }

  cout << n - fm_count << '\n';
}

This didn’t seem to work so I just copy pasted the editorialist’s solution. Solution: 49906536 | CodeChef.

void solve(int testcase) {
  int n;
  cin >> n;
  vi a(n);
  iter(x, a) cin >> x;

  sort(ALL(a));

  int i = 0;
  while (i < n && a[i] == a[0]) ++i;

  int j = i;
  while (i < n) {
    if (a[i] <= a[0] * 2) {
      cout << n << '\n';
      return;
    }
    ++i;
  }

  cout << n - j << '\n';
}

This didn’t seem to work either. Any idea what I’m doing wrong?

I think you missed this line. Integer overflow is main reason for WA.

1 Like