You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFKEY - Editorial

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.

This question is marked "community wiki".

asked 19 Oct '16, 12:42

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 20 Oct '16, 14:15

admin's gravatar image

0★admin ♦♦
19.8k350498541


ans = 0
Start i from 1 to n
   Check if c % i = 0 and c / i <= m
      ans++

link

answered 19 Oct '16, 12:55

coder_voder's gravatar image

2★coder_voder
593332
accept rate: 8%

edited 19 Oct '16, 15:29

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

answered 19 Oct '16, 14:03

smsubham's gravatar image

3★smsubham
675216
accept rate: 15%

edited 19 Oct '16, 14:07

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

answered 29 Oct '16, 01:16

indra_the_zeus's gravatar image

0★indra_the_zeus
1
accept rate: 0%

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.

link

answered 29 Mar '17, 12:28

behram's gravatar image

2★behram
11
accept rate: 0%

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

link

answered 13 Jun '17, 19:16

mathprogrammer's gravatar image

3★mathprogrammer
585
accept rate: 5%

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

link

answered 25 Jun '17, 01:04

strawhatdragon's gravatar image

2★strawhatdragon
435
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,851
×1,688
×281
×98
×63
×45
×2

question asked: 19 Oct '16, 12:42

question was seen: 3,904 times

last updated: 25 Jun '17, 01:04