Connection Status:
Competition Arena > StrangeDictionary

StrangeDictionary

SRM 542 · 2011-11-22 · by ivan_metelsky

SRM 542 · 2011-11-22 · by ivan_metelsky · Simple Math
Class Name: StrangeDictionary
Return Type: double[]
Method Name: getExpectedPositions
Arg Types: (vector<string>)
Problem Statement

Problem Statement

A standard way of ordering words in a dictionary involves comparison of two words character by character, from left to right, until some two characters disagree. Jim thinks it's pretty boring, so he introduced a more complicated and less predictable scheme.

Given is a String[] words that contains N distinct words and each element is a single word. The length of each word is the same -- exactly L characters. To order words according to his scheme, Jim first generates a random permutation p[0], p[1], ..., p[L-1] of integers between 0 and L-1, inclusive. This permutation is generated only once and then considered to be fixed for the rest of the procedure. Using the permutation p, Jim can compare any two words as follows:

// returns -1, if A<B, 0, if A=B, and 1, if A>B
function Compare(Word A, Word B):
	for i = 0, 1, ..., L-1:
		a := character at position p[i] (0-based) in A
		b := character at position p[i] (0-based) in B
		if (a < b), return -1
		if (b < a), return 1

	return 0

Let Sorted be the list of the given words ordered according to Compare operator defined above. In other words, Compare(Sorted[i], Sorted[j]) = -1, for any i, j, 0 <= i < j < N. Let pos[i] be the 0-based position of words[i] within Sorted.

Obviously, the value pos[i] depends on the choice of the random permutation p. Assume that p is chosen uniformly at random. Return a double[] that contains N elements. Element i of the return value must be the expected value of pos[i].

Notes

  • Each element of the return value must have an absolute or relative error of less than 1e-9.

Constraints

  • words will contain between 1 and 50 elements, inclusive.
  • Each element of words will contain between 1 and 50 characters, inclusive.
  • All elements of words will contain the same number of characters.
  • Each character in each element of words will be a lowercase letter ('a'-'z').
  • All elements of words will be distinct.
Examples
0)
{"hardesttestever"}
Returns: {0.0 }

One word will always be at position 0 regardless of the permutation p.

1)
{"ab", "ba"}
Returns: {0.5, 0.5 }

If p = {0, 1}, then "ab" < "ba". If p = {1, 0}, then "ba" < "ab".

2)
{"aza", "aab", "bba"}
Returns: {1.0, 0.8333333333333333, 1.1666666666666665 }

p Sorted {0,1,2} aab, aza, bba {0,2,1} aza, aab, bba {1,0,2} aab, bba, aza {1,2,0} aab, bba, aza {2,0,1} aza, bba, aab {2,1,0} bba, aza, aab

3)
{"abababab", "babababa", "acacacac", "cacacaca", "bcbcbcbc", "cbcbcbcb"}
Returns: {1.0, 1.0, 2.5, 2.5, 4.0, 4.0 }
4)
{"g"}
Returns: {0.0 }

Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StrangeDictionary with a public method vector<double> getExpectedPositions(vector<string> words) · 81 test cases · 2 s / 256 MB per case

Submitting as anonymous