Verti-Words: Difference between revisions
Jump to navigation
Jump to search
imported>Kmk21 Created page with "#assume the phrase will appear starting at some (x,y) #shift each line the minimum to the right to put the appropriate letter in the appropriate column #Iterate through all x,..." |
imported>Kmk21 No edit summary |
||
| Line 13: | Line 13: | ||
[[category:Precomputation]] | [[category:Precomputation]] | ||
[[category:Algorithm Medium]] | [[category:Algorithm Medium]] | ||
[[Category:Implementation | [[Category:Implementation Medium]] | ||
[[Category:Strings]] | |||
Latest revision as of 05:44, 27 August 2016
- assume the phrase will appear starting at some (x,y)
- shift each line the minimum to the right to put the appropriate letter in the appropriate column
- Iterate through all x,y pairs (only 1600 of them...)
- choose the winner from all start locations where we could successfully start the phrase based on the tie breakers in the problem statement
runtime: 1600*20(phrase length)*80(finding the letter on this line) = 2.5 million
Can make this faster if we really want by creating a lookup table for the shifts...for a given column letter and line, how far do we need to shift? For each line, this should take number of unique letters * length time, which is like 80 * 80 or so, and then 20 lines....so 1600*(20+80) rather than 1600*20*80. Isn't needed though