UVa OJ Board

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

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.

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

Ah yes, thanks! I should have seen that.

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

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.

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.

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

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

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.

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

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?

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

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?

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