Search found 35 matches

by Ivan
Sun Aug 03, 2008 6:29 pm
Forum: Volume 114 (11400-11499)
Topic: 11475 - Extend to Palindrome
Replies: 32
Views: 13888

Re: 11475 - Extend to Palindromes

Hint: Rolling hash might be a viable option here.
by Ivan
Sun Jul 13, 2008 8:29 pm
Forum: Volume 114 (11400-11499)
Topic: 11468 - Substring
Replies: 2
Views: 1072

Re: 11468 - Substring

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 :)
by Ivan
Mon Oct 01, 2007 8:38 pm
Forum: Volume 112 (11200-11299)
Topic: 11293 - Tournament
Replies: 19
Views: 6682

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 th...
by Ivan
Sat Sep 22, 2007 4:57 pm
Forum: Algorithms
Topic: Japan 2006 - Manhattan Wiring
Replies: 1
Views: 2287

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.
by Ivan
Tue Aug 07, 2007 11:50 am
Forum: Volume 112 (11200-11299)
Topic: 11257 - New Marketing Plan
Replies: 23
Views: 8271

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 low...
by Ivan
Sat Aug 04, 2007 6:23 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4407

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. :)
by Ivan
Sat Aug 04, 2007 6:11 pm
Forum: Volume 112 (11200-11299)
Topic: 11257 - New Marketing Plan
Replies: 23
Views: 8271

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 go...
by Ivan
Sun Jul 15, 2007 5:33 pm
Forum: Volume 112 (11200-11299)
Topic: 11240 - Antimonotonicity
Replies: 33
Views: 12385

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 the gi...
by Ivan
Fri Mar 02, 2007 9:34 pm
Forum: Volume 111 (11100-11199)
Topic: 11175 - From D to E and Back
Replies: 18
Views: 8786

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...
by Ivan
Fri Mar 02, 2007 4:55 pm
Forum: Volume 111 (11100-11199)
Topic: 11175 - From D to E and Back
Replies: 18
Views: 8786

The input data seem to be a bit weak.
I managed to accept a code which is obviously wrong on pretty simple
test cases.
by Ivan
Tue Feb 27, 2007 11:32 am
Forum: Volume 111 (11100-11199)
Topic: 11176 - Winning Streak
Replies: 18
Views: 12722

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.
by Ivan
Sun Jan 21, 2007 8:09 pm
Forum: Volume 111 (11100-11199)
Topic: 11157 - Dynamic Frog
Replies: 22
Views: 13989

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...
by Ivan
Sun Jan 21, 2007 10:42 am
Forum: Volume 111 (11100-11199)
Topic: 11157 - Dynamic Frog
Replies: 22
Views: 13989

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 rely o...
by Ivan
Sun Jan 21, 2007 9:31 am
Forum: Volume 111 (11100-11199)
Topic: 11157 - Dynamic Frog
Replies: 22
Views: 13989

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!
by Ivan
Sun Dec 31, 2006 4:52 pm
Forum: Volume 111 (11100-11199)
Topic: 11149 - Power of Matrix
Replies: 42
Views: 19818

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 functi...

Go to advanced search