| Show all threads Hide all threads Show all messages Hide all messages |
| Mathematical hint | mouse_wireless2 | 1247. Check a Sequence | 30 Apr 2018 20:02 | 1 |
The property holds for all (i,j) if and only if it holds for all prefixes and all suffixes. You can prove this easily with pen and paper.
Prefix and suffix sums can be checked in linear time. |
| O(n) Solution | Aditya Singh | 1247. Check a Sequence | 11 Dec 2017 08:13 | 1 |
Subtract 1 from each element
Apply window to the array for max sum of S
#include <bits/stdc++.h>
using namespace std;
#define repl(i,x,n) for(long long i=(long long)(x);i<(long long)(n);i++)
#define rep(i,x,n) for(long i=long(x);i<long(n);i++)
int main()
{
//ifstream cin("input.in");
//ofstream cout("output.out");
ios::sync_with_stdio(0);cin.tie(0);
long n,s,a[100009],p=0;
cin>>n>>s;
bool flag=1;
rep(i,0,n)
{
cin>>a[i];
a[i]--;
}
rep(i,0,n)
{
p+=a[i];
if(p>s)
flag=0;
p=max(p,0l);
}
if(flag)
cout<<"YES";
else
cout<<"NO";
}
Edited by author 11.12.2017 08:23 |
| Надоело писать на чужом языке. Решение на русском. | Mahilewets | 1247. Check a Sequence | 18 Jul 2017 22:28 | 1 |
Так как сумма всех элементов последовательности равна (S+N), то сумма всех элементов последовательности, в которой каждый элемент уменьшен на единицу, равна просто N.
Тогда если мы найдём в такой последовательности с уменьшенными членами отрезок с максимальной суммой и сравним сумму на нем с числом N, то мы узнаем ответ на задачу.
А именно, если эта сумма превосходит N, то ответ "NO".
В противном случае, ответ "YES".
Отрезок с максимальной суммой ищется за O(n) методом кумулятивных сумм. |
| Time limit exceeded | Lincoln | 1247. Check a Sequence | 14 Jan 2015 23:00 | 3 |
used:
...
for(i=1;i<=S;i++)
for(j=i;j<=S;j++)
...
But the result is 'Time limit exceeded'. Please help, why 'Time limit exceeded'? don't use brute force... O(n^2) n=30000 ===>>> time limit)
hint: you can don't use N in your solution brute force (with some optimizations) works fine |
| good test for WA#4 | hoan | 1247. Check a Sequence | 5 Dec 2014 22:33 | 2 |
input:
6 10
2
2
2
0
10
1
output:
NO
|
| nice task. There's a hint for those who want it. | jk_qq | 1247. Check a Sequence | 23 Mar 2014 08:26 | 1 |
substract one from every element of sequence and search for prefix or suffix (I mean subsequence A_0, A_1, ..., A_j or A_k, A_{k+1}, ..., A_s) with negative sum. |
| TO ADMINS! Please add this test. | Plamen_N | 1247. Check a Sequence | 29 Aug 2013 19:52 | 2 |
30000 30000
0 |
0 |
. | => 30000 lines with '0' on each
. |
0 |
There are solutions that may get Time Limit. The sum of all elements of the sequence must be equal to S + N (60000). Your test is incorrect. |
| wa?!?!?!? | Roman1994 | 1247. Check a Sequence | 15 Nov 2009 18:42 | 3 |
Edited by author 15.11.2009 18:42 program Project286286;
{$APPTYPE CONSOLE}
uses
SysUtils,Math;
var a,b,c:array[0..2000000]of longint;
i,j,m,n,f:longint;
function RMQ(l,r:longint):longint;
var res,i,j:longint;
begin
i := l + n - 1;
j := r + n - 1;
res:=0;
while i<=j do
begin
res := max(res,max(a[i],a[j]));
i:=(i+1) div 2;
j:=(j-1) div 2
end;
result:=res;
end;
begin
reset(input,'input.txt');
rewrite(output,'output.txt');
readln(n);
for i := 1 to n do
readln(c[i]);
for i := 1 to n do
c[i]:=c[i]-1+c[i-1];
for i := 1 to n do
b[i]:=c[i]-c[i-1];
for i := n to 2*n-1 do
a[i]:=b[i-n+1];
for i := n-1 downto 1 do
a[i]:= max(a[i*2],a[i*2+1]);
for i := 1 to n - 1 do
if rmq(i+1,n)-c[i-1]>n then
begin
writeln('NO');
halt(0);
end;
writeln('YES');
end. |
| Hot to use fact, that sum=S+N? | Oracle[Lviv NU] | 1247. Check a Sequence | 23 Mar 2009 18:12 | 2 |
How to use information about sum of entire sequence? I've solved this problem for any sum of sequence, not only S+N. But algo is quite complicated. Is there any way to simplify algo using information about sum of sequence? probably if you subtract 1 from every element, you get simpler problem. |
| give me a wrong test please | Latina_Matrix | 1247. Check a Sequence | 19 Nov 2008 09:53 | 1 |
My program works like that:
int sum = 0;
int sum1 = 0;
int i = 0;
for( int j = 0; j < s; j++)
{
cin >> temp;
sum1 += temp;
if( sum1 > n + j + 1)
{
cout << "NO" << endl;
return 0;
}
if( temp < 3)
{
sum = 0;
i = j + 1;
}
else
{
sum += temp;
if( sum > n + j - i + 1)
{
cout << "NO" << endl;
return 0;
}
}
}
cout << "YES" << endl;
==========> WA in #12 V_V |
| Bad tests | _ksardas | 1247. Check a Sequence | 17 Nov 2008 18:17 | 2 |
My first AC submission
on test
s = 5 n = 2
1 3 0 3 0
answers YES,
but correct is NO
(sorry for bad english) "No" is true.
because: a[1]=1 a[2]=3 a[3]=0 a[4]=3 a[5]=0;
sum=a[1]+a[2]+a[3]=6 > (4-2+1)+2=5 ,=> "No" |
| Why my program got WA? | Aleksey S.S. | 1247. Check a Sequence | 13 Aug 2008 14:19 | 7 |
var sum,s,n,i,j,k:longint; a:array[1..100]of longint;
begin
read(s,n);
for i:=1 to s do read(a[i]);
for j:=1 to s do
for i:=1 to j do
begin sum:=0;
for k:=i to j do sum:=sum+a[k];
if sum>j-i+n+1 then begin write('NO'); exit; end;
end;
write('Yes');
end. Think about simpler solution -> without array - just O(n) !! I got AC without any array! ) var sum,s,n,i,j,k:longint; a:array[1..30000]of longint;
begin
read(s,n);
for i:=1 to s do read(a[i]);
for j:=1 to s do
for i:=1 to j do
begin sum:=0;
for k:=i to j do sum:=sum+a[k];
if sum>j-i+n+1 then begin write('NO'); exit; end;
end;
write('YES');
end. var sum,s,n,i,j,k:longint; a:array[1..30000]of longint;
begin
read(s,n);
for i:=1 to s do read(a[i]);
for j:=1 to s do
for i:=1 to j do
begin sum:=0;
for k:=i to j do sum:=sum+a[k];
if sum>j-i+n+1 then begin write('NO'); exit; end;
end;
write('YES');
end. use
for i:=1 to s do
for j:=i to s do
begin
....
end;
{1<=i<=j<=s} |
| Hint 4 all.... you don`t need any array! just O(1*N)... | Locomotive | 1247. Check a Sequence | 2 Aug 2008 19:32 | 8 |
I don't understand a problem
Why the answer to sample input 1 is "YES" ?
If we take i = 2 and j = 3, then
(3+0)<>(3-2+1)+3 O(n) PTD_PDP 24 Oct 2004 16:01 Yes, just 373K and it's AC. Check that it's a sequence. very nice problem !!!
jus a bit of thinking reqd Re: O(n) Piratek-(akaDK) 2 Aug 2008 19:32 Nice - i agree. For others only 10 strings - AC - 0.015 Re: O(n) Piratek-(akaDK) 2 Aug 2008 19:32 Nice - i agree. For others only 10 strings - AC - 0.015 |
| Incorrect tests | pperm | 1247. Check a Sequence | 4 Mar 2008 00:41 | 3 |
...
int main()
{
...
scanf("%d%d",&s,&n);
sum=s+n;
for (i=0;i<s;i++)
{
scanf("%d",&t);
sum-=t;
...
}
while (sum);
...
return 0;
}
I have TLE4 ... My algo is O(n)...
I have TLE in "while (sum);"... I think in test4 sum of Ai not equal S+N...
sorry for my bad english :) Admins! I'm also sure that in test4 sum of all Ai is not equal to S+N !!! I just calculated the sum and if it was not equal to S+N I thrown the exception ("throw 0;"). And I got Crash on test4 !
Please, check test4! |
| Why AC? :) | alext [Vologda STU] | 1247. Check a Sequence | 8 Feb 2008 02:43 | 1 |
I've solved this problem by using algorithm:
my pseudo code:
......
for (i=0; i<S; i++) {
for (j=i; j<S and j<i+3; j++)
if (sum_from_I_to_J(i,j) > j-i+1 + N) then begin
out("NO");
return(0);
end;
for (j=i+S-10; j<S and j>=i; j++)
if (sum_from_I_to_J(i,j) > j-i+1 + N) then begin
out("NO");
return(0);
end;
}
out("YES");
....
It was a test solution, I did't thought that I'll got AC.
I don't understand, why it works?
Thanks.
ps
sorry for my bad english. |
| Why access violation? | Leonid Chistov | 1247. Check a Sequence | 23 Jul 2004 04:20 | 2 |
#include <iostream.h>
int main()
{
long S,N,Sum;
bool X;
int A[30000];
cin>>S;cin>>N;
Sum=0;X=1;
for(long i=1;i<=S;i++)cin>>A[i];
for(long i=S;i>=1;i--)
{
Sum+=A[i];
if(Sum>S-i+1+N)X=0;
}
if(X==0) cout<<"NO"; else cout<<"YES";
return 0;
} it has to ba int A[30001] not int A[30000]
just try it
Edited by author 23.07.2004 04:20
Edited by author 23.07.2004 04:20 |
| What does it mean?? | AmBush | 1247. Check a Sequence | 24 Jul 2003 01:59 | 3 |
According to problem rules:
Is it right that for all 1 <= i <= j <= S the following inequality
holds:
Ai + Ai-1 + ... + Aj <= (j – i + 1) + N?
I do not understand the last line.
if j>=i then why Ai + Ai-1 + ... + Aj
Does it mean
Ai+Ai-1+Ai-2+...+A1+Aj or Aj+Aj-1+Aj-2+Aj-3+...+Ai+1+Ai
if yes then waht should i do when i=j
Ai+Aj or olny Ai
It should be Ai + Ai+1 + ... + Aj. > It should be Ai + Ai+1 + ... + Aj.
Right. It is missprint here. |
| My program is wrong !!!??? But I think it is right?? | Aleksey S.S. | 1247. Check a Sequence | 13 Apr 2003 23:48 | 2 |
Help me please!!!
-------------------------------------
var s,n,sum,i,j,k,a:longint;
procedure solve(i:integer);
var j:integer;
begin
for j:=i to s do readln;
end;
begin
readln(s,n); k:=0;
for i:=1 to s do begin
read(a); inc(k);
if a<>0 then sum:=sum+a
else begin
if sum>k+n then begin solve(i); write('No'); halt; end
else
if sum<k then begin sum:=0; k:=0; end
end;
end;
if sum>k+n then write('No') else write('Yes');
end.
----------------------------------
Thank you!!! Just think when it is most likely the inequality won't be true ! When
You realize it You'll get AC ! |
