ByteCode 2013 problem DIFBMB

general
,
1

Now, contest is over i want to ask this question from the day i saw this problem. The constraints limit on a and b is from 1 to 10^9. And i solve this problem for first 1000 values that is 1 to 10^3 by simple counting number of primes form a to b with given properties.

Can this problem be solved for the given constrainst that is

1
1 1000000000

If yes, how and If, no then what the organisers of ByteCode 2013 are thinking.

2 Likes
2

hello @sobhagya constraints were not given correctly . Yes constraints of a,b is 1<=a,b<=10^9 but test cases contained values of a and b such that b-a <=10^4 or 10^5 .

Problem can be easily solve with using of Rabin Miller to check given number is prime or not then further check given number represented as sum of two number’s square or not (simple number%4==1 but you also have to consider number “2” ). Thats it .

2 Likes
3

This question can be done using the property that all prime numbers of the form 4n+1 can be expressed as the sum of squares of 2 numbers. In the problem, actual limits in the test cases were only primes upto 100 i think. TROLLED!!

1 Like
4

Actually, in the test cases b < 1000. :stuck_out_tongue:

5

Now, i’m thinking only the organisers of ByteCode can answer this question.

6

Its not robin miller first of all!

7

Are you all kidding?? In actual test cases, b <= 16, because, my code (given below) is an AC solution.

As there were many discussions going on about the test cases, I did a few checks of my own, and was surprised that even THIS passed!!

#include <stdio.h>

int main()
{
	int t, a, b, count;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &a, &b);
		count  = (a <=  2 &&  2 <= b);
		count += (a <=  5 &&  5 <= b);
		count += (a <= 13 && 13 <= b);
		printf("%d\n", count);
	}
	return 0;
}

Seriously, why do they give such constraints, then??

PS:

  1. There was another post, where a student from IITG (not part of the organizing team this year) has promised that there won’t be any such issues next year. Hope so tee a good contest, next year.
  2. In my opinion, the problems were good, only the test files were not good enough to exploit the constraints!
1 Like
8

Now, I said b <= 16, because, the next possible solution 17 is not included in the code and still I got AC. So, the maximum b can reach is 16!!