YODANESS - Yodaness Level

Yoda is the wisest, and perhaps the most powerful Jedi of his time. Yoda is a mysterious figure and he has many oddities. One of them is that Yoda often changes the order of words in the sentence. For example, one of such phrases is "Or I will help you not." Let's call the yodaness level of any statement the number of pairs of words that changed their order, as to the order in which they were supposed to go in a normal statement. Write a program that determines the yodaness level of different statement of Yoda.



The first line of input contains the number t - the number of tests. Next comes the description of t tests. Each test consists of three rows. The first line of the test contains an integer n - number of words in the statement. The next line contains n words separated by spaces - the statement as Yoda says it. The next line is n words separated by spaces - the same statement as it should be said normally. All the words in the statement are different and consist of small latin letters.


1 <= t <= 10
1 <= n <= 30000
the length of each word does not exceed 20 characters


For each test print the yodaness level of the statement.


in the force strong you are
you are strong in the force
or i will help you not
or i will not help you


hide comments
siddharth: 2016-04-29 13:14:45

I have solved INVCNT and i am using the same algo for this problem still it is giving me TLE
I am using STL+mergesort.
Please help

solved using maps+mergesort

Last edit: 2016-04-29 14:22:52
Safayet Islam Anonno: 2016-01-21 14:07:23

Thanks Rajat for your clarification. It helped.

Advitiya: 2015-10-20 22:48:29

STL+mergesort :'D AC

Mayank Garg: 2015-08-07 12:34:16

Just basic STL !! :D

BALMUKUND SINHA: 2015-07-24 22:15:43

100th question

Last edit: 2015-07-24 22:15:54
PRIBAN91: 2015-07-24 14:53:28

The problem statement should be bit more descriptive. Otherwise a good problem. Thanks Rajat.

r0bo_dart: 2015-06-25 12:34:20

maps + INVCNT :D

GAURAV CHANDEL: 2015-04-26 06:53:57

Easy if you have solved INVCNT .. Good problem

Rajat (1307086): 2015-04-02 10:59:48

had to modify the code of INVCNT.
Those that did not understand the cases:
"in the force strong you are"
following are the yodaness pairs:
in strong
in you
in are
the strong
the you
the are
force strong
force you
force are
strong you
strong are
so total=11

Mitch Schwartz: 2014-10-07 23:41:42

@Akshay: It seems clear enough to me. Suppose word A comes before word B in the original sentence. If Yoda's version puts A after B, then that counts as one reversal. You are concerned with the total number of reversals.

Added by:Spooky
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Advancement Spring 2010, http://sevolymp.uuuq.com/