## Search found 429 matches

Fri Aug 17, 2007 9:21 am
Forum: Volume 111 (11100-11199)
Topic: 11176 - Winning Streak
Replies: 18
Views: 13179
Apart from solving this problem case by case by substituting the value of p in an early stage, we can also solve the general cases: the answer for a certain length l, A(l), can be expressed as a polynomial in p. If my hand calculations are right, the first four polynomials are: A(1) = p A(2) = 2p A...
Wed Mar 07, 2007 10:04 am
Forum: Volume 111 (11100-11199)
Topic: 11187 - Water Crisis
Replies: 12
Views: 5618
Per wrote:That gave around 7 secs, but using krijgers second optimisation would probably decrease it a lot more.
Yes, it did. Doing the full symmetry optimisations as well, it ended up on roughly 1 second.
Wed Mar 07, 2007 9:35 am
Forum: Volume 111 (11100-11199)
Topic: 11187 - Water Crisis
Replies: 12
Views: 5618
Quite similar to a problem named Bookcase in this years NWERC, but a bit more time hungry. Yeah, my solution was almost the same as my solution for Bookcase, with the same optimisations: keep track of which entries of the matrix are filled, prune away entries which can never improve upon the best s...
Tue Feb 20, 2007 1:37 am
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 16477
Ah yes, thanks! I should have seen that.
Tue Feb 20, 2007 1:21 am
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 16477
How about the following fix to mf's greedy algorithm: instead of choosing m.b as small as possible, first choose m.b-m.v as small as possible, and if there are several possible choices, choose m.v as large as possible. The intuition for the first criterion is that m.b-m.v is a more accurate measure ...
Fri Feb 16, 2007 5:46 pm
Forum: Algorithms
Topic: a problem from TIMUS
Replies: 3
Views: 2416
misof wrote:Note that the above solution, while probably fast enough, is really nasty to implement. Anyone with a better idea?
No. The problem is very similar to (but perhaps even messier than) http://acm.uva.es/p/v105/10572.html which I solved the way you described.
Wed Jan 24, 2007 10:09 pm
Forum: Volume 111 (11100-11199)
Topic: 11163 - Jaguar King
Replies: 17
Views: 10834

### Re: 11163 Jaguar King

paulmcvn wrote:Could anyone give me an idea for this problem?
I used IDA* search. The judge I/O is very kind, there are many cases where my solution is hopelessly slow.
Wed Jan 24, 2007 10:06 pm
Forum: Volume 111 (11100-11199)
Topic: 11157 - Dynamic Frog
Replies: 22
Views: 14730
Am I the only one here who used DP (complexity O(n^3)) ? I find the problem very similar to the 'round-trip trough canada'-problem, for those who know what I mean. Basically the idea is as follows. I also did DP (with the same state space as you), but it ended up being just one recursive call for e...
Mon Jan 22, 2007 8:49 pm
Forum: Volume 111 (11100-11199)
Topic: 11156 - Continuous Drawing
Replies: 10
Views: 5660
ardiankp wrote:Btw how do you get the 20 bound?
The only vertices which can have odd degree are the endpoints of the line segments, and there at most 2*N of those.

(And now I see that the bound is N < 10 rather than N <= 10, so you will have at most 18 odd vertices.)
Mon Jan 22, 2007 4:41 pm
Forum: Volume 111 (11100-11199)
Topic: 11156 - Continuous Drawing
Replies: 10
Views: 5660
It's a Chinese Postman problem.

There's a fairly easy O(x^2*2^x) solution where x is the number of odd nodes in the graph, which will be at most 20.
Wed Dec 13, 2006 1:49 am
Forum: Bugs and suggestions
Topic: PE issues
Replies: 11
Views: 5265

### Re: PE issues

Great! My list of solved problems is shorter by 60 in one swoop! If only FIFA had the same rejudging policy for their tournaments, Holland would become World Champion for 1978, for sure! Hmm, was this announced somewhere? I can't recall having received a mail about it, and I can't see it mentioned ...
Wed Nov 22, 2006 10:56 pm
Forum: Volume 120 (12000-12099)
Topic: 12096 - The SetStack Computer
Replies: 8
Views: 4799
Thanks, nice to hear you liked the problems. To clarify, the jury consisted of some of the best people from all over the region. I was actually the only one from KTH.

Out of curiosity, did anyone watch the webcast? If so, what did you think of it?
Mon Oct 23, 2006 11:16 pm
Forum: Volume 111 (11100-11199)
Topic: 11131 - Close Relatives
Replies: 8
Views: 3466
I'm sorry. I've re-re-read the problem statement, and it's getting clearer. So I'm suppose to give the minimum amount of lists that would allow the unambiguous reconstruction of the tree?[/list] Yes. Note that any set of lists you give will either uniquely define a tree or be invalid because it def...
Mon Oct 23, 2006 10:51 pm
Forum: Volume 111 (11100-11199)
Topic: 11131 - Close Relatives
Replies: 8
Views: 3466
danielrocha wrote:I'm having a really hard time understanding this problem's statement. I've re-read it some times and I still haven't figured it out. Could some one please try to explain it here?
Which part of the problem statement are you having trouble with?
Mon Oct 23, 2006 10:46 pm
Forum: Volume 111 (11100-11199)
Topic: 11119 - Chemical Attraction
Replies: 19
Views: 9362
I remember that last year during the coaches' meeting at the World Finals, Bill Poucher announced that from now on, all regional contests must publish their data. If by "must" you mean "should", and by "publish" you mean "send to Miguel so he can put the problem i...