DSTAPLS - Editorial

editorial
, , , ,
21

Python in simplified terms:

for _ in xrange(input()):
    n,k = map(int,raw_input().split())
    print "NO" if n%(k*k)==0 else "YES"

Great discussion on these forums. One can learn so much. Thank you all!

22

We can just find a=n/k and then we can do a%k which will not give SIGFPE in C++.

1 Like
23

#include<bits/stdc++.h>
using namespace std;
int main()
{
int test;
cin>>test;
unsigned long long int n,k,temp;
for(auto j=0;j<test;j++){
cin>>n>>k;
if(k==1)
cout<<“NO\n”;
else{
temp=n/k;
if(temp%k==0)
cout<<“NO\n”;
else
cout<<“YES\n”;
}
}
return 0;
}

24

can someone clarify what is the mistake in my code…my code only passes 30%,thanks
below is my code,
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner scan=new Scanner(System.in);
int t=0,n=0,k=1,i;
if(scan.hasNextInt())
t=scan.nextInt();
for(i=0;i<t;i++)
{
if(scan.hasNextInt())
n=scan.nextInt();
if(scan.hasNextInt())
k=scan.nextInt();
int c=n/k;
if((c%k)==0)
System.out.println(“NO”);
else
System.out.println(“YES”);

	}
	
}

}

25

Numbers are as large as 10^{18} and hence overflow ‘int’ . Use ‘long’

26

The only condition when the final condition will be same is if N is a multiple of k*k.
Your logic works.

27

Sir please have a look at this code submission

It gives correct output for sample test case but gives WA for subtask 1 and TLE for subtask2. I guess for the latter, it is due to O(n^2) of second loop but I can’t figure out the faulty logic for WA.

Edit 1: Found faulty logic and fixed it here
Edit 2: Fixed TLE using the logic given here. Also implemented in cpp avoiding integer overflow-underflow here

28

@anon41636913
Your simulation for first is incorrect i think . It increments every box just once

2 Likes
29

Why (n/k)%k == 0 and not (n%k)%k==0

30

Try it with some real values of n and k and you’ll see why :slight_smile:

1 Like
31 
import java.util.*;
import java.lang.*;
import java.io.*;

import java.util.Scanner;


/* Name of the class has to be "Main" only if the class is public. */
 class Ques2 {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int t=s.nextInt();
        for (int i = 0; i <t ; i++) {
         long  n=s.nextInt();
         long  k=s.nextInt();
            if(n%(k*k)==0){
                System.out.println("NO");
            }
            else {
                System.out.println("YES");
            }

        }
    }
}

I am getting only 30 points can somebody please tell me the issue?

32

Did you read the editorial regarding the overflow part in calculating k*k ?

33

So question, Its given that “the second one chooses a random box with the smallest number of apples and puts K apples in it.”
so my understanding is that first he will select a box at random. Then after that he’ll randomly select from the remaining boxes and so on. Is that correct? Because at the beginning all the boxes will have zero apples

34

No. Its like, out of all boxes with minimum apples, he will select a box at random.