StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is a <code>O(n log(n))</code> answer in a reasonable amount of detail.</p> <p>First sort the people by beauty ascending, strength descending. Eliminate duplicates. (Either explicitly here, or implicitly by skipping over them in the next step.)</p> <p>Run through the list. As you go, maintain a balanced tree of people who are possibly on their way to being the next person in a maximal ascending chain. Each person should be stored with a length of the current chain, and a pointer to a linked list of the rest of the people in the chain. The tree should be sorted by strength.</p> <p>More specifically whenever you see a new person, find the next weakest person in the tree (nobody is OK), and construct a triplet <code>(person, length of chain, pointer to chain)</code>. Insert the person in the tree. If the next stronger person in the tree has a chain no longer than the current person, delete that person. All of these operations are <code>O(log(n))</code>.</p> <p>When you have finished processing all of the people, the maximal record in the tree will have a person at the end of a maximal chain of people, the length of the chain, and a pointer to a linked list with the rest of the people in the chain. That is your answer, print it out.</p> <p>To show you with your sample data, here is what you start with:</p> <pre><code>4 1 1 1 2 2 1 2 2 </code></pre> <p>This represents:</p> <pre><code>{person: 1, beauty: 1, strength: 1} {person: 2, beauty: 2, strength: 1} {person: 3, beauty: 1, strength: 2} {person: 4, beauty: 2, strength: 2} </code></pre> <p>Sort by beauty increasing, then strength decreasing (there are no duplicates) to get:</p> <pre><code>{person: 3, beauty: 1, strength: 2} {person: 1, beauty: 1, strength: 1} {person: 4, beauty: 2, strength: 2} {person: 2, beauty: 2, strength: 1} </code></pre> <p>To simplify things I'll just represent the tree by a sorted set. This is not how it should be represented in memory.</p> <p>After inserting person 3:</p> <pre><code>{person: 3, strength: 2, length: 1, next_person: null} </code></pre> <p>Next person 1 bumps person 3.</p> <pre><code>{person: 1, strength: 1, length: 1, next_person: null} </code></pre> <p>Then person 4 comes after person 1. (I've written the linked list as a nested data structure, in reality it should be a linked list.)</p> <pre><code>{person: 1, strength: 1, length: 1, next_person: null} {person: 4, strength: 2, length: 2, next_person: {person: 1, next_person: null}} </code></pre> <p>Then person 2 bumps person 1.</p> <pre><code>{person: 2, strength: 1, length: 1, next_person: null} {person: 4, strength: 2, length: 2, next_person: {person: 1, next_person: null}} </code></pre> <p>To find your answer look at the end of the tree, at person 4, points at person 1. And your answer is length 2, and then (from the best to the worst) persons 4 then 1.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload