OJ Board

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]

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.

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?

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 ...

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 ...

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 ...

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.

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 ...

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 ...

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 ...

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.

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 ...

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,

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 ...

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 ...