SimilarSequencesAnother
SRM 619 · 2013-12-22 · by ir5
Problem Statement
Two sequences A and B are called similar if they have the same length and have the following property: we can obtain two identical sequences by deleting at most two elements of A and at most two elements of B. (The elements deleted from A don't have to have the same indices as the elements deleted from B. The order of the remaining elements in each sequence has to be preserved.)
You are given
Constraints
- N will be between 1 and 100, inclusive.
- bound will be between 1 and 1,000,000,000, inclusive.
2 10 Returns: 10000
Any two 2-element sequences are similar. There are (10^2)^2 = 10,000 pairs of such sequences.
3 3 Returns: 687
In this case, two sequences are similar if they have at least one element in common. In other words, the two sequences are similar if there is a value that occurs in each of them. Let's count the pairs of sequences that are not similar. There are two possibilities: Each sequence contains the same value three times. For example, one sequence could be {1,1,1} and the other {3,3,3}. There are 6 such pairs. One sequence contains the same value three times, and the other contains the other two values, each of them at least once. For example, one sequence could be {2,3,2} and the other {1,1,1}. There are 2 * 3 * (2^3 - 2) = 36 such pairs. Thus, the total number of pairs of similar sequences is 3^6 - 6 - 36 = 687.
8 1 Returns: 1
100 123456789 Returns: 439681851
1 1 Returns: 1
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SimilarSequencesAnother with a public method int getCount(int N, int bound) · 55 test cases · 2 s / 256 MB per case