| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Mathematical hint | mouse_wireless2 | 1247. Проверка последовательности | 30 апр 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. Проверка последовательности | 11 дек 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. Проверка последовательности | 18 июл 2017 22:28 | 1 |
Так как сумма всех элементов последовательности равна (S+N), то сумма всех элементов последовательности, в которой каждый элемент уменьшен на единицу, равна просто N.
Тогда если мы найдём в такой последовательности с уменьшенными членами отрезок с максимальной суммой и сравним сумму на нем с числом N, то мы узнаем ответ на задачу.
А именно, если эта сумма превосходит N, то ответ "NO".
В противном случае, ответ "YES".
Отрезок с максимальной суммой ищется за O(n) методом кумулятивных сумм. |
| Time limit exceeded | Lincoln | 1247. Проверка последовательности | 14 янв 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. Проверка последовательности | 5 дек 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. Проверка последовательности | 23 мар 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. Проверка последовательности | 29 авг 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. Проверка последовательности | 15 ноя 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. Проверка последовательности | 23 мар 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. Проверка последовательности | 19 ноя 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. Проверка последовательности | 17 ноя 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. Проверка последовательности | 13 авг 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. Проверка последовательности | 2 авг 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 окт 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 авг 2008 19:32 Nice - i agree. For others only 10 strings - AC - 0.015 Re: O(n) Piratek-(akaDK) 2 авг 2008 19:32 Nice - i agree. For others only 10 strings - AC - 0.015 |
| Incorrect tests | pperm | 1247. Проверка последовательности | 4 мар 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. Проверка последовательности | 8 фев 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. Проверка последовательности | 23 июл 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. Проверка последовательности | 24 июл 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. Проверка последовательности | 13 апр 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 ! |
