Cody

Problem 1913. GJam 2013 Veterans: Ocean View (Small)

This Challenge is derived from GJam 2013 Veterans Ocean View. This is the Small data set witn N<=50 and Q<=4, guaranteed.

The GJam story goes that as Supreme Ruler you are annoyed by complaints of non-ocean views on a hillside. To resolve the issue a minimum number of homes will be removed to provide a maximum number of ocean view homes. The Elevation of the homes should monotonically increase, no equal values, from element 1 thru the end.

Succinct Challenge statement: Given a vector create the maximum length monotonically increasing vector by removing values. Report the number of values removed.

Input: V , Vector length N<=50 with values 1 thru 1000.

Output: Q , minimum quantity of removed values to produce a valid vector [0:4]

Examples: [V] [Q]

[1 4 3 3] [2]  for [1 4] or [1 3]
[1 2 3 4 5] [0]
[4 3 2 1] [3]

Commentary:

1) The GJam Small test suite is not robust
2) nchoosek(50,4) is too slow for Cody and the 100 cases
3) The Large test suite is N<=1000 with some delete cases >4
4) A Good Algorithm that solves the Large case is usually best to pursue
5) GJam Competition allows one Large submission within 10 minutes of download 
6) <Large Suite Challenge>

Solution Stats

78.95% Correct | 21.05% Incorrect
Last Solution submitted on Dec 06, 2018

Problem Recent Solvers11

Suggested Problems

More from this Author276

Problem Tags