Problem 1385D — a-Good String

Правка en1, от Schnider, 2020-07-20 01:07:52

So, I tried solving the problem in question, here is a link to it 1385D - a-Good String, but I faced a TLE. In the first submission 87154198 I tried to loop over the string every time to count the number of characters, and that is probably a stupid thing to do and takes a long time to execute even though I looks somewhat similar to the tutorial code. But I tried it again, 87258034 and basically I prepared an array beforehand that contains the number of characters up to that point, and that made the backtracking method O(1) in every iteration. I know that I'm doing a (26 * 131072) iterations per test case, but that's it. I'm thinking that the posted solution doesn't do a lot better because it's using the count() method, and cplusplus reference website says that count is O(n). Does anyone have any ideas why the posted solution is fine while mine got a TLE? Any help is appreciated

Теги #contest, #656 div3

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Schnider 2020-07-21 08:39:58 251
en1 Английский Schnider 2020-07-20 01:07:52 994 Initial revision (published)