PAT 1085. Perfect Sequence Solution: sort + linear

Preface:

We give the algorithm to solve the programming ability test problem of perfect sequence with sorting and linear scan techniques. Binary search could also be used but it is slower and more tricky to implement.

Perfect Sequence Problem Definition:

Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.

Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:

10 8
2 3 20 4 5 1 6 7 8 9

Sample Output:

8

Perfect Sequence Problem Algorithm:

The key observation is the subsequence does not have to be in the same order as the original sequence does. We could first sort the input and for each element A[i], we find the max value after A[i] which could form the perfect sequence. To find this max value for A[i], one way is to binary search from i to N – 1, the total time complexity would be O(NlogN + NlogN).

Another key observation is that, once we find the max value for A[i] say it is A[j] such that A[i] to A[j] form the longest perfect subsequence, we have the observation that, the perfect subsequence starting from A[i+1] must contain all the values before and including A[j] because A[j] <= A[i] * p <= A[i+1] * p. So we could linear scan the sorted array to find the max value and the total time complexity would be O(NlogN + 2N), So we have the following accepted code by the PAT OJ:

long long linearScan(const std::vector<long long> &vec, long long n, long long p) {
	long long nMaxCount = 0;
	long long nCount = 1;
	long long next = -1;
	for (long long i = 0; i < n && nMaxCount; ++i) {
		--nCount;
		for (int s = next + 1; s < n && vec[i] * p >= vec[s]; ++s) {
			nCount++;
			next = s;
		}
		if (nCount > nMaxCount) nMaxCount = nCount;
	}
	return nMaxCount;
}
long long bs(const std::vector<long long> &vec, long long n, long long p) {
		long long llMaxCount = 0;
		for (long long s = 0; s < n && llMaxCount; ++s) {
			long long i = s, j = n - 1, mid = 0;
			while (i < j) {
				mid = i + (j - i) / 2;
				if (vec[mid] <= vec[s] * p)
					i = mid + 1;
				else
					j = mid - 1;
			}
			if (mid + 1 < n && vec[mid + 1] <= vec[s] * p)
				if (llMaxCount < mid + 1 - s + 1) llMaxCount = mid + 2 -s;
			if (vec[mid] <= vec[s] * p)
				if (llMaxCount < mid - s + 1) llMaxCount = mid + 1 -s;
			if (mid - 1 >= s && vec[mid - 1] <= vec[s] * p)
				if (llMaxCount < mid - s) llMaxCount = mid - s;
		}
		return llMaxCount;
}
int main() {
	long long N, p;
	scanf("%lld %lld", &N, &p);
	long long n = 0;
	std::vector<long long> vecSequence;
	for (long long i = 0; i < N; ++i) {
		scanf("%lld", &n);
		vecSequence.push_back(n);
	}
	std::sort(vecSequence.begin(), vecSequence.end());
	printf("%lld\n", bs(vecSequence, N, p));
	return 0;
}

Conclusion

To summarize, I just gave both linear scan and binary search algorithm to tackle PAT perfect sequence problem. Binary search is more tricky to implement and runs actually slower although it is the easiest one to think of.

 

(End. Original articles, please associate the author information and original URL with any reprints)


(Please specify the source  烟客旅人 sigmainfy — http://www.sigmainfy.com for any reprints,  

and please do not use it for commercial purpose)

Written on October 2, 2014