LEDIV - Editorial

editorial
, ,
11

CodeChef: Practical coding for everyone What’s wrong in my code? It shows WA. I’ve implemented the method shown in the editorial. Please help.

12

i am getting a WA…
please help…

#include<stdio.h>
long int a[100000]={0};
int main(void)
{
 long int t,n,i,min,flag,j,res;
 min=100000;
 scanf("%ld",&t);
 while(t--)
 {
  scanf("%ld",&n);
  for(i=0;i<n;i++)
  {
   scanf("%ld",&a[i]);
   if(a[i]<min)
   {
    min=a[i];
   }
  }
  for(i=2;i<=min;i++)
  {
   flag=1;
   for(j=0;j<n;j++)
   {
    if(a[j]%i!=0)
    {
     flag=0;
     break;
    }
   }
   if(flag==1)
   {
    res=i;
    break;
   }
  }
  if(flag==0)
  {
   res=-1;
  }
  printf("%ld\n",res);
 }
 return 0;
}
13

i am getting a WA… please help…

#include<stdio.h>
int main(void)
{
 int t,ds,dt,d,x;
 x=0;
 scanf("%d",&t);
 while(t--)
 {
  scanf("%d%d%d",&ds,&dt,&d);
  if(ds+dt<d)
  {
   printf("%.6f\n",(float)(d-dt-ds));
  }
  else
  {
   printf("%.6f\n",(float)(x));
  }
 }
 return 0;
}
14

https://www.codechef.com/viewsolution/13098242
can somebody tell me, for which case it is not working???

15

I am getting WA.Please tell me the case where my code fails.
https://www.codechef.com/viewsolution/14322036

16

I am getting wrong answer although in the dry run everything seems to be working fine. Also, the sample test cases from editorial are working.

Can anyone suggest the test case which could fail my solution/ review my solution?

https://www.codechef.com/viewsolution/14364283

TestCases:

1 1 1 => -1 (since x>1)

1 2 20122 30183 => 10061

1 1 24371 => 24371

1 2 123 456 => 3

Many Thanks!

17

When your ‘r’ is divisible by 3 you did not find this. Say r=63.

1 Like
18

That was a huge miss … sorry . .
but sadly that does not fix the error
submission 1565280

19

Consider T=1 N=1 A[1]=24371

2 Likes
20

You logic is completely incorrect. Try this test T=1 N=2 A[1] = 2 * P A[2] = 3 * P where P is large prime say A[1] = 20122, A[2] = 30183.

1 Like
21

Try the simplest possible test:
1
1
1
:wink:

3 Likes
22

well … lesson learned …paid for incoherence. .
@anton thank a lot , very much appreciated :slight_smile:

23

@anton_lunyov:Thanks,i got it :slight_smile:

24

Try this test
1
1
12346

25

Replace array p[1000] by p[10000]. There are 9592 primes up to 100000.
However this leads to TLE :slight_smile:
http://www.codechef.com/viewsolution/1565776

What is even more fun that your previous solution passes first two tests and get WA on the third test. But the new “correct” version get TLE on the second test which have the following structure: T=100000 N=1 A[1]>90000 is prime. So as you see you perform about 9000 operations in average for each number. This is about 900 millions operations in all which of course do not fit in TL.

I can only suggest you to follow the editorial.

1 Like
26

Due to the lack of space I continue here.

You will be probably interested how you first solution can pass more tests than the corrected version. This is probably because array x[] follows p[] in the memory. So when you iterate over array p[] with condition p[i]<=min after the end of this array you jump to x[] which contain the element x[0] which is prime and it is the answer. So you break here.

1 Like
27

i am getting same answer as of tester solution .
what is the error?

28

No, you are NOT.

tester’s solution returns 24371

your solution returns 12186

1 Like
29

ok…got it…thanks

30

Thanks for the editorial, but I’ve found a typo in the part where we find the smallest prime factor of the gcd :

for i = 2 to floor(sqrt(N))
    if G is divisible by i
        return i
return N  // Since N is prime!

Shouldn’t the ‘N’ be ‘G’ ?

1 Like