Search found 429 matches

by Per
Sun Feb 13, 2005 8:33 pm
Forum: Other words
Topic: Programming Contest for Newbies 2005
Replies: 34
Views: 5821

The problemset was ok, was a pity that I only had time to participate for the first 1.5 hours, of which I spent a bit too much of my time trying to figure out which of my asserts on Problem C that went off, when I really should have spotted a very stupid algorithmic error in my solution. But at leas...
by Per
Tue Feb 08, 2005 8:13 pm
Forum: Volume 108 (10800-10899)
Topic: 10809 - Great Circle
Replies: 17
Views: 6057

There are infinitely many great circles passing through the two cities in that sample case, since the two points are antipodal.
by Per
Mon Jan 03, 2005 11:49 pm
Forum: Other words
Topic: About ICPC and NCPC contest certificate(Only for Bangladesh)
Replies: 7
Views: 2751

* After writing all these things I wanted to have a look at the ranklist of Dhaka site http://icpc.baylor.edu/icpc/regionals/ViewRegionalStandings.asp?ContestID=706 . Somehow, I feel that the median rule has not been applied. Teams who could solve a single problem are ranked. This would make many o...
by Per
Thu Dec 30, 2004 1:51 pm
Forum: Other words
Topic: HELP WITH NCPC
Replies: 54
Views: 13881

Re: hmm

To solve problem I just find readings related to "Ham Sandwich Cut". I recognized Problem I as a Ham Sandwich application, but since the only Ham Sandwich Theorems I've seen are existence theorems, it didn't help me much (I even tried thinking through the only proof I've seen to see if it would yie...
by Per
Tue Dec 21, 2004 11:48 am
Forum: Volume 107 (10700-10799)
Topic: 10798 - Be wary of Roses
Replies: 58
Views: 19839

No. Consider, for example, the test case 9 ####.#.## ####.#.## #..#.#.## ####.#.## ####P#### ##.###### ##.##.... ##.###### ##.###### There is only one minimum weight exit path, but applying your second step to that path would give you the answer "4", whereas the real answer is "2" (take two steps fo...
by Per
Wed Dec 15, 2004 5:42 pm
Forum: Volume 107 (10700-10799)
Topic: 10766 - Organising the Organisation
Replies: 20
Views: 5829

One can use a simple double-and-add algorithm for multiplication (analogous to square-and-multiply for exponentiation).
by Per
Wed Dec 15, 2004 5:39 pm
Forum: Volume 107 (10700-10799)
Topic: 10798 - Be wary of Roses
Replies: 58
Views: 19839

Then I think I really misunderstand the problem. The problem states that "You must come up with an escape path that tramples the fewest possible roses". I thought the gardener (me) can make decision when I am escaping. So for the following input: <snip> Originally, I think the answer is 2 because i...
by Per
Wed Dec 15, 2004 5:31 pm
Forum: Volume 107 (10700-10799)
Topic: 10766 - Organising the Organisation
Replies: 20
Views: 5829

My "intended" solution was to compute the answer modulo a prime bigger than 10^15. There is no need for CRT or BigInts, just regular modular arithmetic (including inverse).

A rational-based solution would probably get TLE (or well, at least the one I wrote is way too slow).
by Per
Wed Dec 15, 2004 11:53 am
Forum: Volume 107 (10700-10799)
Topic: 10766 - Organising the Organisation
Replies: 20
Views: 5829

It is a small mistake from my side that the problem is solvable using long doubles, I never thought to make sure that that wouldn't work. Bigints are highly likely to give you TLE, and regular doubles have no way of handling the precision required.

But anyway, all ways that work are good ways. :)
by Per
Wed Dec 15, 2004 11:48 am
Forum: Volume 107 (10700-10799)
Topic: 10798 - Be wary of Roses
Replies: 58
Views: 19839

I don't quite understand the problem... What's the purpose of 'P' in the input? And why I have to tramples 2 roses to escape for the sample? P has no significance. It is always in the middle square of the map. Since you don't know your direction, you can never be certain that your first step is nei...
by Per
Tue Dec 14, 2004 11:54 am
Forum: Volume 1 (100-199)
Topic: 193 - Graph Coloring
Replies: 93
Views: 21075

The problem is actually Maximal Independent Set. But of course, that's NP-complete as well. Cormen, Leiserson, Rivest say you should not confuse Maximal Set with Maximum Set. Maximal Set being just an independent set which can't grow more. You're absolutely right. I was a bit sloppy in what I wrote...
by Per
Sat Dec 04, 2004 2:49 pm
Forum: Algorithms
Topic: Dominating Sets in grraphs
Replies: 2
Views: 1324

Yes.
You can test all subsets of the vertex set.
by Per
Wed Dec 01, 2004 2:30 pm
Forum: Other words
Topic: Hidden advertisement in problem statement??
Replies: 4
Views: 1437

Since it's in the actual webpage, it seems plausible that the spyware is in the computer used to generate the page.
by Per
Tue Nov 23, 2004 8:32 pm
Forum: Volume 107 (10700-10799)
Topic: 10766 - Organising the Organisation
Replies: 20
Views: 5829

It was illustrated by the second case I posted, where the same pair occured many times. If you want, you can send me your solution and I'll try to see what's wrong with it.
by Per
Tue Nov 23, 2004 7:32 pm
Forum: Volume 107 (10700-10799)
Topic: 10766 - Organising the Organisation
Replies: 20
Views: 5829

Ooops, sorry, the answer should be 819224, you are correct. My input generation program outputted a number to standard err and I thought it was the answer, but I remembered incorrectly.

Go to advanced search