Skip to the content

The khan's horses

Problem

The khan's mail crosses the steppe from post to post, and at every post the rider changes horses. Batu, the stable keeper, won't waste fodder on horses he doesn't need. A horse beats another if it runs as fast or faster and lasts as long or longer, and is strictly better at one of the two; the beaten horse stays in the corral.

Write a function that takes speed and stamina, two lists of whole numbers of the same length: horse i has speed[i] and stamina[i] (they may be empty). Return a whole number: how many horses are beaten by no other horse. Two identical horses don't beat each other; both stay, unless a third one beats them.

With speed [5, 3, 4, 2] and stamina [1, 4, 3, 2], horse 3, with (2, 2), is beaten by horse 2, with (4, 3), which is better at both. Nobody beats horse 2: horse 0 falls short of it in stamina and horse 1 in speed. Horse 0 is the fastest and horse 1 lasts the longest, so they stay too. Three remain. With empty lists, 0.

Examples

  • The example

    [5, 3, 4, 2], [1, 4, 3, 2] → 3

  • Ties at one and wins at the other

    [5, 5], [3, 4] → 1

  • Two identical horses

    [4, 4], [6, 6] → 2

  • Nobody wins at both

    [1, 2, 3, 4], [4, 3, 2, 1] → 4

  • One horse beats them all

    [9, 1, 2, 3], [9, 4, 2, 1] → 1

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

Python

def unbeaten(speed, stamina):
    pass

JavaScript

function unbeaten(speed, stamina) {
}
Solve this challenge

It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.

More O(n²) challenges

See all challenges →