Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

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

Created by Richard Zapor

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>

Tags

Problem Group

Solution Statistics

6 correct solutions 0 incorrect solutions
Last solution submitted on Sep 07, 2014