Problem 1914. GJam 2013 Veterans: Ocean View (Large)

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 Large data set with N&lt;=1000 and Q&lt;N&lt;=1000, with typical 80.</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;=1000 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 (typical 80)</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) nchoosek(1000,80) is a little big\n2) The Large test suite is N<=1000 with some delete cases >4\n3) A Good Algorithm that solves the Large case is usually best to pursue\n4) GJam Competition allows one Large submission within 10 minutes of download \n5) This was only solved by one entrant.]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1913-gjam-2013-veterans-ocean-view-small\"><w:r><w:t>Small Suite Challenge</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Algorithm Spoiler:</w:t></w:r><w:r><w:t> 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)&gt; 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&gt;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 &lt; 2 seconds on Cody.</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 Large data set with N&lt;=1000 and Q&lt;N&lt;=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&lt;=1000 with values 1 thru 1000.Output: Q , minimum quantity of removed values to produce a valid vector (typical 80)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) nchoosek(1000,80) is a little big
2) The Large test suite is N&lt;=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.
</pre><a href = "http://www.mathworks.com/matlabcentral/cody/problems/1913-gjam-2013-veterans-ocean-view-small">Small Suite Challenge</a>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 &lt; 2 seconds on Cody.

Solve

Solution Stats

26 Solutions
5 Solvers

Last Solution submitted on Sep 21, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 329484

2 Comments

2 Comments

Richard Zapor on 6 Oct 2013

Very elegant method to generate and utilize created optimal scores from the left. This solution is very fast and nearly linear with size.

Rafael S.T. Vieira on 21 Sep 2020

It is not close to linear. Richard, since he is using the function max for every number. It is at least O(n^2), in which n is size, and maybe even a little bit more since he is using indexing, another comparison(besides max), creating new arrays and so on. His code is small and functional though: kudos.

Problem Recent Solvers5

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1914. GJam 2013 Veterans: Ocean View (Large)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Problem 1914. GJam 2013 Veterans: Ocean View (Large)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Players