hugh.hn
BAN USERi take back my comment. Just read Mihail's solution below and it is ingenious. This game does have a best strategy!
When n is even, it is true who ever moves first can choose the odd-pot series or the even-pot series, so whoever moves first wins.
When n is odd, whoever first is guaranteed to lose unless the first pot can be big enough to offset the difference between odd-pot series and even-pot series!
this is nice Mihail!
When n is even, it is true who ever moves first can choose the odd-pot series or the even-pot series, so whoever moves first wins.
When n is odd, whoever first is guaranteed to lose unless the first pot can be big enough to offset the difference between odd-pot series and even-pot series!
this solution does not scale. what happens if n is too large? recursion is practically impossible.
this problem is similar to the problem of finding 'perfect' chess strategy. Only that it is a reduced version. At each turn you only have to consider 2 choices, where as in chess it is many.
when n is large, the best you can do is some kind of 'look-ahead' algorithm to make sure by kth move you are not in a worse off position.
my attempt:
since a lot of English words have common characters between them (e.g., a majority of English words have letter 'e'), it is too expensive to loop through the entire dictionary every time you try to find a non-overlapping pair.
Rather, we could pre-compute the dictionary and divide words into 'buckets'. The English alphabet has 26 characters, so each word can belong to one or more buckets (eg: 'red' belongs to bucket R, bucket E and bucket D).
When searching for non-overlapping pair, the outer for() loop can be all words in the entire dictionary, so O(N).
For each word in the dictionary, we run a second inner for() loop to try to pair it with the longest non-overlapping word. For this inner for() loop, we only have to consider words that do not belong to any of the buckets of the first word. For example, if first word is 'red', we look at words that do not belong to buckets R, E and D. That will reduce significantly time spent in the inner for() loop from O(n) to O(k), where k is the number of words that have no overlap with first word.
Repeat for all words in dictionary. At all time, keep track of max multiple and update it every time we find a pair's multiple that beats current max.
the 'overlap' detection using bitmask is nice.
however, for finding max product length, it is incorrect to traverse the dictionary by decreasing order of length and return the first pair that has no overlap.
By starting out with the longest words, you are assuming that both the final 2 words have long length. But it could be the case that your 'found' pair has one long word and one short word. If that is the case, a pair of 2 average-length words can beat a pair of a long word and a short word. For example, 5 * 5 > 10 * 2
RepShayneRies, Android Engineer at ASAPInfosystemsPvtLtd
I am Shayne , working as a Playwright at Woilds , where I write scripts for theatrical productions. Works with more experienced ...
Repjaramsmond, Passenger rate clerk at Sportswest
I am a Passenger Rate Clerk . Charter representative Provides fare information to passengers traveling on non scheduled or chartered motor ...
RepCrystalKeane, Android test engineer at ABC TECH SUPPORT
Hello I am a skill trainer. Master's Degree in Industrial and Organisational Psychology and 10 years of experience working ...
RepFannieRamirez, Accountant at A9
I am a technically skilled Payroll bookkeeper responsible for the full charge bookkeeping function. My expertise includes knowledge of accepted ...
RepZairaMoore, Accountant at AMD
I am an ambitious and promising young chef with culinary education and prestigious intern and entry-level work experience. I trained ...
Replorfalinda8, Travel Agent at Creative Wealth
Hello, I am Janice. I help people make travel arrangements, which include booking flights, hotels, sightseeing tours, and making dining ...
RepKeciaFowler, Area Sales Manager at Auto NInja
My name is Kecia and I am a results-oriented Real Estate Appraiser Trainee with a strong determination to perform great ...
RepEddieCody, abc at A9
I am a creative freelance graphic designer with over 3 years of experience in developing engaging and innovative digital and ...
Repsylviatobins, Applications Developer at 247quickbookshelp
Hi, I am Sylvia Law librarian. I am an information resource expert. I work in law schools, corporate law departments ...
My solution:
- hugh.hn November 21, 20131) Find the list with the least number of elements. Let's call that list K.
2) Loop through all elements of list K
3) For each element of K[i], find the closest range that can include K[i], using numbers from other lists.
4) Compare all the ranges we found in step 3: best range for K[0], best range for K[1],... . Pick the best range out of them all.
Example
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
1) List 2 and List 3 both have same number of elems. We can pick List as the seed List.
2) Loop through all elements of List 2
3)
For '0': best range that can represent '0' is [0,5]
For '9': best range that can represent '9' is [5,10]
For '12': best range that can represent '12' is [12,18]
For '20': best range that can represent '20' is [20,24]
Out of those 4 ranges, [20,24] is the best