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: 3466

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: 18385

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: 3466

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: 6793

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: 12522

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....
by danielrocha
Mon Oct 31, 2005 8:39 pm
Forum: Volume 105 (10500-10599)
Topic: 10557 - XYZZY
Replies: 31
Views: 15579

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: 11033

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: 15893

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 alre...
by danielrocha
Mon Oct 31, 2005 4:03 pm
Forum: Volume 2 (200-299)
Topic: 276 - Egyptian Multiplication
Replies: 22
Views: 6396

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: 12522

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: 3633

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: 11033

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&...
by danielrocha
Sat Oct 29, 2005 10:53 pm
Forum: C++
Topic: can anyone tell me good compile for c++
Replies: 7
Views: 2906

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: 3977

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: 15726

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