Search found 44 matches

by danielrocha
Mon Oct 23, 2006 11:01 pm
Forum: Volume 111 (11100-11199)
Topic: 11131 - Close Relatives
Replies: 8
Views: 3281

I'm sorry. I've re-re-read the problem statement, and it's getting clearer. So I'm suppose to give the minimum amount of lists that would allow the unambiguous reconstruction of the tree?[/list][/quote]
by danielrocha
Mon Oct 23, 2006 4:46 pm
Forum: Volume 111 (11100-11199)
Topic: 11136 - Hoax or what
Replies: 31
Views: 17709

I'm not sure the problemsetter considered this, but this problem can be solved pretty easily using C++ STL's "multiset". At first I tought the test cases were made so that using STL would give a TLE, but it passed on 8s.
by danielrocha
Mon Oct 23, 2006 4:41 pm
Forum: Volume 111 (11100-11199)
Topic: 11131 - Close Relatives
Replies: 8
Views: 3281

I'm having a really hard time understanding this problem's statement. I've re-read it some times and I still haven't figured it out. Could some one please try to explain it here?
by danielrocha
Fri Jun 02, 2006 6:43 pm
Forum: Volume 110 (11000-11099)
Topic: 11036 - Eventually Periodic Sequence
Replies: 22
Views: 6328

A couple of observations about this problem: 1. There's no such case as (x+1)%N with N=11*10^6 in the judge test cases... I don't really understand why, since I didn't even submitted my code during the contest because it was to slow (4 seconds) to solve this case. 2. Floyd's Cycle detection algorith...
by danielrocha
Tue Nov 01, 2005 12:10 am
Forum: Volume 109 (10900-10999)
Topic: 10956 - Prime Suspect
Replies: 24
Views: 11885

I agree that it was a really interesting problem (made me learn a lot of things about the Miller-Rabin test), but the time limit was really too tight. Anyways, thanks for the tip, i "sieved" the interval instead of testing using Miller-Rabin and the problem ran in half the time: 0:02.877s. We did so...
by danielrocha
Mon Oct 31, 2005 8:39 pm
Forum: Volume 105 (10500-10599)
Topic: 10557 - XYZZY
Replies: 31
Views: 14724

I used Bellman-Ford algorithm with some modifications. Here's a sample input/output: Input 5 0 1 2 -60 1 3 -60 1 4 20 1 5 0 0 5 0 1 2 20 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 21 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 20 2 1 3 -60 1 4 -60 1 5 0 0 7 0 1 2 -98 2 3 5 -1 1 4 101 1 1 -60 1 6 -60 1 7 0 0 8 0 1 2 0 1 3 ...
by danielrocha
Mon Oct 31, 2005 4:19 pm
Forum: Volume 109 (10900-10999)
Topic: 10950 - Bad Code
Replies: 19
Views: 10491

Yes, you are correct. My previous input wasn't legal. I edited the post above, so now I hope it contains a valid input/output.
by danielrocha
Mon Oct 31, 2005 4:12 pm
Forum: Volume 109 (10900-10999)
Topic: 10957 - So Doku Checker
Replies: 31
Views: 15139

While we're on the Sudoku topic, has any of you tried to solve the problem 3285 ( http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3285 )? It a simple "count-how-many-different-solutions" Sudoku problem, but I can't develop an fast enough algorithm :( Can anyone who's already solved...
by danielrocha
Mon Oct 31, 2005 4:03 pm
Forum: Volume 2 (200-299)
Topic: 276 - Egyptian Multiplication
Replies: 22
Views: 5716

Here's a tip for anyone who's trying to solve this problem but keeps getting WA: don't worry about overflow (as I only used ints), print only the result % 100000 and if you read a blank line, terminate your program. It appears that the judge's input has one blank line at the end (and not a EOF as so...
by danielrocha
Sun Oct 30, 2005 3:07 pm
Forum: Volume 109 (10900-10999)
Topic: 10956 - Prime Suspect
Replies: 24
Views: 11885

There's one thing I don't understand: if the problemsetter's solution runs in 0:03.197s, don't you think that a time limit of 4s during the contest is a little extreme? I get the impression that we should code exactly like the problemsetter so we can get an AC solution. And, while in the topic, what...
by danielrocha
Sun Oct 30, 2005 2:59 pm
Forum: Other words
Topic: time limits
Replies: 7
Views: 3378

If I'm not mistaken, Valladolid Online Judge policy is that all problems have 10s of running time, unless there's an explicit request from the problemsetter. A lot of problemsetters add more inputs to their program, so that "way-too-brute-force" approaches don't work.
by danielrocha
Sun Oct 30, 2005 2:52 pm
Forum: Volume 109 (10900-10999)
Topic: 10950 - Bad Code
Replies: 19
Views: 10491

I'm sorry, but I don't think the above sample input is valid, since the problem clearly states that every character is replaced by a unique positive integer value So "a 0" is not a valid replacement, therefore the input is not valid. I'm not sure if there can be an input like "a 0001", but my AC pro...
by danielrocha
Sat Oct 29, 2005 10:53 pm
Forum: C++
Topic: can anyone tell me good compile for c++
Replies: 7
Views: 2750

http://gcc.gnu.org/
Website of the GNU GCC project. Most linux distributions already come with gcc/g++. If yours doesn't, look for some guide on how to install it. If you use Windows as your OS you should probably give Cygwin a try:
http://www.cygwin.com

Hope it helps,
by danielrocha
Sat Oct 29, 2005 9:07 pm
Forum: Volume 109 (10900-10999)
Topic: 10951 - Polynomial GCD
Replies: 7
Views: 3757

I'm not sure this will be very helpful, but this is the input we used during the contest: 3 3 2 2 1 1 4 1 0 2 2 2 3 3 2 2 1 1 2 1 2 1 3 4 1 0 2 2 2 2 1 2 1 100 10 1 2 3 4 5 6 7 8 9 10 11 10 1 2 3 4 5 6 7 8 9 10 11 100 5 10 0 0 0 0 0 5 15 0 0 0 0 0 1500 4 1 2 3 3 1 5 1 1 4 3 4 2 1500 4 2 4 5 5 2 5 1 ...
by danielrocha
Tue Oct 25, 2005 9:34 pm
Forum: Volume 109 (10900-10999)
Topic: 10944 - Nuts for nuts..
Replies: 35
Views: 15139

On the contest day we used a memoization technique like the one described above - O(N^2*2^N), and it got AC with 0.5s. This is a very interesting algorithm, and it should be able to solve problems up to 20 nodes, like this one: 3153 - Long Night of Museums http://acmicpc-live-archive.uva.es/nuevopor...

Go to advanced search