if string(Say "str") contains '*' then it means that we can replace this '*' by another string(say "child_str") of any length (possibly 0). And this "child_str" must contain only bad characters(if it is not empty).

Assuming it is possible to replace every '?' in "str" by a good character(because if it is not possible than answer is "NO") which is equal to the character at the corresponding position in query string, If you are able to form some child_str such that both the strings become equal then answer is "YES."

Hmm, links works strange...

Check Topcoder(https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#A%20O(N),%20O(1)%20algorithm%20for%20the%20restricted%20RMQ)

Simply Farach-Colton and Bender algorithm :)

Or we can go offline and get O((n + q)α(n)) by Tarjan's algorithm.

It's just the basics of linear algebra. You can find it everywhere.

And you said that we considered 3! = 6 permutations of a, b and c, but as I saw in the code, there was only 3 permutations

It's because editoral for this problem is written by me, but solution is by Arpa.

Arpa, can you explain your solution?

We calculate the length of common part of paths from a to c and from b to c, so there is no sense in ordering vertices a and b, and we have only 3 variants for the third vertex.

I got to test 79 with Python's Regex :-) 28858499

Lowest common ancestor

Ugh, C isn't even conceptually hard, it's just extremely painful to code up.

Honestly, I'm really tired of problems which are obvious binary searches on doubles with horrible implementations and high chance of floating-point error.

Sorry, I've found a counterexample to my solution to C (although it passes all tests). To simplify it, assume that the right-hand-side limit is L=76 instead of 1000000. Now, consider the input with n=3 people and s=4.

• person p1 looks left at x1=24, and v1=1.
• person p2 looks left at x2=28, and v2=3.
• person p3 looks right at x3=36, and v3=1.

The right place for the bomb is x=x3=36, and it gives t=8.

But my program is not going to find it.

Take a look at mraron's answer below

I also didnt understand formula in editorial so I made it up myself. Lets say you want to calculate commong edges of paths a->c and b->c.

If level of lca( a,b ) is higher than max( lca(a,c), lca(b,c) ) that means a and b will meet up, and then together continue their path to lca( a,c) (in this case lca(a,c) == lca(b,c) ), and from there they will continue to b. So solution in this case is level[ lca(a,b) ] — level [ lca(a,c) ] + level[ b ] — level [ lca(a,c) ] , which is actually just level[ lca(a,b) ] — 2* level [ lca(a,c) ] + level[ b ]

If level of lca( a,b) is not higher than max( lca(a,c) , lca(b,c)) , that means a and b will separately go to c, without meeting before reaching their lca's with b, so solution is level [ b ] — max( level[ lca(a,b) ] , level [ lca( c,b) ].

So, you have 2 cases for 3 combinations of s,f,t : when s,f and t are destinations respectively. Code: http://mirror.codeforces.com/contest/832/submission/28877111

thanks for it ...i have used this and my solution get accepted ...but can u please explain how you land on this expression?

You're a genius. This was the only solution I could understand :)

Counter example:

Suppose we have the following graph:

     1
    /
   2
  /  \
 3    4

Note that the following expression uses floor division:

Let s = 3,  f = 2,  t = 4

But the answer in this case should be 1.

Did I misunderstand your formula?

Really clean solution. Thanks!

That is true! And since I used a slower lca method ( in such a way that my code complexity was ) checking only 3 instead of 3! possibilities made my code get AC instead of TLE

TLE code checking 3!

AC code checking 3

You use a sparse table, where the operation is just finding the max of two elements. Although it should be since you need to find the largest power of two less than a number. I guess this is negligible.

Read about it more here on topcoder

Mainly, look at the Sparse Table section.

I think they assume that power and log operations are .

It means Sweepline.

Yes :)

Your objective is to mark in an array (i.e. working in range [1,n] ) which places are suitable to put bomb in.

For each person you get information about a new range [a,b] of the array that is suitable. The naive approach would be to iterate from a to b on the array and set all those items to 1. But it cost O(n) in worst case for person, that is O(n * m) overall where n is the amount of places and m is the amount of people.

So to optimize you Just use an auxiliary array (name it sum[1,n]) and for each person that adds an a-b range you just increment sum[a]++ and sum[b+1]-- (the differences that would be in the final array). Note this cost O(1)

With those information stored in sum[1,n] you can, after processing all people ,generate the real array with suitable positions with a simple formula in O(n)

arr[i] = sum[i] if i = 1

arr[i] = sum[i] + arr[i - 1] if i != 1

There is a slight difference that in this case if arr[i] > 0 then the place is suitable, but the information we've generate is still useful.

And the overall complexity of the process is O(m + n)

Deleted