## Search found 40 matches

Sun Jan 23, 2005 5:42 pm
Forum: Volume 5 (500-599)
Replies: 67
Views: 44509
I got AC after several WA. http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:53290 You're right this is a multiple input problem, also the precision is difficult to get right. Personally, I implemented *exact* computation (which is possible because when you divide by 2 you always get a finite number ...
Fri Jan 21, 2005 7:16 pm
Forum: Volume 3 (300-399)
Topic: 357 - Let Me Count The Ways
Replies: 90
Views: 8270

### Re: 357 exceed time limit

I think your code is too slow. a O(1) solution (i.e closed form solution) is possible. But even if you don't find it, try to build a table in O(N) time, to get the number of ways for each integer between 1 and 30000 and then for each input just look up its value, instead of running the algo for each...
Fri Jan 21, 2005 4:38 pm
Forum: Volume 5 (500-599)
Topic: 514 - Rails
Replies: 79
Views: 25715

### Re: p514 WA

Your program returns No on this permutation:
1 2 3 4 5 10 9 8 7 6

If I understood the problem correctly, it should return Yes:
the first 5 coaches leave the station first in first out and the last five Last in First out , so it should return yes.
Fri Jan 21, 2005 3:56 pm
Forum: Volume 5 (500-599)
Replies: 67
Views: 44509

I haven't attempted to solve the problem but there are several errors I see in your program. 1) You shouldn't get the number of cases from the input stream . The first line isn't the number of cases. it is the first number fot which you have to produce an output. 2)The remaining part of your input c...
Wed Jan 19, 2005 11:51 pm
Forum: Volume 1 (100-199)
Topic: 108 - Maximum Sum
Replies: 233
Views: 25187
1) You have a very nice array overflow. the array can be 100 by 100 and you declared it 10 by 10 2)Your algo as far as I can judge is O(N^6), and that's too slow . so even if you correct all your bugs , you will get a Time Limit Exceeded error. These are the errors I saw, maybe there are others. The...
Wed Jan 19, 2005 8:31 pm
Forum: Algorithms
Topic: How to find permutation root?
Replies: 1
Views: 1453

### Re: How to find permutation root?

Of course you can find the nth roots of a permutation only if it has roots . e.g, odd permutations do not have square roots. Here are 2 links to find nth root of a permutation: 1- Description of a general algorithm to find the nth root of a permutation by Prof. Vaughan Pratt : http://groups.yahoo.co...
Wed Jan 19, 2005 1:15 am
Forum: Volume 5 (500-599)
Topic: 535 - Globetrotter
Replies: 20
Views: 6983
Well, I've used this formula in another problem and it really works!!! Please someone who have got AC, send me some I/O. Thx in advance :wink: I got AC, and there's several problem with your code at the top of this page . 1)If you enter a query with the 2 cities having the same name but not in the ...
Tue Jan 18, 2005 11:38 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9913
Thank you!
Tue Jan 18, 2005 1:09 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9913
Christian Schuster wrote:I just got AC after a few (7) tries using that Node Voltage Method!
Did you implement large integer operations (+,*,%,-) or was long long enough ?
Mon Jan 17, 2005 4:01 pm
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9913
Is there a way other than solving a linear system of equations? I don't think so . my background is in computer engineering and we took several electric circuits courses, and this problem is a very classical one . The method to solve it is called the "Node Voltage Method" (you can find several web ...
Sun Jan 16, 2005 2:51 am
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13477
Abednego wrote:All submissions got rejudged because the output file had changed. You might get an email saying that.
Ah, OK, your're right. And now I resubmitted a correct solution , and I got an accepted message. Thank you!
Sun Jan 16, 2005 2:08 am
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13477
AC at last. Well I am on the list of accepted solutions, but there's something weird. I didn't get an accepted notification, I only got Wrong Answer notifications, including after the fix. The error could be on my part, (maybe I made a successful submission, didn't notice which,and then modified th...
Fri Jan 14, 2005 11:39 pm
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13477
My result wich should be the same as domino's since we implemented the same algorithm is 3. Mine too returns 3 on this example. But maybe I have done a subtle error ? I check for the case with a single nest. I append a newline after each test case, including the last. I start with Case#1 not Case #...
Fri Jan 14, 2005 9:40 pm
Forum: Volume 108 (10800-10899)
Topic: 10805 - Cockroach Escape Networks
Replies: 38
Views: 13477
I'm the problemsetter of a similar problem in the Romanian contest abednego is talking about. The official solution I used in that contest outputs 8 not 7 on the example given above, I've implemented the algorithm sugested by the link mentioned before. Also I wanted to add that in the Romanian cont...
Fri Jan 14, 2005 1:54 am
Forum: Volume 108 (10800-10899)
Topic: 10806 - Dijkstra, Dijkstra.
Replies: 24
Views: 18137
I've written an AC program but i works in O(n^2*m*log n), i wonder how i can do it quicker. Is there exist any special algo to do it or it is a special combination of dijkstra algos... Yes, you can do it in m lg n by using the algorithm called "successive shortest path" described in these 2 documen...