Search found 35 matches
- Sun Aug 03, 2008 6:29 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11475 - Extend to Palindrome
- Replies: 32
- Views: 19059
Re: 11475 - Extend to Palindromes
Hint: Rolling hash might be a viable option here.
- Sun Jul 13, 2008 8:29 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11468 - Substring
- Replies: 2
- Views: 1602
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 ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
- Mon Oct 01, 2007 8:38 pm
- Forum: Volume 112 (11200-11299)
- Topic: 11293 - Tournament
- Replies: 19
- Views: 8282
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...
- Sat Sep 22, 2007 4:57 pm
- Forum: Algorithms
- Topic: Japan 2006 - Manhattan Wiring
- Replies: 1
- Views: 2719
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.
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.
- Tue Aug 07, 2007 11:50 am
- Forum: Volume 112 (11200-11299)
- Topic: 11257 - New Marketing Plan
- Replies: 23
- Views: 10120
- Sat Aug 04, 2007 6:23 pm
- Forum: Volume 112 (11200-11299)
- Topic: 11259 - Coin Changing Again
- Replies: 12
- Views: 5629
- Sat Aug 04, 2007 6:11 pm
- Forum: Volume 112 (11200-11299)
- Topic: 11257 - New Marketing Plan
- Replies: 23
- Views: 10120
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...
- Sun Jul 15, 2007 5:33 pm
- Forum: Volume 112 (11200-11299)
- Topic: 11240 - Antimonotonicity
- Replies: 33
- Views: 15952
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...
- Fri Mar 02, 2007 9:34 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11175 - From D to E and Back
- Replies: 18
- Views: 10332
- Fri Mar 02, 2007 4:55 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11175 - From D to E and Back
- Replies: 18
- Views: 10332
- Tue Feb 27, 2007 11:32 am
- Forum: Volume 111 (11100-11199)
- Topic: 11176 - Winning Streak
- Replies: 18
- Views: 14970
- Sun Jan 21, 2007 8:09 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11157 - Dynamic Frog
- Replies: 22
- Views: 17165
- Sun Jan 21, 2007 10:42 am
- Forum: Volume 111 (11100-11199)
- Topic: 11157 - Dynamic Frog
- Replies: 22
- Views: 17165
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...
- Sun Jan 21, 2007 9:31 am
- Forum: Volume 111 (11100-11199)
- Topic: 11157 - Dynamic Frog
- Replies: 22
- Views: 17165
- Sun Dec 31, 2006 4:52 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11149 - Power of Matrix
- Replies: 42
- Views: 24300
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...