RendezvousProblem code: TR1 |
All submissions for this problem are available.
The problem statement has been updated
There are N cities in Byteland numbered 1 to N with city 1 as the capital. The road network of Byteland has a tree structure. All the roads are bi-directional. Alice and Bob are secret agents working for the Bytelandian Security Agency (BSA). Each secret agent is assigned a random city each month, where he/she must be stationed for the complete month. At the end of each month, they come to the capital to submit their reports to the head of BSA. They always take the shortest path from their city to the capital. If Alice is assigned city A and Bob is assigned city B then they meet at a city C which is common to both their routes to the capital and then travel together from C to the capital.
Alice and Bob wish to spend maximum time together in any trip. So for any pair of assigned cities (A,B) they meet at a city C such that C is the farthest city from the capital and appears in the shortest path from capital to A and capital to B. Since this happens each month they compute this for each pair of assigned cities (A,B) and store it in a matrix M, where M[A][B] = C, the city where they meet.
The importance of a city C(according to Alice and Bob), Im(C) is defined as the number of times C appears in their matrix M. Alice and Bob are interested in finding the importance of each city. Since this output can be large, output the sum S defined as S = (sum i=1 to N) i*Im(i) modulo 1000000007.
Input
First line of input contains an integer t (t<=25), the number of test cases. Each test case starts with an integer N (1<=N<=10000), the number of cities
The next N-1 lines contain two space separated integers u v (1<=u,v<=N) denoting a road from u to v.
Output
For each test case output the required sum S
Example
Input:
3
5
1 2
1 3
2 4
2 5
3
1 2
1 3
1
Output:
41
12
1
Explanation
For the first test case, the matrix M is:
1 1 1 1 1
1 2 1 2 2
1 1 3 1 1
1 2 1 4 2
1 2 1 2 5
and the corresponding importance array is: 15 7 1 1 1
so the required sum is 1*15 + 2*7 + 3*1 + 4*1 + 5*1 = 41For the second test case, the matrix M is:
1 1 1
1 2 1
1 1 3
and so the Importance array is: 7 1 1
So the required sum is 1*7 + 2*1 + 3*1 = 12For the third test case, there is only one city, so the Matrix M just has one entry 1, so S = 1
| Author: | akhilravidas |
| Date Added: | 10-04-2010 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
length of each road is same?
length of each road is same?
I rezolve this problem and it
I rezolve this problem and it works on my pc.But the problem is that when I submit it I get a SIGKILL error.
Can you tell me why? I found some explinations on the Internet but only for C++.I'm working in Pascal.
What causes a SIGKILL error?
@problem creater/Adimn can
@problem creater/Adimn
can we assume tree to be binary ?
I didn't understand the input
I didn't understand the input properly. What does it mean by a road from s to t?
@ADMIN All the roads are
@ADMIN
All the roads are bi-directional.
WHAT IS MEANT BY THIS LINE....???
EITHER THIS MEAN WE CAN MOVE UP OR DOWN (BIDIRECTION) OR EVERY ROOT HAVE 2 NODES....?
It means that you can move up
It means that you can move up and down
City 1 is always the root of
City 1 is always the root of the tree?
Shall we assume the tree to
Shall we assume the tree to be a binary tree?
@Mohit, Ankul: You shall
@Mohit, Ankul: You shall assume what you are told in the problem statement. You shall not assume anything else.
@Admin. I am getting runtime
@Admin.
I am getting runtime error(OTHER) in my code (C++) . I tried to find out the error using assert. But I did *not* get SIGABRT even when i placed assert(1==2) as the first line of my code !!. I also tried submittig a dummy code just to check if the amount of memory i allocated was within limits, and it worked fine. So, can you please tell me wheres the problem !!
I have noticed that it
I have noticed that it appears to be saying runtime error (OTHER) for all runtime errors now, I think that is a bug in the system. But no, you will not be told where the problem is in your code.
I'm getting NZEC error in
I'm getting NZEC error in pascal.The problem works on my pc.Can you give me any idea of how to pass over this error?
Did you read the message I
Did you read the message I just posted? You will not get hints during a contest, please do not ask for them.
Finally got accepted :)
Finally got accepted :)
Its so nice sometime. After
Its so nice sometime. After so many WA and after so many modification one time came that you are so confident that before submitting the code you know that it will be ACCEPTED. :D
Does the input have some sort
Does the input have some sort of order?
No, the edges can be in any
No, the edges can be in any order in the input.
Thanx!!!! One more doubt does
Thanx!!!!
One more doubt does a pair (s t) implies that t is at lower order than s?
No, the problem statement
No, the problem statement doesn't impose any such restriction.
Is this the case that the
Is this the case that the cities with smaller no are either above or at the same level as of cities with large number?
Like I said, you cannot
Like I said, you cannot assume anything not stated in the problem itself. You are given a list of roads, in any order; there are no restrictions at all over how these are numbered or ordered.
if the run time is 1s then
if the run time is 1s then what should be the complexity of the source code.....???
comment removed by admin
comment removed by admin
can dere be any cycle in
can dere be any cycle in graph ??
@Amritpal.. you should not
@Amritpal.. you should not ask ANYTHING related to Solution, be it complexity or anything.
@Pankaj, read the problem statement carefully, you will find the answer.
@Amritpal, You must not
First line of input contains
First line of input contains an integer t (t<=25), the number of test cases. Each test case starts with an integer N (1<=N<=10000), the number of cities
The next N-1 lines contain two space separated integers s t (1<=s,t<=N) denoting a road from s to t.
what does t stands for???
No of test cases or anything else??
Unable to understand the sentence "The next N-1 lines contain two space separated integers s t (1<=s,t<=N) denoting a road from s to t."
please please explain!!!!
t has been (wrongly) used in
t has been (wrongly) used in two different places, but the description is pretty clear. The first number is the number of test cases; after that, each pair of numbers are two cities that are joined by a road.
Hi Stephen Tx for such a
Hi Stephen
Tx for such a quick response.
Can you please explain a little more about matrix M is formed w.r.t given example
For the first test case, the matrix M is:
1 1 1 1 1
1 2 1 2 2
1 1 3 1 1
1 2 1 4 2
1 2 1 2 5
Tx in
@Badrinath, Stephen The input
@Badrinath, Stephen The input description problem statement has been updated to remove the confusion :)
@Badrinath: the matrix M is clearly defined in the problem statement itself.
Time limit:
Time limit: s
(nothing?)
^--- something wrong with the description? (i think it happens after the last update)
/sources/Main.java:7: class
/sources/Main.java:7: class Rendezvous is public, should be declared in a file named Rendezvous.java public class Rendezvous { ^ Note: /sources/Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. 1 error
I am uploading a file Rendezvous.java and have compiled the code with -Xlint option. There are no warnings or error. Any pointers to uploading solution?
Admins???
Admins???
Have you considered, say,
Have you considered, say, reading something like the FAQ?
@ Admin-If i submit a java
@ Admin-If i submit a java solution is the Main class only compiled??? or the classes I have in my code also get compiled???... i m getting wrong answer when I submit ... i think my solution is correct it may be a case of TLE but i do not thing it is wrong ... :)
If your code wasn't compiling
If your code wasn't compiling properly you would get a compile error. Wrong answer means your program is outputting the wrong results.
what is the limit of memory a
what is the limit of memory a program can use??
admin??
admin??
In case two person solve same
In case two person solve same number of prblems how the tie is broken
In case two person solve same
In case two person solve same number of prblems how the tie is broken
@sushil: ties aren't broken.
@sushil: ties aren't broken. In case of prize money, it is shared.
Suppose the rank list says:
1 A
2 B
3 C
3 D
3 E
6 F
then:
A gets cash prize for 1st
B gets cash prize for 2nd
each of C, D, E get cash = (cash prize for 3rd + cash prize for 4th + cash prize for 5th) / 3;
F gets cash prize for 6th
S must be output modulo
S must be output modulo 1000000007, or every member of this sum (i*Im(i) ) must be counted modulo 1000000007, but sum can exceed 1000000007?
@Yury You are expected to
@Yury You are expected to compute S = ( (sum i=1 to N) i*Im(i) ) modulo 1000000007
@Akhil, thanks!
@Akhil, thanks!
admin getting "internal error
admin
getting "internal error in system" on submission.
me too getting "internal
me too getting "internal error in system:(" upon submission
it works now, I saw my
it works now, I saw my submission which was about 1h ago accepted. But the ranks list has not updated.
admin I am getting "an
admin
I am getting "an internal error occurred in the system". Could you please clarify the meaning ?
i think the site is not
i think the site is not working properly everybody is getting the same error
yeah .. that too a day before
yeah .. that too a day before the end of the competition :( !
can a test case have given
can a test case have given disorder relation like lower level node relations enter first.
@amritpal... there is nothing
@amritpal... there is nothing as such mentioned in the problem so the question does nt arise..
@saransh there is no any
@saransh
there is no any restriction in question about this type of test case, then they may have a like this....
i had the same approach as
i had the same approach as stated in the editorial.....bt i kept on getting WA.....can anyone provide the input cases file they used to chck their code..or can admin provide the test cases used for this problem.....
It is really easy to come up
It is really easy to come up with input cases and check them by hand for this problem, you don't need other people to do that for you.
for small cases i m getting
You might want to generate a
You might want to generate a simple case of 10000 cities with roads from u to v like "1 2 , 2 3 , 3 4 , ... , 9999 10000 etc". Or the one where the network of roads is like a maximally packed (or whatever you call it) binary tree. Then a min level tree of degree 3 , etc .
Not that this would cover all the cases (it can ?? ) ... but they should check most overflow conditions you might have :-?