Problem 1385D — a-Good String

Revision en2, by Schnider, 2020-07-21 08:39:58

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

UPD: I got it accepted with almost the same code, but with a few simple modifications. To be perfectly honest, I have no idea why the previous code gave a TLE while this one worked, but if you're interested, here's the code 87480391

Tags #contest, #656 div3

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Schnider 2020-07-21 08:39:58 251
en1 English Schnider 2020-07-20 01:07:52 994 Initial revision (published)