I haven’t heard about the trie DS till now, but I think I used a similar approach, and after a lot of submissions, I finally got AC 100pts.
I don’t know anything about suffix arrays either, I guess I’ll read about them now.
Basically I went through the entire string and saved the indices of all a’s,b’s,c’s…z’s separately in vectors.
Then, I would pick any one vector, and for each index look at index+1, and again store all indexes of a’s,b’s,c’s…z’s. If the number of alphabets is more than 1, only then will it be used, so whenever any such vector had more than 1 alphabet, then I would make an entry in a multiset of the number of alphabets.
Example: You start with the vector of all 1st a’s. Now you look at index+1 for each a, and find say 3 a’s 2 b’s 1 c
this means you have 3 strings of the form ‘aa’ , two of the form ‘ab’ and 1 of the form ‘ac’
The contribution we care about is only from where we have 3 equal strings ‘aa’ and 2 equal ‘ab’, we don’t care about ac,
further, we don’t need to recursively use the vector containing only this one c, because it will only lead to a string which will never match any other, as we only have 1 ‘ac’, we will always have at most 1 ‘aca’,‘acb’,‘acc’ etc.
Using this approach, I was able to calculate the required multiset, in which there were entries such as 2 2 2 3 3 4 4 etc, denoting the number of equal strings of various types.
I further shortened this to a simple vector which had pair of values, the actual number and number of occurrences, eg: in 2 2 2 3 4 4
we have entries for vector as pairs
(2 3)
(3 1)
(4 2)
As I had used a multiset, these values were already sorted, even in the created vector.
After this I simply used the logic of inverse modulo and saving inverse factorials to compute nCr. I later precomputed all values till 5000! % MOD and stored them in an array, and then when required computed r, n-r inverse factorials if they weren’t already computed and stored.
I was also sorting the given queries, so as to answer the same query value without having to recompute, like if k=3 is given 5 times in all, then it will be computed once, and then the result will be reused.
I was getting AC in all tasks except 1 of the last subtask.
To my surprise, in that task, if I would just terminate the program before the actual nCr calculating part, and only let the entire multiset and vector creation take place, it was taking a running time of 0.08 s, but after the nCr calc, it was giving TLE.
I tried using putchar_unlocked and using getchar for string input instead of scanf/printf, but the running times were almost exactly the same.
For a little more shocking experience, in one of the statements of the nCr calculating function, there were 3 terms being multiplied, and if I would just comment out 1 of them, it was giving WA with a running time of about 0.8s but no TLE.
Anyway, after a lot of tweaking around, I finally managed to get AC by removing 1 % operation in a certain loop. I was stunned that such a small change got my submission accepted! but well, at least it did get submitted finally.
Here’s my final solution CodeChef: Practical coding for everyone