Query problems involving calculating GCD or LCM in a range?

How can we solve this kind of problem efficiently? Does any other data structure also helps in solving these kinds of problems? Some hints might be helpful. Even links to blog or papers. Thanks.

Let T be a String of length m. And S be a multiset of n characters. I need to find all substring of T in length n that are formed by characters of S.

example — S = {a,b,c,d,a} T = aabcdaah answer- {aabcd,abcda,bcdaa}

It should be running in O(m) times. It should also state, for each position i, the length of the longest substring in T starting at i that can be formed from S.

I was not sure of two pointer(not exactly) solution correctness. If possible can someone know any question similar to this on training site. Can It be find by some specific algorithm or data stricture or its just simple iteration?

I have recently tried to test the different kind of solution both on java 7 and java 8 and I found out that using Collection library or using class like BigInteger take less time in java 8 compare to java 7. But when you run normal program which has does not use class like HashSet, HashMap etc.

For example I will give you some small example I tested both on java 7 and java 8.

1. Using BigInteger Class we all know this class is very helpful sometimes for Java users. So I did some multiplication and addition and subtraction for 20000 times to check how much time it takes on codeforces platform to run. 8371132 it runs in Java 8 and takes 826ms displaying 3192KB memory 8371128 same code in Java 7 takes 2292 ms displaying 0 KB memory

2. In practice I solved 271D - Good Substrings using Java Library HashSet on String instead of trie data structure.

8356449 this code got accepted in java 8, and that time codeforces does not have Java 8 environment.

8356450 same code got TL in Java 7.

I don't know its Java 8 optimization or it is codeforces server.

Some more example using ArrayList of Integer and String java 8 — 8371287 685 ms with 0 KB memory displaying java 7 — 8371288 951 ms with approx 33 MB memory

So using Java 8 in big data is really helpful in codeforces. You can try on your own and use it accordingly.

I hope this article will helpful for those who are solving problems in java and sometimes their code get TL because their code is not that much optimized. If you are using Collection library Java 8 at codeforces gives you little freedom in terms of run time at least.

I am from that place where you can get no guidance.No one can help you if you stuck in problem.I tried reading some blog and some sites too but stuck or you can say confused from where to start , tried reading some advance dynamic programming or graph theory book but stuck when going for implementation,I can solve the basic problem (at max Div2 C or Div2 500 or Div1 250 not all the times) but when It comes problem like which require in depth dynamic programming , some advanced data structure or graph theory and many other, I got stuck like many people.I tried reading from CLRS and some more algorithm book, topcoder tutorial ,usaco training program and some blog too and I solved some problem but stuck some time and tried like that problem for 3 or 4 days.Some times I solved it on pen or paper but it need implementation .I started programming very late but read somewhere that it is never too late to learn something.I am good at mathematical thinking too and I know I can do that.I need guidance , So I request to some top coders like rng_58,Petr,tomek,Egor,yeputons and many others topcoder or at least red (It is no offense to other coders in case hurt I say sorry, if you like you can share too)to give your thought or suggestion how to good at it without any mentor . I have patience too , I like it very much ,I do other thing too but I want to try it to that level ,I succeed or not it depends on things which I can't control.