SPOJ.com - Problem SIS

Problem hidden

This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden on 2013-03-25 15:27:43 by [Trichromatic] XilinX

SIS - Strictly Increasing Subsequences

no tags

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

Submit solution!

hide comments



	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-11-30 16:35:33 my C code: AC=0.00 sec my python 2 code: AC=0.12 sec my python 3 code: AC=0.58 sec Time limit = 10 sec Is too high time limit... 1 sec is more than enough! Stop complaining, not many people know how to do the algorithm really fast, in a contest you will almost never be asked for the fastest algorithm, but maybe the fastest to code. The simple version of the problem easly can get 3 or 4 seconds. Last edit: 2013-03-11 05:05:36
	(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... David says: A lot of experimentation is 10 tries, use binary search, lol. Last edit: 2013-02-11 18:09:31
	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.

Submit solution!

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