Search found 429 matches

by Per
Sat May 21, 2005 4:53 pm
Forum: Volume 108 (10800-10899)
Topic: 10853 - Pablito nailed a nail
Replies: 10
Views: 3320

My solution was based on observations of the kind "if the entire range [X, Y] are winning positions for player A when player A begins, then the range [X+Bmax, Y+Bmin] are losing positions for player B when player B begins". Swapping "winning" and "losing", and doing different player combinations, yo...
by Per
Sat May 21, 2005 1:38 pm
Forum: Volume 108 (10800-10899)
Topic: 10849 - Move the bishop
Replies: 44
Views: 15860

The answer can also be 0.
by Per
Thu May 12, 2005 9:35 am
Forum: Algorithms
Topic: IPSC 2005 invitation
Replies: 7
Views: 1339

Re: how to submit solutions...

We would like to create a contest where as many teams as possible can compare their skills. To be able to do some comparison we do need at least somehow similar conditions. It makes no sense to compare the result of an individual and a result of a 20-people team. We felt that three people per team ...
by Per
Tue May 10, 2005 7:42 pm
Forum: Algorithms
Topic: IPSC 2005 invitation
Replies: 7
Views: 1339

Re: how to submit solutions...

The difference between IPSC and e.g. ACM is that we allow you to use ANY method to compute the output data. Well, not ANY method... the rules state that a lot of useful tools, such as e.g. Matlab and Maple, are not allowed. Regarding that, have you considered easing up the rules a bit? I am of the ...
by Per
Tue Apr 12, 2005 10:27 pm
Forum: Other words
Topic: ACM regionals and finals questions..
Replies: 29
Views: 12766

Re: ACM regionals and finals questions..

the acmicpc live archive contains the names of all the questions correctly. However it doesnot allow us to view them. Isn't this kind of ridiculous? Well, someone has to format the problems into html documents. Just getting the names of the problems isn't much work, but converting them into html is...
by Per
Tue Apr 12, 2005 10:16 pm
Forum: Algorithms
Topic: Problem J - World Finals 2005
Replies: 11
Views: 6673

By the way, regarding the problem set: despite us not doing as good as we had hoped, I really enjoyed the problem set, it was definitely one of the better ones I've seen (and I've seen quite a few by now :)).
by Per
Tue Apr 12, 2005 10:12 pm
Forum: Algorithms
Topic: Problem J - World Finals 2005
Replies: 11
Views: 6673

Here's how we did problem D: First, finding the number of shuffles is fairly easy. Then, we construct a permutation P based on the "misplaced" elements of the input (if the element at the place where we should have an A was B (where we might have B = A), this permutation maps A -> B). Next we look a...
by Per
Tue Apr 12, 2005 9:55 am
Forum: Volume 10 (1000-1099)
Topic: 1047 - Zones
Replies: 17
Views: 5522

Yeah, we did it with bitmasks. I think you'll get something like O(n*t*(n choose k)) if you're not using bitmasks. How do you get rid of the factor n? For each subset of size k that you check, you have to add up k of n numbers. But if you're using bitmasks, wouldn't you have to check all n possible ...
by Per
Mon Apr 11, 2005 8:10 am
Forum: Volume 10 (1000-1099)
Topic: 1047 - Zones
Replies: 17
Views: 5522

Re: Problem J - World Finals 2005

Anybody knows a solution for problem J in the last ICPC World Finals that is more efficient than O(n^2 * 2^n)? Namely, checking all possible subsets? Isn't checking all possible subsets actually O((n+t)*(n choose k)), where k is the number of towers to be built? But apart from that, no, I don't kno...
by Per
Sun Mar 20, 2005 7:37 pm
Forum: Off topic (General chit-chat)
Topic: A request to University of Waterloo
Replies: 19
Views: 5459

But, it does cause a problem when deciding the difficulty level of a problem. If you look at the timings, a good number of people have the same time and memory usage as G.V. Cormack, despite there being a great deviation in the timing from other solvers. Too much as a coincident, isn't it. One thin...
by Per
Tue Mar 08, 2005 10:12 pm
Forum: Algorithms
Topic: Interesting-Chinese postman problem
Replies: 5
Views: 1827

Observer wrote:You may use backtracking/recursion to find the minimum pair matching cost. :)
There are also poly-time algorithms for finding a minimum weight matching, but they're quite complicated.
by Per
Wed Feb 23, 2005 12:59 am
Forum: Other words
Topic: Problem that is tree-rebild ?
Replies: 4
Views: 1248

For ordered trees, the answer is always 0 or 1, not very hard to prove by induction.

For unordered trees, the pre/post-order traversal is not well defined.
by Per
Mon Feb 21, 2005 4:23 pm
Forum: Volume 106 (10600-10699)
Topic: 10605 - Mines For Diamonds
Replies: 22
Views: 7541

Per, The only thing it cares about are the pairwise Manhattan distances of all the diamonds, and the diamonds' distance to the nearest '#' Does your solution imply that there always exists manhattan-distance long path between any two diamonds? I.e. that "manhattan convex hull" of diamonds contains ...
by Per
Tue Feb 15, 2005 2:23 pm
Forum: Other words
Topic: Programming Contest for Newbies 2005
Replies: 34
Views: 5746

Doesn't Java come with a built-in bignum library? Yeah, but here a very restricted variant of an old version of Java is used, coupled with a buggy compiler which produces incorrect code for some perfectly fine constructs. So for instance, the BigInteger/BigDecimal classes are not allowed (or do not...
by Per
Tue Feb 15, 2005 10:29 am
Forum: Other words
Topic: Programming Contest for Newbies 2005
Replies: 34
Views: 5746

A: I don't like bignum very much, but some of you say it's possible to solve without. I wish I could program in Java :( Java wouldn't really have helped you here. Knowing Java is more of a handicap than an advantage when it comes to solving UVA problems. I'm in doubt about A since I can't see a non...

Go to advanced search