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

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is derived from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam/contest/2334486/dashboard#s=p2\"><w:r><w:t>GJam 2013 Veterans Ocean View</w:t></w:r></w:hyperlink><w:r><w:t>. This is the Small data set witn N&lt;=50 and Q&lt;=4, guaranteed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Succinct Challenge statement:</w:t></w:r><w:r><w:t> Given a vector create the maximum length monotonically increasing vector by removing values. Report the number of values removed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> V , Vector length N&lt;=50 with values 1 thru 1000.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> Q , minimum quantity of removed values to produce a valid vector [0:4]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Examples:</w:t></w:r><w:r><w:t> [V] [Q]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[1 4 3 3] [2] for [1 4] or [1 3]\n[1 2 3 4 5] [0]\n[4 3 2 1] [3]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Commentary:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[1) The GJam Small test suite is not robust\n2) nchoosek(50,4) is too slow for Cody and the 100 cases\n3) The Large test suite is N<=1000 with some delete cases >4\n4) A Good Algorithm that solves the Large case is usually best to pursue\n5) GJam Competition allows one Large submission within 10 minutes of download \n6) <Large Suite Challenge>]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This Challenge is derived from <a href = "http://code.google.com/codejam/contest/2334486/dashboard#s=p2">GJam 2013 Veterans Ocean View</a>. This is the Small data set witn N&lt;=50 and Q&lt;=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&lt;=50 with values 1 thru 1000.Output: Q , minimum quantity of removed values to produce a valid vector [0:4]Examples: [V] [Q]<pre class="language-matlab">[1 4 3 3] [2] for [1 4] or [1 3]
[1 2 3 4 5] [0]
[4 3 2 1] [3]
</pre>Commentary:<pre class="language-matlab">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&lt;=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) &lt;Large Suite Challenge>
</pre>

Solve

Solution Stats

19 Solutions
11 Solvers

Last Solution submitted on Dec 06, 2018

Last 200 Solutions

Problem Recent Solvers11

Problem Tags

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

Solution Stats

Last 200 Solutions

Problem Recent Solvers11

Suggested Problems

More from this Author236

Problem Tags

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

Solution Stats

Last 200 Solutions

Problem Recent Solvers11

Suggested Problems

More from this Author236

Problem Tags

Players