957 - Popes
Moderator: Board moderators
957 - Popes
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.
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.
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.
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.
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
Thanks.. ![:-)](./images/smilies/icon_smile.gif)
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
![:-)](./images/smilies/icon_smile.gif)
Last edited by helloneo on Thu Jun 28, 2007 6:20 pm, edited 1 time in total.
Try the cases.
Input:
Output:
Hope the weird input set helps.
.
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 :)
Code: Select all
11 12 21
11 12 21
13 6 21
![:wink:](./images/smilies/icon_wink.gif)
Ami ekhono shopno dekhi...
HomePage
HomePage
957-Popes
I can't realize why I'm getting WA.
Please give me some input output.
thanks...
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;
}]
-
- New poster
- Posts: 2
- Joined: Fri Sep 13, 2013 8:37 am
Re: 957 - Popes
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 957 - Popes
Don't read from a file.
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 2
- Joined: Fri Sep 13, 2013 8:37 am
Re: 957 - Popes
@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 ?
Is there any other problem that can end with a RE ?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 957 - Popes
Hello all,
I'm getting RE and I can't find out the reason of that.
Here's my code:
Appreciate your help ![:-)](./images/smilies/icon_smile.gif)
EDIT:
For those who are getting RE notice that P<=100000 in the judge's input (not 5000 as in the problem statement).
I'm getting RE and I can't find out the reason of that.
Here's my code:
Code: Select all
Accepted
![:-)](./images/smilies/icon_smile.gif)
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.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 957 - Popes
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
http://online-judge.uva.es/board/viewto ... &hilit=957
Check input and AC output for thousands of problems on uDebug!
Re: 957 - Popes
Thanks a lot. Got Acceptedbrianfry713 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
![:-)](./images/smilies/icon_smile.gif)
Re:
Could someone tell me how is this correct?Jan wrote:Try the cases.
Input:Output:Code: Select all
11 20 20 numbers given in sample :) 12 20 20 numbers given in sample :) 17 20 20 numbers given in sample :)
Hope the weird input set helps.Code: Select all
11 12 21 11 12 21 13 6 21
.
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.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 957 - Popes
Input:Correct output:
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.
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
Code: Select all
11 12 21
11 12 21
13 6 21
Check input and AC output for thousands of problems on uDebug!