Problem 42806. GJam 2016 Rd1A: Rank and File (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/4304486/dashboard#s=p1\"><w:r><w:t>GJam Rd1A 2016 Rank and File</w:t></w:r></w:hyperlink><w:r><w:t>. This is the first 26 large cases with max N=50.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The GJam story is a matrix H(NxN) which has every row and column increasing. Each row and column is recorded on strips. The strips get scrambled and one gets incinerated. The goal is to reconstruct the missing increasing vector strip.</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> [M], matrix of size [2*N-1,N] of all rows and columns of H except one</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> [V], the missing vector of H not included in M</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> [M] [V]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[1 2 3;2 3 5;3 5 6;2 3 4;1 2 3] [3 4 6] \n[22 222;2 22;2 22][22 222]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>GJam 2016 Rd1A Matlab results show three qualifiers for Rd2.</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>Theory:</w:t></w:r><w:r><w:t> Brute force permutation will not succeed in a timely manner for N=50. Recreating the original matrix is possible in a timely manner. The min corner or the max corner will always be available. Evolving solution, no guessing, is possible. OR one can observe an inherent mathematical result to create a 1-line solution. </w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.go-hero.net/jam/16/solutions/1/2/MATLAB\"><w:r><w:t>GJam Rank_file solutions</w:t></w:r></w:hyperlink><w:r><w:t>.</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/4304486/dashboard#s=p1">GJam Rd1A 2016 Rank and File</a>. This is the first 26 large cases with max N=50.The GJam story is a matrix H(NxN) which has every row and column increasing. Each row and column is recorded on strips. The strips get scrambled and one gets incinerated. The goal is to reconstruct the missing increasing vector strip.Input: [M], matrix of size [2*N-1,N] of all rows and columns of H except oneOutput: [V], the missing vector of H not included in MExamples: [M] [V]<pre class="language-matlab">[1 2 3;2 3 5;3 5 6;2 3 4;1 2 3] [3 4 6] 
[22 222;2 22;2 22][22 222] 
</pre>GJam 2016 Rd1A Matlab results show three qualifiers for Rd2.Theory: Brute force permutation will not succeed in a timely manner for N=50. Recreating the original matrix is possible in a timely manner. The min corner or the max corner will always be available. Evolving solution, no guessing, is possible. OR one can observe an inherent mathematical result to create a 1-line solution. <a href = "https://www.go-hero.net/jam/16/solutions/1/2/MATLAB">GJam Rank_file solutions</a>.

This Challenge is derived from <http://code.google.com/codejam/contest/4304486/dashboard#s=p1 GJam Rd1A 2016 Rank and File>. This is the first 26 large cases with max N=50.

The GJam story is a matrix H(NxN) which has every row and column increasing. Each row and column is recorded on strips. The strips get scrambled and one gets incinerated. The goal is to reconstruct the missing increasing vector strip.

*Input:* [M], matrix of size [2*N-1,N] of all rows and columns of H except one

*Output:* [V], the missing vector of H not included in M

*Examples:* [M] [V]

[1 2 3;2 3 5;3 5 6;2 3 4;1 2 3] [3 4 6] 
  [22 222;2 22;2 22][22 222] 
 
GJam 2016 Rd1A Matlab results show three qualifiers for Rd2.

*Theory:* Brute force permutation will not succeed in a timely manner for N=50. Recreating the original matrix is possible in a timely manner. The min corner or the max corner will always be available. Evolving solution, no guessing, is possible. OR one can observe an inherent mathematical result to create a 1-line solution. <https://www.go-hero.net/jam/16/solutions/1/2/MATLAB GJam Rank_file solutions>.

Solve

Solution Stats

51 Solutions
10 Solvers

Last Solution submitted on Oct 15, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Rafael S.T. Vieira on 15 Oct 2020

A better description for this problem can be found at http://joonprogramming.blogspot.com/2016/04/google-code-jam-qualification-round-1a_17.html We have to find an NXN matrix, without repeating numbers at any row or column that must be ordered. And we have 2*N-1 strips of scrambled numbers, which can be rows or columns. The problem is to find what the missing strip is (notice that a NXN matrix has 2*N strips).

Problem Recent Solvers10

Problem Tags

Community Treasure Hunt

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

Start Hunting!