[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение теории 1, 2
Author Message
Mihail Dolinskiy (Online)

Topics: 1562
Messages: 38195

My Profile
2014 February Bronze: 2. Auto-Complete

To quickly find the first word that matches the prefix, we can use binary search on the sorted dictionary. This reduces the running time to O(N * L * log(W)). The full solution below uses C++'s convenient "lower_bound" function
 
Forum Index ->Олимпиадное программирование ->Обсуждение теории 1, 2
Time:0,062