957 - Popes

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

Moderator: Board moderators

aha2007
New poster
Posts: 10
Joined: Sun Jan 21, 2007 10:38 am

957 - Popes

Post by aha2007 » Thu Jan 25, 2007 12:54 pm

It's seems to me the problem of maximum sum of continuous sub sequences of length m.
I know a linear algorithm when length m is not specified , but don't know how to extend it for
specified length m. Can any one kind enough to give me a linear time algorithm for this problem , or any link describing that algorithm.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Feb 17, 2007 11:09 am

It is even easier when m is fixed.
Let a be the number of popes elected in the year i.
Let f[0]=a[0], and f = f[i-1]+a for i>0, so f is a cumulative sum.
Consider the value of f[i+m-1]-f[i-1] for all i.

As for the algorithm for maximum consecutive sum, it is trivial to solve when all the elements of the array is non-negative.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Jun 28, 2007 5:36 pm

Hello..~
Can anybody tell me what is wrong with my code..?
I'm getting WAs.. but I have no idea..

check is the number of occurences of 'i' and..
sum is the cumulative sum up to check

Code: Select all

code removed
Thanks.. :-)
Last edited by helloneo on Thu Jun 28, 2007 6:20 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jun 28, 2007 6:01 pm

Try the cases.

Input:

Code: Select all

11
20
20 numbers given in sample :)
12
20
20 numbers given in sample :)
17
20
20 numbers given in sample :)
Output:

Code: Select all

11 12 21
11 12 21
13 6 21
Hope the weird input set helps. :wink: .
Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Jun 28, 2007 6:26 pm

Thanks a lot..~
I got AC.. :-)


PS. very funny input.. :-) It took some time to get the point.. :cry:

Symon
New poster
Posts: 1
Joined: Thu Sep 09, 2010 12:09 am

957-Popes

Post by Symon » Sat Sep 18, 2010 9:29 pm

I can't realize why I'm getting WA.
Please give me some input output.

Code: Select all

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    long int y,p,i,j,a[100005],cnt[1][3],max,increase;
    while(scanf("%ld%ld",&y,&p)!=EOF)
    {
        max=-1;
        increase=-1;
        for(i=0;i<p;i++)
        {
            scanf("%ld",&a[i]);
            if(i!=0&&a[i]<a[i-1])
            {
                increase=0;
            }
        }
        if(increase==0)
        {
            sort(a,a+p);
        }
        for(i=0;i<p;i++)
        {
            cnt[0][2]=0;
            for(j=i;j<p&&a[j]<=a[i]+(y-1);j++)
            {
                cnt[0][2]++;
            }
            if(max<cnt[0][2])
            {
                max=cnt[0][2];
                cnt[0][0]=a[i];
                cnt[0][1]=a[j-1];
            }
        }        
        printf("%ld %ld %ld\n\n",max,cnt[0][0],cnt[0][1]);
    }
    return 0;
}]
thanks...

Hammer Engineer
New poster
Posts: 2
Joined: Fri Sep 13, 2013 8:37 am

Re: 957 - Popes

Post by Hammer Engineer » Fri Sep 13, 2013 9:00 am

Why RE ? Please help

Code: Select all

#include <iostream>
#include<vector>
#include<cstdio>
using namespace std;

int main()
{
    freopen("input.txt", "r", stdin);

    int span;

    //scanf("%d",&span);
     while ( scanf("%d",&span) != EOF ) {
          vector<int> a(100001);
          vector<int> F(100001);

          int Y , year;
          a[0] = F[0] = 0;



        scanf("%d",&Y);

        span -=1;
        for(int i=1; i<=Y; i++)
        {
            scanf("%d",&year);
            a[year] +=1;
        }

        for(int i=1;i<a.size();i++)
        {
            F[i] = (a[i] + F[i-1]);
        }

        int max=0,from , sum;
        for(int i=1;i<F.size();i++)
        {

            if(i+span < F.size())
                sum = F[i+span] - F[i-1];
            else
                sum = F[F.size()-1] - F[i-1];

            if(sum > max)
            {
                max=sum;
                from = i;
            }
        }



        printf("%d %d %d\n", max , from , from+span);

     }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 957 - Popes

Post by brianfry713 » Fri Sep 13, 2013 9:23 pm

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

Hammer Engineer
New poster
Posts: 2
Joined: Fri Sep 13, 2013 8:37 am

Re: 957 - Popes

Post by Hammer Engineer » Mon Sep 16, 2013 1:06 am

@brainfry713 When i'm submitting code i'm removing freopen() [ sorry I did't mension that in code].
Is there any other problem that can end with a RE ?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 957 - Popes

Post by brianfry713 » Tue Sep 17, 2013 10:04 pm

year L <= 1,000,000
Check input and AC output for thousands of problems on uDebug!

omar.fmc
New poster
Posts: 2
Joined: Sun Oct 05, 2014 11:00 pm

Re: 957 - Popes

Post by omar.fmc » Sun Oct 05, 2014 11:07 pm

Hello all,
I'm getting RE and I can't find out the reason of that.
Here's my code:

Code: Select all

Accepted 
Appreciate your help :-)


EDIT:
For those who are getting RE notice that P<=100000 in the judge's input (not 5000 as in the problem statement).
Last edited by omar.fmc on Tue Oct 07, 2014 10:57 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 957 - Popes

Post by brianfry713 » Tue Oct 07, 2014 10:50 pm

There is a case in the judge's input where P > 5000, but not one where P > 100000.
http://online-judge.uva.es/board/viewto ... &hilit=957
Check input and AC output for thousands of problems on uDebug!

omar.fmc
New poster
Posts: 2
Joined: Sun Oct 05, 2014 11:00 pm

Re: 957 - Popes

Post by omar.fmc » Tue Oct 07, 2014 10:58 pm

brianfry713 wrote:There is a case in the judge's input where P > 5000, but not one where P > 100000.
http://online-judge.uva.es/board/viewto ... &hilit=957
Thanks a lot. Got Accepted :-)

morkoh
New poster
Posts: 2
Joined: Sat Oct 18, 2014 7:22 pm

Re:

Post by morkoh » Sat Oct 18, 2014 7:28 pm

Jan wrote:Try the cases.

Input:

Code: Select all

11
20
20 numbers given in sample :)
12
20
20 numbers given in sample :)
17
20
20 numbers given in sample :)
Output:

Code: Select all

11 12 21
11 12 21
13 6 21
Hope the weird input set helps. :wink: .
Could someone tell me how is this correct?
From years 11-21 we had 12 popes.
There was a pope elected in year 8 and he was alive up until year 12 when a new one was elected.
pope 5 was from 8-11, pope 6 in 12, pope 7 and 8 | 13-14, pope 9 15, pope 10 16, pope 11 in 17, in year 21 pope 16.
So, there were popes from 5 to 16 on a period of 11 years. Pope 5 being in year 11, and pope 16 in year 21.
21 - 11 + 1 = 11 years...
Shouldn't the answer be 12 8 21, instead of 11 12 21?

It is obvious that the text of the task is completely unclear. There's no limit between difference of election years of first and last pope.
And somehow all of the answers automatically assume that last-first+1 <= Y.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 957 - Popes

Post by brianfry713 » Tue Oct 21, 2014 8:13 pm

Input:

Code: Select all

11
20
1
2
3
6
8
12
13
13
15
16
17
18
19
20
20
21
25
26
30
31

12
20
1
2
3
6
8
12
13
13
15
16
17
18
19
20
20
21
25
26
30
31

17
20
1
2
3
6
8
12
13
13
15
16
17
18
19
20
20
21
25
26
30
31
Correct output:

Code: Select all

11 12 21
11 12 21
13 6 21
From years 12 to 21 there were 11 popes elected. There was no pope elected in year 11. We are only interested in the years of election, not the number of popes in office during the time frame. The problem statement is misleading.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 9 (900-999)”