 # CHEFKEY - Editorial

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

*ans = 0

Start i from 1 to n

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

ans++*

1 Like

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";
}
}

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;
}
}

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.

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

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