SIS - Strictly Increasing Subsequences
Given a series of integers, determine how many different strictly-increasing subsequences (of length 2 or more) are contained in that series.
For example, the series “3 1 1 5 9” contains the increasing subsequences “1 5”, “1 9”, “5 9”, “3 5”, “3 9”, “3 5 9”, and “1 5 9”, for a total of 7 different subsequences.
Input:
A series of space-separated integers.
Output:
The number of unique strictly-increasing subsequences within that series, as an integer.
Output | |
3 1 1 5 9 | 7 |
1 12 4 9 7 11 1 14 9 | 48 |
12 2 4 9 8 76 14 17 22 | 107 |
hide comments
(Tjandra Satria Gunawan)(曾毅昆):
2012-11-30 16:35:33
my C code: AC=0.00 sec
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-11-30 16:04:15
Got AC in 0.00s with almost brute-force algo O(n^2) with scanf/printf for I/O, input is exthremely small, even that the result is fit in 32-bit signed integer... that's all i know about the constraints for this problem... need a lot of experiment to know exactly size of input...
|
|
aristofanis:
2012-11-12 19:06:10
Last edit: 2013-03-25 18:59:43 |
|
:D:
2012-10-22 10:19:04
I know only what I've written below. As for the size of input sequence I only know it's small. Used std::vector, so I didn't care for an actual upper bound. |
|
Ehor Nechiporenko:
2012-10-19 09:36:32
@:D could you plese help and tell the constraints of the data? |
|
:D:
2012-10-17 12:18:57
This is a pretty good problem, but constrains seem to be low. 32-bit integer is enough for input numbers and 64-bit for result. Since I got 0.00 i assume input size is small. I'm leaving this in classical until someone shows/puts pretty much the same problem with bigger data. |
|
Francky:
2012-10-17 11:29:34
Constraints are not present, it is important. A problem with poor description is often put in tutorial section, be aware. |
Added by: | Ben Dilts |
Date: | 2012-10-12 |
Time limit: | 2.672s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |