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
ishraaq_56789: 2021-09-22 05:44:23

To the author of the problem, wy is brute force not passing?

sicho_mohit: 2021-08-03 15:02:45

First please try this https://www.spoj.com/problems/INVCNT/, then try to do this one.

Rafail Loizou: 2021-05-09 22:34:42

@punkfaiz the numbers work correctly for the example that you give just a heads up to everyone else this is not the example input. The example input would be this one:
5 6 4 1 2 3
4 gives 2, 1 gives 3, 2 gives 3 and 3 gives 3. 2+3+3+3 = 11.

Last edit: 2021-05-09 22:35:06
punkfaiz: 2020-08-20 11:06:39

1 2 3 4 5 6
4 5 6 3 1 2
simple no. of inversion

Last edit: 2020-08-20 11:11:32
pandey101299: 2020-07-16 14:41:20

similar to inversion count solved using BIT

the_pythor: 2020-05-15 09:20:29

This question is the same as "count the number of smaller elements in the right". It took me a while to figure it out. Problem statement should have been more clear.

Last edit: 2020-05-15 10:14:06
coolio_1: 2020-03-09 17:22:33

AC in 1 go using BIT

harshil nori: 2019-12-04 11:07:22

Solved using merge sort and counting total inverted elements. Good problem.

codefresher: 2019-11-22 23:03:47

AC in one go....solved using merge sort tree...

purplecs: 2019-11-14 07:38:11

easy one

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