Verti-Words

From programming_contest
Jump to navigation Jump to search
  1. assume the phrase will appear starting at some (x,y)
  2. shift each line the minimum to the right to put the appropriate letter in the appropriate column
  3. Iterate through all x,y pairs (only 1600 of them...)
  4. 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