CHEFKEY - Editorial

editorial
, , , , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

Cakewalk

PREREQUISITES

loops, simple maths

PROBLEM

Find number of (x, y) pairs such that 1 \leq x \leq H, 1 \leq y \leq W and x * y = K.

QUICK EXPLANATION

Iterate over x and you can check if there exists a valid y in the desired range satisfying x \cdot y = K or not.

EXPLANATION

##\mathcal{O}(H * W) bruteforce solution

Constraints on H and W are quite small. We can exploit these to get a
simple bruteforce solution. We iterate over all (x, y) pairs and check
whether their product x * y is equal to K or not. We can count such
valid pairs in \mathcal{O}(W * H) time.

Pseudo Code:

ans = 0
for x = 1 to H:
  for y = 1 to W:
    if x * y == K:
      ans++

##\mathcal{O}(K log K) solution
Let us make a simple change in the last solution? What if we you stop iterating over y when the value
of x * y exceeds K. Will that improve time complexity?

ans = 0
for x = 1 to H:
  for y = 1 to W:
    if x * y > K:
      break;
    if x * y == K:
      ans++

Yes, it will. Let us estimate it. From a casual look, it looks that
its time complexity will still be \mathcal{O}(H * W). But it’s not. Let us
delve into depth.

For each x, the inner loop over y will run at most \frac{K}{x} times. So,
total number of iterations the program will be run will be given by

\frac{K}{1} + \frac{K}{2} + \dots + \frac{K}{H}
\leq \frac{K}{1} + \frac{K}{2} + \dots + \frac{K}{K}
\leq K \cdot (\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{K})

The expression

\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n}

is also known as harmonic sum H_n. One can prove that H_n = \mathcal{O}(log \, n).

Hence, the time complexity will be \mathcal{O}(K log K).

##\mathcal{O}(H) solution
Let us exploit the condition x * y = K. For a fixed x, do we really need to iterate
over all y's to check how many of them satisfy x * y = K. It turns out, no. Firstly there will be at most a single y. If K is not divisible by x, then there can’t exist such y. Otherwise y will be \frac{K}{x}.

In summary, we iterate over only
x values and find the corresponding y (if it exists), and
check whether the y is \geq 1 and \leq H.

Time complexity of this method will be \mathcal{O}(H), as are iterating over x values only once.

Factorization based solutions

If x \cdot y = K, then both x and y should divide K. So we can find all the divisors of the K. Let x be one such divisor, then y will be \frac{K}{x}.

You can find all the divisors of K in \mathcal{O}(sqrt(K)) time.

EDITORIALIST’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like
2

*ans = 0

Start i from 1 to n

Check if c % i = 0 and c / i <= m

ans++*

1 Like
3

MY approach to it in c++:

#include <bits/stdc++.h>
#define rep(i,N) for(i=1;i<=N;i++)
#define rep1(i,N) for(i=N;i>=1;i--)
#define lli long long int
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int T;
 cin>>T;
 while(T--){
 lli n,m,c,count=0,i,j,start;
 cin>>n>>m>>c;
 if(n*m<c) {  cout<<0<<"\n"; continue;  }
 start=m;
 rep(i,n){
  rep1(j,start){
 if(i*j==c) {count++; start=j;   break; }
  }
  }
 cout<<count<<"\n";
 }
 }
4

import java.util.*;

class Chef_and_keyboard
{
public static void main(String args[])
{

       Scanner sc=new Scanner(System.in);
       int c[],x[],y[];
       System.out.println();
       x=new int[sc.nextInt()];
       y=new int[x.length];
       c=new int[y.length];
       for(int i=0;i<x.length;i++)
        {
            x[i]=sc.nextInt();
            y[i]=sc.nextInt();
            c[i]=sc.nextInt();
        }
        
        for(int i=0;i<x.length;i++)
         System.out.println(Combi(x[i],y[i],c[i]));
         
        }
        
   static int Combi(int n,int m,int c)
      {
          int count=0;
          if(n*m<c)
              return count;

            for(int i=1;i<=c;i++)
               {
                   if(i>n || i>(c/i))
                      return count;
                  
                   if(c%i==0)
                   {                   
                  if(i<=m && (int)c/i<=n && c/i<=m)
                   count+=2;
                  else 
                   if(c/i<=m)
                   count++;
                }
            }
         
           return count;
        }
    }
5

Hi there. Just wanted to say that in the O(H) solution we have to check if y>=1 and less than width and not height as mentioned in the explanation.

6

Is O(H) better or O(Klog K) better … I have used the former.

7

can some one explain how does the O(sqrt(K)) solution work