Robots on MapProblem code: TR2 |
All submissions for this problem are available.
NOTE: The problem statement has been updated on June 3rd 2010 at 10:00pm Indian Standard Time.
Byteland is a kingdom of islands. Alice has N maps of the different islands constituting Byteland. Map of each island consists of cities, connected by roads. Being Byteland, the road layout of each island has a binary tree structure. Each island has a capital, which is the root of the binary tree of its map.
Alice is bored and plays the following game:
She chooses k out of these N maps and places a robot on the capital city of each map. Every robot is controlled by a common control string. If the present character of the control string is L(R), then all the robots move to the left(right) subtree on their map. All the robots follow the same control string and move on their respective maps.
A control string is valid with respect to a given map if it corresponds to a valid path on that map. A control string is considered valid for a given set of k maps if it is valid for each of the k chosen maps.
For example in a complete binary tree of 3 nodes, control strings "L" and "R" are valid and "LL" is an example of an invalid control string.
Alice is interested in knowing the longest control string which is valid for at least k maps, for each value of k. Can you find this for her?
Input
First line of input contains an integer t (t<=5), the number of test cases. Each test case starts with an integer M (1<=M<=100), the number of maps. Then M maps description follow.
The ith map description starts with an integer N (2<=N<=1000), the number of cities on the island. Each of the following N-1 lines contain two space separated integers u c v (1<=u,v<=N , c=L or R) which means a road between city u and city v on the ith island and if c is L(R) then v is in the left(right) subtree of u. The capital city of each island is the city with number 1.
Output
For each test case output M space separated integers, where the ith integer denotes the length of the longest valid control string she can obtain assuming she can choose i maps.
Example
Input: 2 3 5 1 L 2 1 R 3 3 L 4 3 R 5 4 1 R 2 1 L 3 2 L 4 3 1 L 2 1 R 3 2 5 1 L 2 2 L 3 3 L 4 4 L 5 6 1 L 2 2 R 3 3 L 4 4 R 5 5 L 6 Output: 2 2 1 5 1
| Author: | akhilravidas |
| Date Added: | 10-04-2010 |
| Time Limit: | 2 - 5 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
Is the empty control string
Is the empty control string (and therefore an answer of 0) valid?
output 'M' space seperated
output 'M' space seperated integers, right?
@Aravind: Yes, output M
@Aravind: Yes, output M integers.
what does "(...) which is
what does "(...) which is valid for at least k maps, for each value of k" mean? what is this "each value of k" ? if k is equal to 3, then "each value" is 0,1,2,3 ?
i think the output for the
i think the output for the 1st map of the 2nd case is wrong..It should be-- 4 1---the longest control string being LLLL..Plz tell me guys if i am wrong..
The input specification is a
The input specification is a bit messy:
"...which means a road between city s and city t"
s and t is the same as u and v?
I AGREE WITH VISHAL .......
I AGREE WITH VISHAL ....... PLZ SUM1 EXPLAIN ....
The output is correct. Read
The output is correct. Read the problem statement again. (For example, vishal refers to 'the output for the first map'; you aren't meant to output an answer for 'the first map'.)
I think Out put would
I think Out put would be
Sorry--Output:2 2 14 1Am I
what is meaning of tym limit
what is meaning of tym limit 2-5 s is it 2.5 sec.???
Plz sum1 xpalin da problem
Plz sum1 xpalin da problem !!!!
@admin what is the time limit
@admin
what is the time limit for this problem.....???
@Chris, yes @Aravind, it is M
@Chris, yes
@Aravind, it is M space seperated integers
@vishal, it means that it is a multiple input problem and each input file has an associated time limit. The lowest is 2s and the highest time limit is 5s.
@Amritpal, it is dependent on the test case file. Any good solution should pass in less than 2s
comment removed by admin
comment removed by admin
@pankaj: you are not supposed
@pankaj: you are not supposed to discuss approaches to the problem. You will be disqualified. Read FAQ !
what does "(...) which is
what does "(...) which is valid for at least k maps, for each value of k" mean?
what is this "each value of k" ?
plz answer...
"1 is always the capital", is
"1 is always the capital", is it necessary that 1st line of map description is always 1 c v(c=LorR, 1<=v<=n)??
Please some one help... and post some gud test cases..
@Marc, You must output the
@Marc, You must output the answer for every possible value that k can take.
@Saikat, you can assume that all inputs strictly follow the given input description and nothing more
Are test cases usually posted
Are test cases usually posted after the contest? I would really like to know which one is giving me TLE when I've been fast on all the huge test cases i've generated
@Tedrick you can find the
@Tedrick you can find the program used to generate all the inputs (before splitting them) here: http://pastebin.com/Ek10cPKZ
Since the input was fairly large, It could have been your I/O routines which were causing the TLE.