OJ Board

Hint: Rolling hash might be a viable option here.

My solution based on dynamic programming on the Aho-Corasick trie build from the given patterns gives the same output. And as you should expect is getting WA. The cool thing is that I believe that even with negative probabilities it should still work correctly

I would like to use the occasion that prof. Cormac become involved
in this discussion to say THANK YOU to the Waterloo team for the excellent
problems they offered us during the last decade. I learnt a lot from
these problems.

I am extremely curious about the logic behind the author's solution of ...

This problem is very similar to problem "connect" from CEOI 2006:

http://www.hsin.hr/ceoi2006/tasks/day2/connect.pdf

And you may also look at the solution at:

http://www.hsin.hr/ceoi2006/tasks/solutions.pdf

Altough the ACM one is a bit easier.

1. I used epsilon of 1e-5 for the ternary search (and epsilon of 1e-8 for
the geometry stuff). By the way 1e-4 gives WA.

2. The search interval for x is from min_x to max_x of the polygon.
For a "fixed" x the serch interval for y is from min_y to max_y - where
min_y is is the y coordinate of the ...

Hmm... I don't know either... The only thing I am pretty sure about is that
DP probably won't pass no matter how hard you try.

What I did is a nested ternary search - the outer one over the x, and the
inner one over y for every x in the outer search. X and y are the coordinates
of the center of the circle.
In the contest it took a few submissions to figure out the right balance
between precision and runtime but finally I ...

I am not going to comment on a linear solution (I believe that no correct greedy
solution exists).

My advice to people that are trying to look at this as a typical DP problem:

1. The n^2 solution is obvious.

Let L be the length of the longest alternating (Mary) sequence ending
at element i of ...

I've got AC two programs - based on somewhat different logic.
For the case:
1
5
4
0 1
0 2
3 2
3 4
one outputs "yes", the other "no"...
Strange...

The input data seem to be a bit weak.
I managed to accept a code which is obviously wrong on pretty simple
test cases.

I solve the problem by using the function F[j] - the
probability that from i consecutive games you get no more than j
consecutive wins. This can be calculated with a complexity of n^2.
Having this computed it is not hard to see how to use it to solve
the actual problem.

Thank you Sohel!
I got your point and now I do like the problem even more! The BS + flow
approach is indeed a solution that is guaranteed to work. I feel that I
am close to a kind of a formal "proof" of the BS + greedy approach.
Would you mind if I send you tomorrow my solution with some comments
as ...

I understand that picking the farthest stones will result in minimum number of small rocks being exhausted. Also that when ever there is a big rock reachable, jump on that.
I feel that this is optimal, but I am unable to prove.
I felt exactly the same during the contest. So I just decided to ...

I personally did a binary search over the length of the longest jump
combined with a kind of greedy.
It would be interesting to here from Sohel did he consider some kind of
DP solution as a working one in the given time limits?
Nice problem, Sohel!

As you probably noticed the problem is almost identical to one of the
relatively recent problems on TopCoder (SRM 306). The only difference
is the time limit. In order to pass it the only thing I did additionaly
is to avoid calculating A^n on every recursive step. So I just kind of
turned the ...