Hi,

I have wrote 2 solutions for this problem in java (actually the only difference is writing an iterative VS recursive segment tree). But both got me TLE.

I am asking here because I can see that there are 3 people managed to get this problem accepted with java. I am curious to know whether they are doing constant time optimisations or they have better approach than O((n + q)log(n + q)) ?

here is the link to the problem: http://www.spoj.com/problems/DQUERY/

Here is the link to my recursive segment tree code: http://ideone.com/itwocf

Here is the link to my iterative segment tree code: http://ideone.com/33m8yZ

If anyone has any way of accepting this problem with java please tell me about it.

I am having a lot of trouble with understanding suffix automaton with all it's details.

I have solved about 5 problems that contained very basic applications for it and I am stuck at some points.

I can't really understand how suffix links works, and what the congruence classes are. I know that the best resource is e-maxx site but actually I don't understand Russian and the translators (Google, Yandex , ... etc) sucks. Proofs are translated grammatically wrong and I really can't understand it in depth. The other resources like Crochemore's books are nice but they are actually long and they go beyond what an ACMer needs to understand a data structure.

So, it would be very nice if some one can explain suffix links and congruence classes to me.

Also, there are lots of people do calculate something called the right array in their codes and their comments are either Russian or Chinese and I can't really understand what and why is those 3 loops there.

I hope that someone can really explain all that.

I am trying to solve this problem for a long time https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=588&page=show_problem&problem=4450

obviously the brute force will TLE, any O(n^2) algorithm will TLE and any use of suffix array will also TLE.

So what I need actually is to find a way to hash the string from left and right and this requires a hashing function that hashes a string as it hashes his reverse.

Is this possible or there is another way to solve the problem.

I am trying to solve this problem and I am stuck in it

http://www.spoj.com/problems/AMR12H/

Any clue how to solve it and if someone can provide a full editorial for it I would be thankful.

I am getting TLE with this problem in java.

Here is the link to the problem http://www.spoj.com/problems/CT16E/

Here is my code http://ideone.com/bxG58H

Can I do more optimization to get it passed with java or I need to change the state representation or even the approach ??!!

I know that when we union 2 sets we compare the ranks of the representatives of the 2 sets and we put the smaller one inside the bigger one to ensure better complexity.

But the thing I don't understand is that why we don't update the rank when we do the find operation??

Actually when we do find we change lots of pointers and this changes actually the biggest depth of the set and correspondingly the rank of it. However the implementations I have seen doesn't change the rank while doing the find operation.

I have looked at Competitive Programming 3 implementation and the wikipedia implementation and both doesn't change the rank while finding.

I am new to the data structure so I need a list of problems that is solvable by suffix automaton to solve.

It is preferred to be sorted by difficulty. :D

Is the usage of multiple threads in Java allowed in the ICPC or no??

added after edit {

I know it won't differ in time but there is a powerful feature in Java that I want to know if I can use it or no.

The feature is the ability of changing the size of the memory stack for recursion.

I can set it for threads by this constructor

new Thread(null, new Runnable() {
    public void run() {
        new Solution().run();
    }
}, "1", 1 << 23).start();

Here the 1 << 23 is the new size for the memory Stack.

The whole solution will be written in the Solution().run() method.

So I don't need to do multiple threads and avoid time. I only need to make one single thread

}

Is this possible in the ICPC World Finals or not ?

I was solving this problem on SPOJ

http://www.spoj.com/problems/STRSOCU/

I got a c++ code accepted but the same code written in java gives NZEC error

here is my java code

Why should this code give an NZEC error??

http://ideone.com/eZ9BYM

Any one knows who is the inventor of the Z-algorithm??!!

I have wrote an O(n^2) solution for this problem

http://www.spoj.com/problems/STRSOCU/

here is my code

http://ideone.com/hEO6jv

What could be a better Solution for it?