Limits 10s, 32 MB

A long long time ago, I left the country that was my home and with my head full of brains and shoes full of feet I went on a journey through the long lonely shores, snoring sleepy mountains and lush green forests. Then I got completely lost.

On my path, I met a philosopher who was lost too but he seemed very content. I said, “How?”. He told me, “Eet izz phet!”. I said, “What?”. With his husky voice, he told me it was my fate to get lost and greatness is not in merely accepting the fate but in loving it. Which seemed like… philosophy.

We became good friends and one day I told him I was a programmer. The philosopher laughed, “Ho ho ho! I noo a good poggamming poblom”. Then he told me, he’ll give me a list of words and a bunch of queries. Each query will ask whether a particular word was in the list he gave me. I said, “Huh, that’s easy. I need to keep a set.” Then the philosopher laughed again and told me the only computer we have right now has 32 MB memory but the list is 50 MB and it’s in the hard disk.

I cried, “Oh philosopher! The problem is too big for me. I can’t even fit it in my memory!”. Philosopher nodded with a serious face and asked me if I thought Hercules could still become Hercules if he didn’t face Hydra and beasts way bigger than himself?

Now, it is your fate to be your own Hercules and face the same problem.


The test case will start with an integer NN (1N1000001 ≤ N ≤ 100000), then NN words will follow with one word in each line - this is the list. After that there will be another integer MM (1M1000001 ≤ M ≤ 100000) and then MM queries will follow with one word in each line. Each word will be at most 1000 ASCII lowercase alphabets (‘a’ - ‘z’).

You can assume the entire input file will be at most 50 MB.


For each query, print one line with the word yes\texttt{yes}, or no\texttt{no} depending on whether that word was on the list or not.



Because the way Java handles memory, it's pretty hard to solve this problem with Java. Even if you have figured out the solution to reduce memory usage, you'll have to use with InputStreamReader, read one by one character, stick to primitive types as much as you can, reuse your variables and call System.gc() after reading every 2000 words. Also note, the dataset was prepared with Linux, so newline is '\n', which is a 10 if you're reading with I wish Java handled memory differently, but it is fate.


Login to submit.



83% Solution Ratio
BSMRSTU_CSEEarliest, May '18
hmdkamrulFastest, 0.0s
hmdkamrulLightest, 7.6 kB
touhidurrrShortest, 97B
Toph uses cookies. By continuing you agree to our Cookie Policy.