## Search found 429 matches

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