Discussion @ 1247. Check a Sequence @ Timus Online Judge

mouse_wireless2 Mathematical hint // Problem 1247. Check a Sequence 30 Apr 2018 20:02

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.

Aditya Singh O(n) Solution // Problem 1247. Check a Sequence 11 Dec 2017 08:13

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 Надоело писать на чужом языке. Решение на русском. // Problem 1247. Check a Sequence 18 Jul 2017 22:28

Так как сумма всех элементов последовательности равна (S+N), то сумма всех элементов последовательности, в которой каждый элемент уменьшен на единицу, равна просто N.

Тогда если мы найдём в такой последовательности с уменьшенными членами отрезок с максимальной суммой и сравним сумму на нем с числом N, то мы узнаем ответ на задачу.

А именно, если эта сумма превосходит N, то ответ "NO".
В противном случае, ответ "YES".

Отрезок с максимальной суммой ищется за O(n) методом кумулятивных сумм.

Lincoln Time limit exceeded [2] // Problem 1247. Check a Sequence 27 Mar 2009 19:25

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'?

dmitri_quick Re: Time limit exceeded [1] // Problem 1247. Check a Sequence 10 Aug 2009 20:46

don't use brute force... O(n^2) n=30000 ===>>> time limit)

hint: you can don't use N in your solution

rip&pvs Re: Time limit exceeded // Problem 1247. Check a Sequence 14 Jan 2015 23:00

brute force (with some optimizations) works fine

hoan good test for WA#4 [1] // Problem 1247. Check a Sequence 19 Nov 2010 18:37

input:
6 10
2
2
2
0
10
1

output:
NO

Ahmadjon{TIU} Re: good test for WA#4 // Problem 1247. Check a Sequence 5 Dec 2014 22:33

it is incorrect test

jk_qq nice task. There's a hint for those who want it. // Problem 1247. Check a Sequence 23 Mar 2014 08:26

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.

Plamen_N TO ADMINS! Please add this test. [1] // Problem 1247. Check a Sequence 28 Aug 2013 22:51

30000 30000
0    |
0    |
.    | => 30000 lines with '0' on each
.    |
0    |

There are solutions that may get Time Limit.

Sandro (USU) Re: TO ADMINS! Please add this test. // Problem 1247. Check a Sequence 29 Aug 2013 19:52

The sum of all elements of the sequence must be equal to S + N (60000). Your test is incorrect.

Roman1994 wa?!?!?!? [2] // Problem 1247. Check a Sequence 15 Nov 2009 18:41

Edited by author 15.11.2009 18:42

Roman1994 Re: wa?!?!?!? [1] // Problem 1247. Check a Sequence 15 Nov 2009 18:41

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.

Roman1994 Re: wa?!?!?!? // Problem 1247. Check a Sequence 15 Nov 2009 18:42

why wa???

Oracle[Lviv NU] Hot to use fact, that sum=S+N? [1] // Problem 1247. Check a Sequence 23 Mar 2009 02:19

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?

Nick J Re: Hot to use fact, that sum=S+N? // Problem 1247. Check a Sequence 23 Mar 2009 18:12

probably if you subtract 1 from every element, you get simpler problem.

Latina_Matrix give me a wrong test please // Problem 1247. Check a Sequence 19 Nov 2008 09:53

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

_ksardas Bad tests [1] // Problem 1247. Check a Sequence 29 Feb 2008 23:44

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)

Huy Re: Bad tests // Problem 1247. Check a Sequence 17 Nov 2008 18:17

"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"

Aleksey S.S. Why my program got WA? [6] // Problem 1247. Check a Sequence 6 Apr 2003 13:06

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.

uuuuuuu Re: Why my program got WA? [2] // Problem 1247. Check a Sequence 6 Apr 2003 15:12

Think about simpler solution -> without array - just O(n) !!

Aleksey S.S. How do you do that??? [1] // Problem 1247. Check a Sequence 12 Apr 2003 00:28

AlexF Re: How do you do that??? // Problem 1247. Check a Sequence 2 Feb 2006 10:46

I got AC without any array! )

Savva'S Re: Why my program got WA? // Problem 1247. Check a Sequence 7 Oct 2006 23:33

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.

Savva'S Re: Why my program got WA? [1] // Problem 1247. Check a Sequence 7 Oct 2006 23:33

Artem Ladik Re: Why my program got WA? // Problem 1247. Check a Sequence 13 Aug 2008 14:19

use
for i:=1 to s do
for j:=i to s do
   begin
    ....
   end;

{1<=i<=j<=s}

Locomotive Hint 4 all.... you don`t need any array! just O(1*N)... [7] // Problem 1247. Check a Sequence 13 Mar 2003 11:35

Aidin_n7@hotmail.com

Popovich Antony I don't understand a problem [6] // Problem 1247. Check a Sequence 20 Mar 2003 03:49

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

ZhouWenzhe Re: I don't understand a problem [5] // Problem 1247. Check a Sequence 5 Apr 2003 14:38

(3+0)<=(3-2+1)+3

PTD_PDP O(n) [4] // Problem 1247. Check a Sequence 24 Oct 2004 16:01

Yes, just 373K and it's AC. Check that it's a sequence.

Beybut Re: O(n) [3] // Problem 1247. Check a Sequence 1 Mar 2007 15:15

manishmmulani Re: O(n) [2] // Problem 1247. Check a Sequence 2 Jan 2008 20:36

very nice problem !!!
jus a bit of thinking reqd

Piratek-(akaDK) Re: O(n) // Problem 1247. Check a Sequence 2 Aug 2008 19:32

Nice - i agree. For others only 10 strings - AC - 0.015

Piratek-(akaDK) Re: O(n) // Problem 1247. Check a Sequence 2 Aug 2008 19:32

Nice - i agree. For others only 10 strings - AC - 0.015

pperm Incorrect tests [2] // Problem 1247. Check a Sequence 3 Mar 2008 23:21

...
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 :)

Ostap Korkuna (Lviv NU) Re: Incorrect tests [1] // Problem 1247. Check a Sequence 4 Mar 2008 00:29

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!

Sandro (USU) All incorrect tests will be fixed (-) // Problem 1247. Check a Sequence 4 Mar 2008 00:41

alext [Vologda STU] Why AC? :) // Problem 1247. Check a Sequence 8 Feb 2008 02:43

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.

Leonid Chistov Why access violation? [1] // Problem 1247. Check a Sequence 18 Apr 2003 22:31

#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;
}

Dilyan Re: Why access violation? // Problem 1247. Check a Sequence 23 Jul 2004 04:20

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

AmBush What does it mean?? [2] // Problem 1247. Check a Sequence 3 Mar 2003 16:10

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

Tiberiu Danet Re: What does it mean?? [1] // Problem 1247. Check a Sequence 5 Mar 2003 23:14

It should be Ai + Ai+1 + ... + Aj.

A. Mironenko Re: What does it mean?? // Problem 1247. Check a Sequence 24 Jul 2003 01:59

> It should be Ai + Ai+1 + ... + Aj.

Right. It is missprint here.

Aleksey S.S. My program is wrong !!!??? But I think it is right?? [1] // Problem 1247. Check a Sequence 13 Apr 2003 22:23

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!!!

uuuuuuu Wrong solution (+) // Problem 1247. Check a Sequence 13 Apr 2003 23:48

Just think when it is most likely the inequality won't be true ! When
You realize it You'll get AC !

Style: flat | tree | nested
Thread Order: bubble | fixed

Discussion of Problem 1247. Check a Sequence