NPC2015A - Eefun Guessing Words
Eefun is currently learning to read. His way of learning is unique, by trying to make every possible substring from a given string. However, when the string becomes longer, he can no longer remember all the substring. His friends want to test Eefun's skill by asking questions, given a string S, is there any substring that begins with letter X and ends with letter Y? According to Eefun, each substring contains at least 2 letters. As the given string S is pretty big, Eefun need your help to answer his friend's questions
First line of input contain a single string S which was given by his friends.
Second line contain a number N, the number of questions that Eefun's friends ask.
Next N lines each consists of 2 characters, X and Y
For each questions, output a single string "YA" if the substring exists, or "TIDAK" otherwise
(YA means yes and TIDAK means no in Indonesian)
simple one but time limit is too strict o(q)+o(|s|)+fast i/o got AC
sImple one AC in 1 go:-)
My approach is O(N + |S|) and I have checked with all the possible inputs I can think of and it runs fine locally. Cannot see why I am getting a WA.
I have WS on submission 16641335.
use faster I/O got tle because of that test case very strong
Could you suggest what might be wrong with O(Nlog(|S|)) approach I did in submission 15486818? I am getting TLE, and I think we need at least log |S| time to answer each query.
Give me some more test cases !!
Last edit: 2015-10-18 17:18:21
@mehmetin Thanks. Rejudged :)
I think the input is brokenLast edit: 2015-10-18 14:36:32