10871 - Primed Subsequence

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon » Sun Oct 09, 2005 3:34 pm


you may post your code

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » Fri Nov 25, 2005 1:56 pm

Posting my code that gives correct ans for the bijon's given input.

Code: Select all

#include<stdio.h>
#include<math.h>
#define max 10011
#define pmax 20000010
char prime[pmax];
int bank[max+100];
int isPrime(long);
void siv()
{
    long i,j,k;
    prime[0]='x';
    prime[1]='x';
    for(i=3;i<=(int)sqrt(pmax);i=i+2)
    {
        if(prime[j]!='x')
        {
            k=i;
            j=k+2*k;
            while(j<=pmax-5)
            {
                prime[j]='x';
                j=j+2*k;        
            }
        }
    }
}
int isPrime(long a)
{
    if(a==2)
        return 1;
    if(a%2!=0)
        if(prime[a]!='x')
            return 1;
    return 0;
}
int main()
{
    int N,n,i,j,sum,s,e;
    siv();
    //freopen("F:\\input.in","r",stdin);
    //freopen("C:\\output.out","w",stdout);
    scanf("%d",&N);
    while(N--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&bank[i]);
        s=0;
        e=10011;
        for(i=0;i<n;i++)
        {
            sum=0;
            for(j=i;j<n;j++)
            {
                sum=sum+bank[j];
                if(isPrime(sum) && i!=j)
                {
                    if(j-i<e-s)
                    {
                        s=i;
                        e=j;
                    }
                    
                }
            }
        }
        if(e!=10011)
        {
            printf("Shortest primed subsequence is length %d:",e-s+1);
            for(i=s;i<=e;i++)
                printf(" %d",bank[i]);
            printf("\n");
        }
        else
        {
            printf("This sequence is anti-primed.\n");    
        }
    }
    return 0;
}
If anyone can find my mistake then I will be very much grateful to him. This problem is making me crazy. Plz help me. Anyway, thanks in advance.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon » Sat Nov 26, 2005 5:26 pm

the number will be at best 9999*10000 .
so how do you check prime if the number will be greater then 300000000?

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » Tue Dec 06, 2005 6:51 pm

bijon wrote:the number will be at best 9999*10000 .
so how do you check prime if the number will be greater then 300000000?
Do you mean "300000000" or "30000000" ?

I got to know from a previous post on this problem that the number will not be too large. That's why I took such a small upper limit. Would you please tell me the upper limit for my SIV ?

Thanks.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Wed Dec 07, 2005 10:09 am

AFAIR,

There can be numbers as large as 300000000 ( 3 * 10^8 )..
.. but you can't get that much memory to store all those..

.. try siving as many as you can, and use the normal method to check for primes for larger numbers.

normal.. check divisibility upto sqrt(n).

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 10871 - Primed Subsequence

Post by Igor9669 » Thu Nov 05, 2009 8:02 pm

Weak test!!!!
For such test:
1
10000 10000 100000.....10000
My program should get MLE! But it got AC!

Post Reply

Return to “Volume 108 (10800-10899)”