Search found 429 matches

by Per
Thu Jul 24, 2003 8:46 am
Forum: Volume 104 (10400-10499)
Topic: 10441 - Catenyms
Replies: 15
Views: 6625

Ok, an example. Consider the graph consisiting of four nodes and the five edges from to label 1 2 A 2 3 A 3 4 A 3 2 B 2 3 B The Eulerian path must begin at node 1. We will first choose the edge 1-->2 since it's the only edge from 1, but when we're at node 2, we have two choices. Since we want the le...
by Per
Thu Jul 24, 2003 12:21 am
Forum: Volume 3 (300-399)
Topic: 374 - Big Mod
Replies: 79
Views: 12015

Hm? O(log P) is simple, but how can you do it in O(1)? (Without using an O(M^3) lookup table...)

M can't be 0, btw.
by Per
Wed Jul 23, 2003 2:14 pm
Forum: Volume 100 (10000-10099)
Topic: 10044 - Erdos Numbers
Replies: 102
Views: 39917

I read the entire line first using fgets, that way I don't have to worry about crossing a '\n'. Upon closer inspection of my name-reading routine, I see that it was slightly more complicated than I described yesterday. Here's a detailed description (for reading an entire author, first and last name)...
by Per
Wed Jul 23, 2003 1:58 pm
Forum: Volume 104 (10400-10499)
Topic: 10441 - Catenyms
Replies: 15
Views: 6625

A small hint: It can be done exactly the same way as usual Eulerian path. You just have to be careful about: 1) How you choose among the edges going out from a node. 2) Where in the partial path you insert cycles. Now, how should you do these two things so that in every step, the partial path you've...
by Per
Tue Jul 22, 2003 7:44 pm
Forum: Volume 100 (10000-10099)
Topic: 10044 - Erdos Numbers
Replies: 102
Views: 39917

My AC program outputs: Scenario 1 Smith, M.N. 1 Hsueh, Z. infinity Chen, X. 2 Erdos, P. 0 Erdos, P. 0 Reisig, W. 1 Scenario 2 Smith, M.N. infinity Smith, M.N. infinity The second case is clearly incorrect, so I don't think you have to worry about such input. My AC program parses names like this: fir...
by Per
Mon Jul 21, 2003 5:42 pm
Forum: Volume 103 (10300-10399)
Topic: 10307 - Killing Aliens in Borg Maze
Replies: 54
Views: 17866

I'm not sure what they mean by the text, but I'll show why the output is 11. Let the borgs split once in the beginning, one group going upwards, one group going downwards, so we get (where B denotes a borg group): ##### #ABA### # A# # ### # # #ABA### ##### having walked a total of four steps (both g...
by Per
Mon Jul 21, 2003 3:28 pm
Forum: Volume 103 (10300-10399)
Topic: 10334 - Ray Through Glasses
Replies: 19
Views: 8636

Yes, and Thomas' formula is indeed one way to express fibonacci numbers. :) Thomas: your output for 10 and 20 are correct, but for 1000 you are way off. The correct answer contains 210 digits, begins with 11379... and ends with ...32376. My guess is that you probably have some small mistake in your ...
by Per
Mon Jul 21, 2003 3:20 pm
Forum: Volume 105 (10500-10599)
Topic: 10524 - Matrix Reloaded
Replies: 41
Views: 4525

Dominik, you should try this test case:

Code: Select all

1
5
It's always the simple things... :)
by Per
Fri Jul 18, 2003 7:28 pm
Forum: Volume 101 (10100-10199)
Topic: 10193 - All You Need Is Love
Replies: 23
Views: 9553

For the first test case, the answer is "Love is not all you need!", and the second test case will not appear in input (though if it did appear I guess the answer would be the same as for the first). zsepi: if you're a C/C++ programmer, the simplest way is to use the strtol function. In Java I think ...
by Per
Wed Jul 16, 2003 11:30 pm
Forum: Volume 101 (10100-10199)
Topic: 10114 - Loansome Car Buyer
Replies: 38
Views: 13652

10114 - Loansome Car Buyer

For the second test case, why isn't the answer "0 months."? (At this time the buyer owes 12*500 = 6000 dollars, but has a car worth 9974.99 dollars.) For the third test case, how can the answer be 49? After 49 months, the buyer still owes (60-49)*2400 = 26400 dollars, almost as much as the car was w...
by Per
Tue Jul 15, 2003 2:30 pm
Forum: Volume 105 (10500-10599)
Topic: 10524 - Matrix Reloaded
Replies: 41
Views: 4525

It looks ok. Since we're dealing with floats, what's a non-zero element? 1e-99? If you want better numerical stability, you should choose the maximum element as pivot, not just the first non-zero (I actually consider a matrix singular if I cannot find a pivot element whose absolute value exceeds 1e-...
by Per
Tue Jul 15, 2003 2:05 pm
Forum: Volume 105 (10500-10599)
Topic: 10526 - Intellectual Property
Replies: 10
Views: 5343

Ah, it seems my construction actually was faster than qsort. The bottleneck was my searches, where I simply used a routine which counts the number of occurences of a string by doing lower and upper bound (i.e. two binary searches instead of one). When I fixed this, the program ran 3.5 times faster o...
by Per
Tue Jul 15, 2003 1:12 pm
Forum: Volume 100 (10000-10099)
Topic: 10027 - Language Cardinality
Replies: 16
Views: 4041

Yeah, sure. I'm not very good at reading code (sometimes not even my own :)) but I could give it a try.
by Per
Tue Jul 15, 2003 1:07 pm
Forum: Volume 105 (10500-10599)
Topic: 10524 - Matrix Reloaded
Replies: 41
Views: 4525

Scythe: My output is correct. Just paste the matrix into Matlab or any other program capable of matrix inversion and check the answer. If you do that, you'll see that my output is correct whereas yours is incorrect (and if that output gave you AC, well, then the judge has way too easy input). Please...
by Per
Mon Jul 14, 2003 7:33 pm
Forum: Volume 100 (10000-10099)
Topic: 10027 - Language Cardinality
Replies: 16
Views: 4041

Try this input (when I had all of them handled correctly I got AC): 9 "aaa" "a"->"a" "aaa" ""->"" "@@@" "@"->"#" "#"->"{" "{"->"%/\=?" "%/\=?"->"&!+-" "&!+-"->"$" "$"->",:-.;_" ",:-.;_"->"abcdefghij" "abcdefghij"->"qwertyuiop" "qwertyuiop"->"0123456789" "@@@" "@"->"#" "#"->"{" "{"->"%%%%%%%%%%" "%%%...

Go to advanced search