Is there an increasing subsequence of length X in a given sequence of length N ? can you find it in O(n)? - Codeforces

→ Pay attention

Before contest
Good Bye 2024: 2025 is NEAR
34:01:40
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	170
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	154
7	Dominater069	154
9	awoo	153
10	luogu_official	152

View all →

→ Find user

→ Recent actions

Detailed →

Is there an increasing subsequence of length X in a given sequence of length N ? can you find it in O(n)?

Revision en1, by X-O__O-X, 2021-04-01 11:42:01

Input: a sequence <A_1, A_2, ..., A_n> of integers and an integer X.

Output: true if there is a subsequence of length X in sequence A, false otherwise.

Is there an O(n) algorithm for this problem ?

History

Revisions

	Rev.	Lang.	By	When	Δ	Comment
	en2		X-O__O-X	2021-04-01 11:43:22	20	Tiny change: 'ere is a subsequen' -> 'ere is a strictly increasing subsequen'
	en1		X-O__O-X	2021-04-01 11:42:01	311	Initial revision (published)