GDOG - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Vlad Mosko
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Simple math

PROBLEM:

You have N coins. You are about to call any number of people between 1 and K and divide the coins to them in such a way that each person gets the same amount of coins and this amount is maximal. You take all coins left after this process. Your task is to compute the maximal number of coins which you can get.

QUICK EXPLANATION:

For each possible number of people, compute the amount of coins which are left after the process. Finally, return the maximum from these values.

EXPLANATION:

Let assume that you decided to call exactly k people and you want to divide N coins to them in the way described in the statement. It means, that each person gets the same amount of coins and this amount is maximal from all possible ones. You can simulate this process by giving one coin to all people at once until you have less than k coins, because then you cannot divide them equally. The number of coins which each person has after the process equals N \mathbin{/} k, where \mathbin{/} is the integer division, i.e. 7 \mathbin{/} 3 = 2. Based on this fact, it is easy to see that there are r = N - k \cdot (N \mathbin{/} k) coins left after the process and this is the amount of coins which you get. Here r is called a remainder after dividing N by k and it is very common in computation. Most programming languages have built in operation for computing a reminder. It is often represented by \texttt{%} or \texttt{mod}.

Since K is not so big, we can iterate over all possible values of it and for each of them, compute the remainder of N \mathbin{/} k, where k is the current number of people, and at the end print the maximum from these remainders.

Time complexity:

We are iterating over K values and for each of them we do constant time operations, so the total complexity is O(K).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here
Tester’s solution can be found here

3 Likes
2

can anyone post much optimize method for this problem??

as this problem has very few test cases it works for this only…

suppose problems has large test cases…10000
than this solution give tle…

3

worst case complexity : K/2
better than editorial solution’s time complexity:

here is my code

#include<bits/stdc++.h>

using namespace std;

int main(){

    int t,n,k;

    scanf("%d",&t);

    while(t--){

       scanf("%d%d",&n,&k);

       int ans=0,d=1,fake_k;

       if(k==1) {cout<<"0"<<endl; continue;}

       if(n<k) { cout<<n<<endl; continue;}

       if(n%k==0){ cout<<(n%(k-1))<<endl; continue;}

        while(1){

            fake_k=n/d;

             if(fake_k+1<=k){

                  ans=n%(fake_k+1);

                  break;
               }
               d++;

               if(!fake_k) break;
          }

           printf("%d\n",ans);
      }
     return 0;
 }

Idea of this solution is simple

to analyze this solution you can just take number and see what all value of mod if you are trying divide n with k where n>k

then you will definitely get this…

HAPPY CODING

4

The answer is directly : N%(N/(N/K+1)+1)…

3 Likes
5

still unable to understand…!

6

What’s wrong with my code?

import java.util.Scanner;
class GDOG
{
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
int t=in.nextInt();
for ( int i=0; i<t; i++ )
{
int n=in.nextInt();
int k=in.nextInt();
int res=n-k;
while ( res>=0 )
{
n=res;
res=n-k;
}
System.out.println(n);
}
}
}

7

whats wrong with my code?

#include
#include <stdio.h>
#include
#include
#include <math.h>
#include <string.h>
using namespace std;
int main()
{
int t,i;
cin>>t;
for (int z=1; z<=t; z++)
{

    int n,k;
    cin>>n>>k;
    
    for (i=n; i>=1; --i)
    {
        if (k*i<=n)
        {
            break;
            
        }
        
    }
    
    cout<<n-(k*i)<<endl;
}
return 0;

}

8

#include
using namespace std;
int main()
{ long n,k,m,r;
int t;
cin>>t;
while(t–)
{cin>>n>>k;
m=n/k;
r=n-(m*k);
cout<<r<<endl;

   }
 return 0;

}

WHAT WRONG IN MY CODE???

9

I thought the solution would simply be N%K but that seems to be incorrect. What am I missing?

10

Not working why???

import java.util.Scanner;
class puppy{
public static void main(String args[]){
Scanner ashok=new Scanner(System.in);
int test=ashok.nextInt();
int i;
for(i=1;i<=test;i++){
int coins=ashok.nextInt();
int people=ashok.nextInt();
int j=1,x=1,count=1;
while(j>0){
count=peoplex;
if(count>coins){
System.out.println(coins-(people(x-1)));
break;
}
//if(count==coins){
//System.out.println(“0”);
//break;
//}
x++;
}
}
}
}

11

/*

  • To change this license header, choose License Headers in Project Properties.

  • To change this template file, choose Tools | Templates

  • and open the template in the editor.
    /
    package javaapplication60;
    /
    Author : Pujan
    */
    import java.util.Scanner;
    class stack
    {
    public static void main(String[] args)
    {
    Scanner in = new Scanner(System.in);
    int x,y;

     x = in.nextInt();
 y=in.nextInt();
 
 int temp = x/y;
 int temp1 = x%y;
 System.out.println("Max coins which people will get: "+temp);
         System.out.println("Coins which are left: "+temp1);

    }
    }

12

Nice! Can you give a short explanation on how it works? How did you land upon that equation?

13

#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
int r=0;
while(k)
{
if((n-(n/k)*k)>r)
{
r=n-(n/k)*k;
}
else
break;
k–;
}
cout<<r<<endl;
}
}

14

#include
using namespace std;
int main()
{ long t,n,k,ans,i,a;
cin>>t;
while(t–)
{ cin>>n>>k; ans=0;
for(i=2;i<=k;i++)
{ a=n%i;
if(ans<a)
ans=a;
}
cout<<ans<<"\n";

  }

return 0;
}

15

What is wrong with this code?
#include
using namespace std;

int main() {
int x,y,t;
cin>>t;
while(t>0){
cin>>x>>y;
if(y==0)
cout<<x;
else
cout<<x%y<<endl;
t–;
}
return 0;
}

16

What is wrong with this code?

#include <iostream>
 using namespace std;

 int main() {
 int x,y,t;
 cin>>t;
    while(t>0){
     cin>>x>>y;
      if(y==0)
        cout<<x;
      else
     cout<<x%y<<endl;
     t--;
}
return 0;

}

17

@sprea27

Your code will fail in many cases, one of them is-
When N=200, K=20
Your code will give (N%K)=0,
Actual answer will be (100%17)=15

18

@raviojha2105

1)When K>N, it will always return N.

2)When K>(N/2) but K<=N, it will always return (N/2)+1.

3)When K<=(N/2), it’s a little tricky, but bear with me. Here it goes-

our main goal is to choose a number num (1<=num<=K),
so that (N%num) will be max for the given range of K. Now how do we do this?
We choose num such that num is the smallest number such that N/K = N/num.

19

@sprea27
but that will not be maximum that people can have… maximum can be 20 so why 17?

20

Okay after scratching my head for sometime I got what the problem is about. The problem statement is somewhat misleading. The value of k is the number of people around the dog. We have to iterate over k to check how many people he should call so that the remainder is maximum. So simple n%k would not work and you have to find a number between 1 and k for which n%k is maxmimum.