All submissions for this problem are available.
Professor Verma and Professor Sharma from Thapar University are visiting a number of colleges across India
to deliver lectures on "Dynamic Advancements in Programming".
Professor Verma received the itinerary of Professor Sharma and is matching it with his itinerary, trying to find longest duration for which they can talk. They are both ready to shorten/extend their stay at a particular college to meet each other but in no way can they change their order of visiting the colleges.
Longest duration here is defined as the maximum number of colleges where they can meet in between their travels.
Given the list of colleges visited by each professor in order,
You have to find the longest duration and impress Professor Verma. (Remember ESTs are coming up!!)
The first line of the input contains an integer T denoting the number of test cases.
- Then T test cases follow, each containing three lines.
- The first line consists of two space-separated integers N and M
- The second line consists of N space separated names of colleges visited by Professor Verma in order
- The third line consists of M space separated names of colleges visited by Professor Sharma in order.
- All names are stripped of spaces. College "Thapar University" is treated as Thaparuniversity or
the professors may write it as thaparuniversity as their writing style is unknown.
- For each test case, output the 'Longest Duration'
- 0 < T < 1000
- 0 < N,M < 1000
- 0 < Length of names of colleges <= 100
Input: 2 4 5 punjabiUniversity IITDelhi Amity NITTiruchirappalli bitmesra NITTiruchirappalli IITDelhi Amity punjabiuniversity 5 5 punjabiUniversity bitmesra IITDelhi Amity NITTiruchirappalli punjabiuniversity IITDelhi bitmesra NITTiruchirappalli Amity Output: 2 3
- Example case 1.it is best to start with IITDelhi and travel together to Amity and will allow professor verma
to spend maximum time together with professor sharma.
- Example case 2.There are number of longest path in this example. One such path is punjabiUniversity - bitmesra - Amity
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.