brain-0-dead's blog

HELP: Getting TLE in an impl problem.
By brain-0-dead, history, 3 years ago, In English

Prob: 88B - Keyboard

sample submission: 110834753,

What am I doing wrong here? I keep getting tle on test case 51.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The worst time complexity of your solution is O(q(nm)^2), and with given constraints it is bound to give TLE on some large test case. Rather then finding the closest shift and alphabet pair every time you encounter one, you should do this just once for each alphabet and store the result for later use. In this way your time complexity will reduce to O(q+26(nm)^2).

→ Reply