CHEFWM - Editorial

For every composite number less than 1e9, there must be a prime factor less than equal to sqrt(1e9). if not then the number itself is a prime.

  • I generated all the divisors of m.
  • Sorted them in increasing order. Let say they are {d_1, d_2, … d_p}
  • After that, I check for every i, if I find d_j such that d_j > d_i and lcm(d_i, d_j) < m, then we cannot have a window of height d_i. Count all such d_i (let say the count is tot)
  • Our answer will be the largest C such that C <= tot and n % C == 0. (Same as the last step mentioned in editorial)

Here is my submission for reference.

oh , okay so it is compulsory to divide the column , cool got it thanks

I have precomputed all the prime numbers less than sqrt(1e9) and then calculated number of prime factors for m. What is wrong with this implementation?

bool isprime(int n)
{
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}
void solve()
{

    vector<int> primes;

    for (int i = 2; i * i <= (int)1e9+5; i++)
    {
        if (isprime(i))
            primes.pb(i);
    }
    tc(t)
    {

        int n, m;
        cin >> n >> m;
        if (m == 1)
        {
            cout << 0 << nl;
            continue;
        }
        if (n == 1)
        {
            cout << 1 << nl;
            continue;
        }
        int prime(0);
        for (int i = 0; i < sz(primes) && primes[i] < m; i++)
        {
            if (m % primes[i] == 0)
            {
                prime++;
            }
        }

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

Thank you so much for this beautiful explanation, @deepansh10.
This explanation cleared my doubt.

1 Like

what is prime(0)?
provide the link of full code with your template

Thanks for the great explanation. Will Codechef provide the data used to test possible solutions? It would be useful knowing for what cases my code fails. Thanks again. Cheers.

can you explain this test case:

input: 30 90
output: 3

prime factors are 2 3 5
then how will you divide into different columns as their lcm is 30
please given me possible column size

Image

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

Here’s an entirely random test case for which your code fails.

Input

1
2 1885387

Expected Output

2

Your Output

1

Explanation:

The Screen of width 2 can be divided into two columns, with the heights of windows being 269341 and 7.

1 Like

thanks

Are there any corner test cases for this question? My code is giving wrong answer for the final test case

Can you elaborate on your thesis using the following test case?

Input

1
210 1050

Also, show how you can attain the maximum number of Columns just by using Prime Factors.

Is this the counter example of what is I just above (according to you) ?
If yes, then please elaborate!

Thanks, updated!

Can anyone tell me why my code is failing.I have checked some test cases also

here’s my submission
https://www.codechef.com/viewsolution/56021154

I have a doubt regarding a corner case, which is, N=4, M=20
Editorialist solution’s output is 2.

But output should be 1.Because the answer takes two prime factors into consideration, which are: 2 and 5. (Prime factorization of 20 : 2 * 2 * 5)
But, there y coordinate will match at y=10, because LCM(2,5)=10.
So, this is a contradiction, right?

Can someone clear this doubt?
Please clear this doubt, @pranavreddyp16 @lavish315 @tejas10p @ajit123q

According to the convention taken in the editorial the LCM of sizes of windows should be considered so as to see if they meet at a point (si and sj), not the count of windows. Furthermore, si and sj should be a multiple of m (if they have remainder left then last window will not be of equal size). Therefore, there LCM is going to m in any case, you can’t have more than that . LCM(si,sj) < m is obviously not gonna help us as then the windows will meet at a horizontal level below y = m. Therefore the only option left is LCM(si,sj) = m.

LCM(si,sj) = m

And this is bascially going to lead us to the same conclusion. Consider the following proof,

LCM(si,sj) = m
LCM(m/ci,m/cj) = m
The last implication basically means that even after removing factors common to ci from m and then factors common to cj from m we get the LCM still as m. This means that ci and cj must have no common factors in it (except 1 obviously) .
=>GCD(ci,cj) = 1
Hence, both the logic are equivalent and lead to the same conclusion.

*do let me know if you find anything wrong *
Thanks

According to the convention taken in the editorial the LCM of sizes of windows should be considered so as to see if they meet at a point (si and sj), not the count of windows. Furthermore, si and sj should be a multiple of m (if they have remainder left then last window will not be of equal size). Therefore, there LCM is going to m in any case, you can’t have more than that . LCM(si,sj) < m is obviously not gonna help us as then the windows will meet at a horizontal level below y = m. Therefore the only option left is LCM(si,sj) = m.

LCM(si,sj) = m

And this is bascially going to lead us to the same conclusion. Consider the following proof,

LCM(si,sj) = m
LCM(m/ci,m/cj) = m
The last implication basically means that even after removing factors common to ci from m and then factors common to cj from m we get the LCM still as m. This means that ci and cj must have no common factors in it (except 1 obviously) .
GCD(ci,cj) = 1
Hence, both the logic are equivalent and lead to the same conclusion.

*do let me know if you find anything wrong *
Thanks

1 Like