Search found 429 matches

by Per
Fri Aug 17, 2007 9:21 am
Forum: Volume 111 (11100-11199)
Topic: 11176 - Winning Streak
Replies: 18
Views: 12275

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...
by Per
Wed Mar 07, 2007 10:04 am
Forum: Volume 111 (11100-11199)
Topic: 11187 - Water Crisis
Replies: 12
Views: 4937

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.
by Per
Wed Mar 07, 2007 9:35 am
Forum: Volume 111 (11100-11199)
Topic: 11187 - Water Crisis
Replies: 12
Views: 4937

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...
by Per
Tue Feb 20, 2007 1:37 am
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 14628

Ah yes, thanks! I should have seen that.
by Per
Tue Feb 20, 2007 1:21 am
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 14628

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 ...
by Per
Fri Feb 16, 2007 5:46 pm
Forum: Algorithms
Topic: a problem from TIMUS
Replies: 3
Views: 2207

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.
by Per
Wed Jan 24, 2007 10:09 pm
Forum: Volume 111 (11100-11199)
Topic: 11163 - Jaguar King
Replies: 17
Views: 9920

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.
by Per
Wed Jan 24, 2007 10:06 pm
Forum: Volume 111 (11100-11199)
Topic: 11157 - Dynamic Frog
Replies: 22
Views: 13543

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...
by Per
Mon Jan 22, 2007 8:49 pm
Forum: Volume 111 (11100-11199)
Topic: 11156 - Continuous Drawing
Replies: 10
Views: 5293

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.)
by Per
Mon Jan 22, 2007 4:41 pm
Forum: Volume 111 (11100-11199)
Topic: 11156 - Continuous Drawing
Replies: 10
Views: 5293

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.
by Per
Wed Dec 13, 2006 1:49 am
Forum: Bugs and suggestions
Topic: PE issues
Replies: 11
Views: 4845

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 ...
by Per
Wed Nov 22, 2006 10:56 pm
Forum: Volume 120 (12000-12099)
Topic: 12096 - The SetStack Computer
Replies: 8
Views: 4274

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?
by Per
Mon Oct 23, 2006 11:16 pm
Forum: Volume 111 (11100-11199)
Topic: 11131 - Close Relatives
Replies: 8
Views: 3146

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...
by Per
Mon Oct 23, 2006 10:51 pm
Forum: Volume 111 (11100-11199)
Topic: 11131 - Close Relatives
Replies: 8
Views: 3146

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?
by Per
Mon Oct 23, 2006 10:46 pm
Forum: Volume 111 (11100-11199)
Topic: 11119 - Chemical Attraction
Replies: 19
Views: 7452

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 in the live archive", then we rememb...

Go to advanced search