Large foot = High IQ?

Computer Science Level 5

Some people think that the bigger the size of a person's foot,the smarter he/she is. To disprove this,you want to analyze a collection of foot size/IQ measurements from $1000$ different people. You do this because you want to place as large a subset of people as possible into a sequence whose foot sizes are increasing but IQs are decreasing.

The following $1000$ line text file contains the data of the $1000$ test subjects.

Find the length $N$ of the largest subset of people in a sequence such that their foot sizes are strictly increasing and IQ is strictly decreasing .

Details and assumptions

Each line in the text file contains a string $(a,b)$ where $a$ is the length of the subject's foot and $b$ is his\her IQ.
Two people may have the same foot size, the same IQ, or even the same foot size and IQ.
All the measurements between $1$ and $10^4$ assume this is because weird units were used.

Sample Input

If the following (foot size, IQ data) for four people was given
1. (108,169)
2. (188,249)
3. (284,140)
4. (104,275)

The largest possible subset of people into a sequence whose foot size's are increasing but IQs are decreasing would be $(104,275)\rightarrow (188,249)\rightarrow(284,140)$ . And thus the length of the sequence $N$ would be $3$ .

Inspired from UVA problem

The answer is 62.

1 solution

Abdelhamid Saadi
Jul 4, 2015

Here is a solution is python 3.4:

def getsample():
    sample =[]
    f = open('sample.txt')
    for s in (f.read()).split('\n'):
        sample.append(eval(s))
    f.close()
    return sample

def smaller(a,b):
    return a[0]<b[0] and a[1]>b[1]

def maxpath(sample):
    following = [set() for e in sample]

    for i in range(len(sample)):
        for j in range(len(sample)):
            if smaller(sample[i], sample[j]):
                following[i].add(j)
    S = set()

    for i in range(len(sample)):
        if len(following[i]) > 0:
            S.add(i)
    N = 0

    while len(S) > 0:
        #print(len(S))
        T = set()
        for e in S:
            T = T.union(following[e])
        S = T
        N += 1
    return N

maxpath(getsample())

Large foot = High IQ?

The answer is 62.

1 solution

0 pending reports