CHEFWM - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Pranav Reddy
Testers: Lavish Gupta, Tejas Pandey
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY

PREREQUISITES:

Prime factorization

PROBLEM:

There is rectangular screen in coordinate plane from (0, 0) to (N, M). We need to divide the rectangle into vertical columns with equal size with borders as integer coordinates. Then each column is further divided into windows with the following properties:

  • For a column, the size of each window must be same and must have borders as integer coordinates.

  • There must be atleast two windows in a single column.

  • No two windows in different columns have the same y coordinate for horizontal edges, except for the borders of the screen.

We need to output the maximum number of columns that can be created.

EXPLANATION:

  • Let there be a total of tot columns in the final answer with the number of windows in each column as c_1, c_2 \dots c_{tot}.

  • To ensure the horizontal edges of two windows of different columns i and j have different y coordinates, we need to have gcd(c_i, c_j) =1.

  • We can easily prove this by contradiction: Let gcd(c_i, c_j) =k \gt 1. Then, c_i = k \cdot p and c_j = k\cdot q for some positive integers p and q. Now, window in column i has size s_i = \frac{M}{k \cdot p} and window in column j has size s_j = \frac{M}{k \cdot q}. It can be observed clearly that p^{th} window from the bottom in column i has a horizontal edge which will have the same y coordinate the q^{th} window from the bottom in column j. In other words, p \cdot s_i = q \cdot s_j = \frac{M}{k} \lt M. We arrived at a contradiction because our assumption is wrong. Therefore, gcd(c_i, c_j) must be equal to 1.

  • Now our main goal is to maximize the value of tot. This can be realised by first doing the prime factorization of M. This can be done in O(\sqrt M) by the classic prime factorization method. Let there be a total of y primes and let M = p_1^{x_1} \cdot p_2^{x_2} \dots p_y^{x_y}.

  • The maximum value of tot we can have is y with possible c_1 = p_1, c_2=p_2 \dots c_y = p_y. Why? Suppose tot \gt y. Then atleast two columns i and j will have gcd(c_i, c_j) \neq 1. This is because of pigeon-hole principle. If tot \gt y and we only have y primes available and every column i must have c_i \gt 1, atleast one prime must be repeated in two columns which results in their gcd greater than 1. Therefore, tot = y is the maximum possible.

  • We are now left to find the maximum number less than tot which is divisible by N for the borders of columns to have integer coordinates. This can be simply done by iterating over i from 1 to tot and choosing maximum i for which N is divisible by i.

TIME COMPLEXITY:

O(\sqrt M) for each test case.

SOLUTION:

Editorialist's solution

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

int main()
{
      int tests;
      cin >> tests;
      while (tests--)
      {
            int n, m;
            cin >> n >> m;

            int primes = 0;
            for (int i = 2; i * i <= m; i++)
            {
                  if (m % i == 0)
                  {
                        primes++;
                        while (m % i == 0)
                        {
                              m /= i;
                        }
                  }
            }
            if (m > 1)
                  primes++;

            int ans = 0;
            for (int i = 1; i <= primes; i++)
            {
                  if (n % i == 0)
                  {
                        ans = i;
                  }
            }

            cout << ans << endl;
      }
      return 0;
}

Setter's solution
// Official Statement at https://www.notion.so/ChefWM-679a2962e13c4597b8bb69f934fc70f8

#include <cstdlib>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace std::chrono;

#define int long long
#define ld long double
#define sz(c) ((int)c.size())
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int inf = 1e18;

const int mod = 1e9 + 7;
const int mod2 = 998244353;

int distinctPrimeFactors(int n) {
    int answer=0;
    vector<int> primeFactors;

    while (n % 2 == 0) {
        primeFactors.push_back(2);
        n = n/2;
    }
 
    for(int i=3;i*i<=n;i+=2) {
        while(n%i==0) {
            primeFactors.push_back(i);
            n = n/i;
        }
    }
 
    if (n>2) primeFactors.push_back(n);
    set<int> distinctFactors;

    for(int x : primeFactors) distinctFactors.insert(x);
    return distinctFactors.size();
}

signed main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    auto startTime = high_resolution_clock::now();
    
    int tt;
    cin>>tt;
    while(tt--) {
        int n,m;
        cin>>n>>m;

        int distinctFactors = distinctPrimeFactors(m);
        if(distinctFactors==0) {
            cout<<0<<endl;
            continue;
        }

        vector<int> divisorsOfN;

        for(int i=1;i*i<=n;i++) {
            if(i*i==n) divisorsOfN.push_back(i);
            else if(n%i==0) {
                divisorsOfN.push_back(i);
                divisorsOfN.push_back(n/i);
            }
        }
        sort(divisorsOfN.begin(), divisorsOfN.end());

        int ans=0;
        for(int i=1;i<(int)divisorsOfN.size();i++) {
            ans = divisorsOfN[i-1];
            if(divisorsOfN[i]>distinctFactors) break;
        }

        if(divisorsOfN[divisorsOfN.size()-1] <= distinctFactors) ans = divisorsOfN[divisorsOfN.size()-1];

        cout<<ans<<endl;
    }

    auto stopTime = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stopTime - startTime);
    //cout<<"Program ran for "<<(ld)duration.count()/1e6<<" "<<"seconds"<<endl;
}


Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
 
/*
------------------------Input Checker----------------------------------
*/
 
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;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            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,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 500;
const int MAX_N = 1000000000;
const int MAX_Q = 100000;
const int MAX_val = 1000000000;
const int MAX_SUM_N = 200000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll p = 1000000007;
ll sum_nk = 0 ;

int get_cnt_prime(int n)
{
    int cnt = 0 ;
    for(int i = 2 ; i*i <= n ; i++)
    {
        if(n%i == 0)
        {
            cnt++ ;
            while(n%i == 0)
                n /= i ;
        }
    }
    if(n != 1)
        cnt++ ;
    return cnt ;
}

void solve()
{   
    int n = readIntSp(1 , MAX_N) ;
    int m = readIntLn(1 , MAX_N) ;
    int num = get_cnt_prime(m) ;

    if(num == 0)
        cout << 0 << '\n' ;
    else
    {
        for(int i = num ; i > 0 ; i--)
        {
            if(n%i == 0)
            {
                cerr << "min_divisible = " << i << endl ;
                cout << i << '\n' ;
                return ;
            }
        }
    }
    return ;

}
 
signed main()
{
    //fast;
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
    
    int t = 1;
    
    t = readIntLn(1,MAX_T);

    for(int i=1;i<=t;i++)
    {    
        solve() ;
    }
    
    assert(getchar() == -1);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    // cerr<<"Sum of lengths : " << sum_n << '\n';
    // cerr<<"Maximum length : " << max_n << '\n';
    // cerr << "Sum o f product : " << sum_nk << '\n' ;
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}

Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

4 Likes

https://www.codechef.com/viewsolution/55879825
why this is wrong?

1 Like

can someone explain the solution that went viral in last 1 hour(submission went to the moon) -_-
this: Solution: 55905735 | CodeChef
and this: Solution: 55905435 | CodeChef

3 Likes

Could you please let me that y the answer will always be equal to k and not less than that?
having gcd(ci,cj) == 1 is great however, I think we need to a have their lcm(ci,cj) >=m.
For instance if my ci == 2 && cj == 3 and m > 6 then your solution will not work.

I think the answer k is indeed correct but your solution is incomplete.

5 Likes
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define SCD(t) scanf("%d",&t)
#define SCLD(t) scanf("%ld",&t)
#define SCLLD(t) scanf("%lld",&t)
#define SCF(t) scanf("%f",&t)
#define SCLF(t) scanf("%lf",&t)
#define PRD(t) printf("%d\n",t)
#define PRLD(t) printf("%ld\n",t)
#define PRLLD(t) printf("%lld\n",t)
#define PRC(t) printf("%c\n",t)
#define PRS(t) printf("%s\n",t)
#define PRF(t) printf("%f",t)S
#define PRLF(t) printf("%lf",t)
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
//typedef map<int,int> MPII;
//typedef set<int> SETI;
//typedef multiset<int> MSETI;
typedef long int li;
typedef unsigned long int uli;
typedef long long int ll;
typedef unsigned long long int  ull;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif


ll n = 100001;
vector<bool> is_prime(n, true);
vector<ll> primes;
bool isPrime(ll n)
{
    if (n <= 1)
        return false;
    for (ll i = 2; i < n; i++)
        if (n % i == 0)
            return false;
  
    return true;
}
li maxprime(ll u)
{
    li count = 0;
    for (ll i = 0; primes[i] <= sqrt(u)+1; i++)
    {
        if(u%primes[i]==0){count++;}
    }
    if(isPrime(u)){count++;}
    return count;
}
int minprime(li j)
{
    int h = 0;
    if(j==1){return 1;}
    for(ll i = 0;primes[i] <= j;i++)
    {
        if(j%primes[i]==0){h = j/primes[i];break;}
    }
    return h;
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("error.txt", "w", stderr);
	    freopen("input.txt","r",stdin);
    	freopen("output.txt","w",stdout);
    #endif
    is_prime[0] = false;
    is_prime[1] = false;
    for(int i = 2; i * i <= n; i++) {
        if (is_prime[i])
        {
            primes.PB(i);
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    int test;
    SCD(test);
    while (test--)
    {
        li n,m;
        cin >> n >> m;
        li k = maxprime(m);
        debug(k);
        li o;
        if(k==0){o=0;}
        else if(n%k==0 || k>=n){o = min(k,n);}
        else{o=minprime(n);}
        cout << o << '\n';
    }
    return 0;
}

I dunno why my code kept getting SIGFPE even though I checked it so many times for zero division. But couldn’t crack it . Please Help.!
My approach is to generate Sieve of Eratosthenes to get primes until \sqrt{n} and then use them to find prime factors of n. Then using them to find possible colums. Please help me!

There is so much plagiarism during contest, it degrades the essence of competition.

6 Likes

Very true i felt the same Infact all the co prime pairs lcm if included will cause problem.

1 Like

I also had the same doubt but I think I have found the reason now.
What you are doing is that you are checking for primes that divide m that are less than sqrt(m) (those primes that u have inserted in sieve) but there can be a prime that is greater than sqrt(m) which divides m which we will miss in that case, and it is for this reason in the editorialist’s solution what he has done is he checks for primes less than sqrt(m) and keeps on dividing by that prime till it is divisible and finally if after dividing by all such primes (factors) less than sqrt(m) if m is still >1 it means that there was a prime greater than sqrt(m) which was a factor and so he increments the primes by 1 as done in the if condition i.e —> primes++

1 Like

Aren’t u just considering primes <= 1e6 in your solution while the upper bound of n is 1e9 , so primes greater than 1e6 and less than 1e9 need to be considered too

Yes. If anyone knows, please clarify.

1 Like

I guess it works why since for two numbers x and y we know that :

gcd(x,y) * lcm(x,y) = x * y

Now for the third condition(to follow that no two windows in different columns can have same y coordinate except for y = 0 and y = m) so we must have their lcm = m

that means for any two different columns i , j

gcd(x,y) * m = x * y

Now if we assume x and y as the power of the prime factors of m( means x and y have their gcd as 1) so their product can never exceed m

that means gcd(x,y) * m needs to be exactly m

hence their gcd needs to be 1 which is consistent with our assumption

take an example of n = 4 and m = 12

the ans of this case will come out to be 2

why since u can take one column with 4 windows and another columns with 3 windows

3 Likes

My doubt is, Why we are only considering prime factors and why not non-prime factors?

In the following example given in the problem statement,

8 210

we have taken non primes into consideration, because the loop hole is that matching y coordinate is 0, which is not a violation.

My question is, Can’t the answer be the combination of prime factors and non prime factors (or just only non prime factors), considering the loophole in case of non prime factors. It there is a combination then the answer is maximized in some cases.

Please clear this doubt, where I am wrong in this?
@pranavreddyp16 @ajit123q

1 Like

c_i is not the size of windows in i^{th} column. c_i denotes the number of windows in i^{th} column.

1 Like

Yeah, it is possible that including non-prime factors may be a case of maximum answer. But we don’t need to do that. If we include a non-prime factor, we can instead take its prime factors separately.

Choosing non-prime factors can actually decrease our maximum possible answer.

Let’s say we have a non-prime factor A, which itself has a prime factor P. Now, we can choose only one from A or P (as shown in the editorial). It is better to choose P so that we don’t compromise factors. If A has prime factors P1, P2 … Pn, if we choose A, we cannot choose P1, P2 … Pn, but if we don’t choose A, we choose all of P1, P2, … Pn (as many as value of N permits).

Let’s see a numeric example.
For 12, 4 is a factor. We can choose 4 and 3. But we can also choose 2 and 3. Both are maximum cases.

Similarly, for 12, 6 is a factor. If we choose 6, we can’t choose any other number. But if we choose its prime factors 2 and 3, we can have two columns.

Hope it helps. Please correct me if I am wrong.

1 Like

@ajit123q I think the links are not working , the ones below Problem Link :

1 Like

This was really a nice problem.
I had the idea of what needs to be done but I couldn’t do it in contest :cry:
can someone please point out what I did wrong
https://www.codechef.com/viewsolution/55880859

Considering this eg = 12 2310
now, first thing - I can divide 12 in 6 equal parts at max .
second thing - 2310 = 2 x 3 x 5 x 7 x 11 x 1
as i see here, there I can form 6 columns too, as I have 6 numbers who have gcd of 1 with each other. But the ans is 4 in this case.

why so ?

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

1 is not prime number.

if N=10003199(prime number) and u call function minprime,then at some point var(i) will be greater than size of primes vector and u are trying to access it.

1 Like