Learning by Example timer 1초 memory 256MB

Problem 4: Learning by Example [Brian Dean, 2014]

Farmer John has been reading all about the exciting field of machine learning, where one can learn interesting and sometimes unexpected patterns by analyzing large data (he has even started calling one of the fields on his farm the "field of machine learning"!). FJ decides to use data about his existing cow herd to build an automatic classifier that can guess whether a cow will have spots or not.

Unfortunately, FJ hasn't been very good at keeping track of data about his cows. For each of his N cows (1 <= N <= 50,000), all he knows is the weight of the cow, and whether the cow has spots. Each of his cows has a distinct weight. Given this data, he builds what is called a "nearest neighbor classifier". To guess whether a new cow C will have spots or not, FJ first finds the cow C' in his herd with weight closest to that of C. If C' has spots, then FJ guesses that C will also have spots; if C' has no spots, FJ guesses the same for C. If there is not one unique nearest neighbor C' but rather a tie between two of FJ's cows, then FJ guesses that C will have spots if one or both these nearest neighbors has spots.

FJ wants to test his new automatic spot predictor on a group of new cows that are just arriving at his farm. After weighing these cows, he sees that the new shipment of cows contains a cow of every integer weight between A and B (inclusive). Please determine how many of these cows will be classified as having spots, using FJ's new classifier. Note that the classifier only makes decisions using data from FJ's N existing cows, not any of the new cows. Also note that since A and B can both be quite large, your program will not likely run fast enough if it loops from A to B counting by ones.