You must use set< hash >, not set< string >. hash may be an int64.

Set compares strings using O(min(|s₁|, |s₂|)) time, so the complexity of your solution will be , where |s| is the length of the largest string. It should not pass.

There ans comparisons in set < string > , which take O(n) and the query of set < string > take O(len ^ 2 * log n) , not O(log n) , as set < int >

B can be solve in O(nlog(n)) just by maping the slops.

Just because we did not call it with a lowercase letter it does not means it is a constant.

If author was using 10⁹ instead of x, i think you would say complexity is O(1), would not you?.

I didnt really undestand what you mean,so why you believe that hashing should be never an intended solution for a task?

Assume that you have a randomized solution which fails with probability 10^- 50 — you should be familiar with such problems and such solutions from ACM contests, it is a common practice to do some stuff like "let's try some magic for some random permutation of input 1000000 times, let's pick some random elements, let's move in some random direction...". And given problem either have no exact solution for given constants, or this solution is extremely complicated. In this case author should not give this problem at all? Because it have no solution or those cheaters will solve it with wrong solution instead of complicated but correct one?

Now let's make your hashing solution non-deterministic. Simplest way to do it — by picking constants for your hashing function using random.

Maybe it is still a bad idea to ignore this 10^- 50 risk when you are running space expedition, but for ACM contests it sounds OK. At least for me. Maybe just because I am already used to such problems.

Once again, you may not like such problems for some reasons (like that analogy with space expedition); but Petr, Gassa, Burunduk1 and lot of other authors are often using such ideas in their contests, and usually feedback for problems with intended randomized solutions is positive — and I guess they would stop doing it in case most contestants does not like this stuff.

Agreed. always expecting a better solution with certainty.(without any possibility of making mistakes.

How to find anti-hash test case for H = (H * p + s[i]) % q ?

set works O(log), so it's NlogN

Is there a way to do it in O(n) in C++?

Putting doubles into set you're just waiting for the precision problems.

First of all, you can implement queue using two stacks. And two pointers algorithm can be implemented with a queue (moving right pointer is equal to adding new element to the end of a queue, moving left pointer is equal to removing front element).

For every element of every stack you can maintain maximum value in part of the stack bounded by this element (it is either given element or maximum value in part bounded by element below). This value for top element of a stack will be equal to maximum value in this stack.

And maximum in queue will be larger among two values for stacks.

Yes, i solved it using prefix tree. :) You can see my code here: http://mirror.codeforces.com/contest/514/submission/9841932

deleted

deleted.

You can invert digit, but you can't delete digit. So 95 cannot be converted into 4, only to 04, but it violates the statement.

В разборе не указан модуль. Например, я никогда не пишу по модулю 2⁶⁴.

ignore, оказывается, надо читать комменты полностью

прикольно :)

For the first question, the complexity is O(Llogn)... Because in the set<T>(T is a kind of type), we should give the way to compare two Ts, which means we should provide a function like bool operator<(const T&a,const T&b)const; However, the comparing function between two string is provided by #include<string> and it is O(L)

And the second question, in order to compare correctly, the comparing function provided is comparing char by char.

Например, 9842348

I think a prefix tree can be considered as a set of string(if we add a counter, it can be a multiset or map), and it can find whether a string is in the set(prefix tree) in O(length). I think it is correct.

Most hashes are certainly not unique or why do we use hash? If C is in ACM/ICPC, you can simply choose a prime other than 3 because the problem setter does not know which prime you used so he can not construct data against you. He can only guess some contestants will choose 3 and build some data to make them failed. However, in Codeforces, hackers can construct data against a solution. So you have to compare two strings themselves when the hash of them are the same. However the probability of two different strings have same hash is low so only a few strings will be compared. So, the hash helped you to evade TLE.

Let every letter has value ('a' — 0, 'b' — 1, 'c' — 2), and there is a KEY (in this case suitable to take KEY=3, usually it is prime number greater than size of alphabets(3)) than simplest hash of the string s[0], s[1] ... is value (s[0] * KEY ^ 0 + s[1] * KEY ^ 1 ...) modulo 2^64, where s[i] — value of the letter on i-th position

Size of alphabet is only 3, not 26. So, O(3*L*log(n)) ~ O(L*log(n)) is enough. Correct me, if I am not right.

"The number shouldn't contain leading zeroes."

No,

It will only check for 3*(Size of word to be checked) in worst case.

You can refer my code for clarification : 9857974

i.e.,

In the dfs recursion i've checked:

if(i==s.size())

if(x && cnt==1)

return true;

else

return false;

Check previous comment

newfp -= Pow*(p[j]-'a'+1)%PRIME_Q;
newfp += Pow*(k-'a'+1)%PRIME_Q;
After the first operation newfp can become negative (too large if you use unsigned type) and the second one might not return it to "positive" numbers.
Generally, if you want to subtract a from b modulo m, it's advised do it the following way: a = ((a - b) % m + m) % m;.

When you increase the right end of the segment, you add the corresponding number to the queue; when you increase the left end, you remove the number. We need a way to maintain the maximum of all numbers in the queue. Let's first do that for a stack. That's easy: we just maintain a parallel stack that contains current maximum. Now recall that a queue can be implemented with 2 stacks. If those stacks maintain their maximums, we calculate the maximum value in the queue as the max of the two maximums. Submission: 9842348

Use doubly-ended queue (Linked list) here. Whenever you have to insert a number, remove all the numbers from the back until you find a number that is more than it. After that, insert the number. In this way, you'll have a queue with numbers sorted in decreasing order from front to back.

Firstly you are computing length again and again using strlen() function inside a loop. Remember that strlen() is O(L). Secondly, you are also computing hashes using getHash() function inside a loop which is again O(L). Third, you are taking array of size 300001 instead of 600001. However the last one is not causing the TLE but Segmentation fault. Look at your corrected submission here

It may help:Matrix Expo Tutorial

You cannot delete digits...only invert them

I've also solved this problem with N log N algorithm. Got 'Exceed Time Limit' with python implementation, but eventually 'Accepted' with C++.

As I can see you have got runtime-error, not time limit. My solution's complexity was O(N**M*log^2 N) because of segment tree(I can code it faster than RMQ) + binary search and it passed.

I had the same problem, there is no need for the string to be in the function parameters
I solved it hours ago, my submission: 20196208

nice work bro! it helped me.

this C problem mush be solved using hashing concept,

can u help me with it:

243714293

what more optimization that can be cone to pass the testcases of problem C: Watto & Mechanism

Do i need to use two hashes and store them as a pair.

If done so, im confused about applying binary Search on it to pind the pair of two hash values