DSTAPLS - Editorial

editorial
, , , ,
12

@vijju123 advantage of python over c++ is calculating the k^2.if we calculate k^2 in c++ it will SIGFPE

13

Right. Sorry, my bad! :stuck_out_tongue: I got confused haha.

Can you give me submission link? Your condition is correct, but your latest submission in python ( CodeChef: Practical coding for everyone ) gets a TLE coz you are making a list of size k

14

Yessssss. :smiley:

If you try to calculate k^2 in C++, you will get overflow and hence undefined behavior - which may (or may not :stuck_out_tongue: ) result in SIGFPE.

1 Like
15

What part do you think could have been better? :slight_smile:

I think you no longer need me to explain the test case - because what you wrote is correct!

The main thing to realize is that, equality can be achieved only after putting K^2 applies at time t=0,K,2*K,3*K... minutes

1 Like
16

Yeah , I tried to do differently but my previous solutions were based on the logic stated here

17

Solution link please? :slight_smile:

18

Here is the link:
https://www.codechef.com/viewsolution/25882552

19

Replace n/k with n//k .

In python / operator performs floating point division which can lead to precision errors if numbers are large. Hence your n/k does not get accurate value.

// is integer division and gives correct precision.

20

Okay , I got it !
Thank you sir .

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?