10871 - Primed Subsequence

[sohel]

I just observed one of my friend getting this one AC with a solution that has a time complexity of O(n^3).

I mean if there is just one test case having the format
1
10000 10000 10000 10000............... 10000

it would surely get TLE..

a line from problem statement:

Code: Select all

The line begins with the integer n, 0< n< 10001

So, we can suspect at least one data will have n == 10000 or somewhere very close to it. But, I figured out that no data has a value of more than 1000 for n, using assert();

no wonder why so many got this one AC in the real time contest.

[misof]

Well, there was a small problem I noticed: The text of the problem statement says:

You should note that 80% of the test cases will have at most 1000 numbers in the sequence.

And the clarification just before the contest says:

Problem B:
There are only three sets of inputs.

Surely you can see that combined together this says: Each of the (at most 3) test cases has at most 1000 numbers. (If some of them didn't, it would be more than 20%.)

[shahriar_manzoor]

The judge data used for this problem is not complete. because a slow solution takes a lot of time if all judge data are used. The original contest allowed the slow solution to pass, so to allow the slow solutions to pass and still keep the time limit reasonable I used only small number of data and hence this problem is there.

[kp]

I got AC during contest but now it's interesting to me
what complexity does the "best" solution have?

[misof]

I got AC during contest but now it's interesting to me
what complexity does the "best" solution have?

I don't think that you can do better than a worst-case quadratic solution -- there can be sequences leading to Omega(N^2) different numbers to test for primality. (E.g. the sequence 1 2 4 8 16 ..., but here the numbers grow too rapidly.) I don't think that in the general case you can think of some clever way of checking this in less than N^2 time. (Prove me wrong )

Let B be the upper bound on each of the numbers in the input. IMHO the asymptotically fastest way of doing the primality checks is to compute the sieve of Erathostenes up to NB in O(NB log(NB)) and then to answer the queries in O(1) time each. The total time complexity is thus O(N^2 + NB log (NB)).

(Well, I think that given the 80% constraint in the problem statement and at most 20 test cases, the worst possible inputs could still force this solution to timeout... but nothing significantly better comes to my mind)

[rotoZOOM]

If upper bound will be 10000 and amount of numbers is 10000 than
N*B = 10^8. If we use bit sieve of Erathosphenes it take us 12,5 Mb and
complexity O(10^8*log(10^8)). What do you think about it ?

[misof]

You only need one bit for each odd number up to 100'000'000. This reduces the memory to only 6 MB. The sieve can be computed in under 10 seconds, if implemented well... and this should be the most time-consuming operation.

[neno_uci]

I am getting TLE, what can I do to optimize my solution...???

Code: Select all

#include <stdio.h>



#define MAXBITS 50000000
#define USIZE (8*sizeof(unsigned))

unsigned bitarray[MAXBITS/USIZE + 1];

#define SETBIT(X)    (bitarray[X/USIZE]|=1<<(X%USIZE))
#define RESETBIT(X)  (bitarray[X/USIZE]&=~(1<<(X%USIZE)))
#define GETBIT(X)    ((bitarray[X/USIZE]&(1<<(X%USIZE)))?1:0)



#define MAX 10000

int arre[MAX + 1];
int n;

void sieve()
{
	RESETBIT(1);
	
	for (int i = 3; i <= MAXBITS; i += 2)
		if (GETBIT(i / 2) == 0)
		{
			for (int j = 3; j <= MAXBITS / i; j += 2)
				if (i * j % 2)
					SETBIT(i * j / 2);
		}
		
	//puts("MATO");
}

void readdata()
{
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++)
		scanf("%d", &arre[i]);
}

void makesolu()
{
	for (int l = 2; l <= n; l++)
		for (int ini = 1; ini <= n - l; ini++)
		{
			int sum = 0;
			
			for (int p = 0; p < l; p++)
				sum += arre[ini + p];
			
			if (sum == 2 || ((sum % 2) && (GETBIT(sum / 2) == 0)))
			{
				printf("Shortest primed subsequence is length %d:", l);
				
				for (int p = 0; p < l; p++)
					printf(" %d", arre[ini + p]);
				
				putchar('\n');
				return;
			}
		}
		
	puts("This sequence is anti-primed.");
}

int main()
{
	int test;
	
	sieve();
	scanf("%d", &test);
	
	while (test--)
	{
		readdata();
		makesolu();
	}
	
	return 0;
}

Any kind of help will be appreciated

Yandry.

[kp]

Your algorithm calculates same things more then once!
It is about to improve.

Try this:

1. Calculate sums of size 2 for every element
2. Increase size by 1
3. Calculate sums of size 3 for every element using
result of step 1
...
and so on...

[neno_uci]

Thanx a lot kp, I got AC, although my solution was almost TLE(>9sec), you are a great helper

[Niaz]

Please give some I/O.
I have generated prime upto 30000010 and then got WA. Is it due to upper bound or for some other reason ? Is there any tricky input ? plz help.

Thanks in advance.

[bijon]

read this :
You should note that 80% of the test cases will have at most 1000 numbers in the sequence.

so you can run siv atmost for 100000

and remember that this is a consecutive subsequence of length at least two.

so sum them and check in siv if it is in limit .if not then check menually
that it is prime or not.

remember that you should print the shorted lenths sequences not shorted value.

I think this will help you .

[Niaz]

Actually My siv is fast enough to find mentioned primes. And if the input in 1000 10000 then the sum of the numbers will be really very high. That's why i did find the prime at such a high range.

Can any one give me some Input and Output so that I can check my code with them.

Thanks.

[bijon]

try this :

Code: Select all

INPUT :

33
5 3 5 6 3 8
5 6 4 5 4 12
21 15 17 16 32 28 22 26 30 34 29 31 20 24 18 33 35 25 27 23 19 21
8 922 7912 7299 6369 9734 5226 9503 2307
12 6667 1903 2516 6149 4515 3388 2497 9125 7007 7727 2658 1221
3 9858 1730 8553
9 2429 7761 9133 5532 8835 7629 5560 2815 8383
4 8930 4868 7901 8361
15 2398 7179 9487 1341 3908 1409 3950 3425 3285 7604 5050 4655 2948 5631 4497
1 3004
6 1152 4202 6900 7787 7781 1304
19 2348 570 7391 4605 7447 6080 7300 4085 2663 1199 6660 7793 1592 5903 2596 9605 549 2460 5293
6 3621 1935 6193 7685 7667 4041
19 5572 9197 9289 548 4352 6114 8438 8979 6191 275 6236 6088 2683 8693 5593 1038 9322 8436 6890
11 2105 4772 5682 3913 6243 5723 8140 1612 4961 8733 950
13 1457 9675 5006 5380 8300 2350 7458 9904 9506 1615 7247 5721 378
9 1501 4438 5642 768 4557 9965 6436 2153 6346
6 7334 9086 2091 7902 1763 8260
15 6661 8917 6217 6263 6425 1326 7556 3919 4018 925 6596 2766 184 2796 109
6 9198 5735 9766 3001 6280 3412
10 1377 4167 8621 7110 3714 8166 2907 286 5875 7242
9 9409 5385 3023 4344 1829 9544 3940 6215 5864
15 5854 1539 7304 8819 9725 1833 1521 6112 231 6676 5500 4949 8498 5884 2045
8 2794 8226 3533 7948 1615 1084 2011 6809
11 7248 9426 3472 1628 9068 9160 8682 4934 9762 7403 8447
10 1084 5492 1412 412 5635 7611 2899 8333 334 7526
15 1968 7770 937 8204 1832 7517 4027 6689 5410 375 7331 9643 4671 3372 2589
17 9223 5455 2542 9927 3045 3702 8316 6169 6624 8596 6300 3523 1871 9390 9929 5118 2940
4 3331 4931 1118 5530
10 6009 2067 5949 4159 4928 2820 792 9968 7497 2715
15 5636 5953 6050 5332 997 3518 759 6733 5579 7993 7606 5900 5915 1511 4878
3 3748 9191 6227
1 4350

OUTPUT :

Shortest primed subsequence is length 2: 5 6
Shortest primed subsequence is length 3: 4 5 4
This sequence is anti-primed.
Shortest primed subsequence is length 2: 6369 9734
Shortest primed subsequence is length 4: 1903 2516 6149 4515
This sequence is anti-primed.
This sequence is anti-primed.
This sequence is anti-primed.
Shortest primed subsequence is length 2: 3285 7604
This sequence is anti-primed.
This sequence is anti-primed.
Shortest primed subsequence is length 2: 2460 5293
This sequence is anti-primed.
Shortest primed subsequence is length 2: 8438 8979
Shortest primed subsequence is length 3: 8140 1612 4961
Shortest primed subsequence is length 6: 8300 2350 7458 9904 9506 1615
Shortest primed subsequence is length 2: 1501 4438
Shortest primed subsequence is length 2: 9086 2091
Shortest primed subsequence is length 2: 3919 4018
Shortest primed subsequence is length 2: 3001 6280
Shortest primed subsequence is length 2: 8621 7110
Shortest primed subsequence is length 2: 4344 1829
Shortest primed subsequence is length 2: 5854 1539
Shortest primed subsequence is length 2: 1615 1084
Shortest primed subsequence is length 4: 8682 4934 9762 7403
Shortest primed subsequence is length 2: 412 5635
Shortest primed subsequence is length 2: 7770 937
Shortest primed subsequence is length 2: 1871 9390
Shortest primed subsequence is length 3: 4931 1118 5530
Shortest primed subsequence is length 3: 792 9968 7497
Shortest primed subsequence is length 2: 5332 997
This sequence is anti-primed.
This sequence is anti-primed.

I think this will help you.

[Niaz]

Thanks Bijon for ur effort. But still I am getting WA!
Here is my outputs accourding to ur inputs.

Shortest primed subsequence is length 2: 5 6
Shortest primed subsequence is length 3: 4 5 4
This sequence is anti-primed.
Shortest primed subsequence is length 2: 6369 9734
Shortest primed subsequence is length 4: 1903 2516 6149 4515
This sequence is anti-primed.
This sequence is anti-primed.
This sequence is anti-primed.
Shortest primed subsequence is length 2: 3285 7604
This sequence is anti-primed.
This sequence is anti-primed.
Shortest primed subsequence is length 2: 2460 5293
This sequence is anti-primed.
Shortest primed subsequence is length 2: 8438 8979
Shortest primed subsequence is length 3: 8140 1612 4961
Shortest primed subsequence is length 6: 8300 2350 7458 9904 9506 1615
Shortest primed subsequence is length 2: 1501 4438
Shortest primed subsequence is length 2: 9086 2091
Shortest primed subsequence is length 2: 3919 4018
Shortest primed subsequence is length 2: 3001 6280
Shortest primed subsequence is length 2: 8621 7110
Shortest primed subsequence is length 2: 4344 1829
Shortest primed subsequence is length 2: 5854 1539
Shortest primed subsequence is length 2: 1615 1084
Shortest primed subsequence is length 4: 8682 4934 9762 7403
Shortest primed subsequence is length 2: 412 5635
Shortest primed subsequence is length 2: 7770 937
Shortest primed subsequence is length 2: 1871 9390
Shortest primed subsequence is length 3: 4931 1118 5530
Shortest primed subsequence is length 3: 792 9968 7497
Shortest primed subsequence is length 2: 5332 997
This sequence is anti-primed.
This sequence is anti-primed.

[/quote]