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 1914. GJam 2013 Veterans: Ocean View (Large)

Created by Richard Zapor

This Challenge is derived from GJam 2013 Veterans Ocean View. This is the Large data set with N<=1000 and Q<N<=1000, with typical 80.

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<=1000 with values 1 thru 1000.

Output: Q , minimum quantity of removed values to produce a valid vector (typical 80)

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) nchoosek(1000,80) is a little big
2) The Large test suite is N<=1000 with some delete cases >4
3) A Good Algorithm that solves the Large case is usually best to pursue
4) GJam Competition allows one Large submission within 10 minutes of download 
5) This was only solved by one entrant.

Small Suite Challenge

Algorithm Spoiler: A general method is to start at the end and build all unique length valid vectors. It is only necessary to maintain a Min Value and length for the potential solutions. Once all values are checked find the maximum solution length. There are three key steps in this method: 1) If vin(j)> Max of all solutions, start a new solution with length 1. 2) Find solutions that are 1 greater than vin(j). Update minimums of these solutions with vin(j) and increase length values. 3) Find solutions where mins>vin(j). Augment solution set by a single line of [vin(j),max length found +1]. 4) Find maximum length solution. This method solved all 100 large cases in < 2 seconds on Cody.

Tags

Problem Group

Solution Statistics

3 correct solutions 0 incorrect solutions
Last solution submitted on Oct 10, 2013

Solution Comments