Problem Statement is here: http://www.spoj.pl/problems/YODANESS/

Summary:  at first you will be given an order of strings, and then you will be given another order of strings. You need to find that how many pairs of words in the order are not in relative order.

Algorithm: Segment Tree [http://wcipeg.com/wiki/Segment_tree ], BIT

This Problem is solvable with both Segment tree and BIT. But I don’t know BIT very well, that’s why I am describing the segment tree approach.

Let’s check the first sample case first line:

in the force strong you are

We can give the words some number id, so that we can identify them easily.

If id of the word in is 1, then id of the word the is 2 and so on, then we can rewrite the sentence with numbers like this way

1 2 3 4 5 6

Now let’s see the second line:

you are strong in the force

Now we can change this to integers with the value of the first order. Then we can rewrite it as-

5 6 4 1 2 3

As you word have id of 5, are word have id of 6 and so on.

Now what’s the benefit of this? Let’s check.

We will use Segment Tree now-

We will sort the value in Descending order with keeping the index information. Here’s the table will become-


6 5 4 3 2 1
Index 2 1 3 6 5 4

Now we will run loop on this sequence then do some query and update.

Initially we will assume that our array is empty.

First iteration:

I get value of 6 and index of 2. So we will do sum query on this [1, 2] interval, then add it with ultimate result. Now update the index 2 with 1. Array becomes


1 2 3 4 5 6
Value 1

Second Iteration:

I have value of 5, and index of 1, So again do a sum query on the interval [1,1] and add the result with ultimate result. And obviously update the index with 1. So the array becomes

Index 1 2 3 4 5 6
Value 1 1

Third Iteration:

Now Value is 4, index is 3, now do the query on [1,3], you will get 2, because before 4, we have 5,6 which are not in relative order with 4. So add 2 with the ultimate result. Update the index 3 with 1.

Index 1 2 3 4 5 6
Value 1 1 1

So on….

I am not showing the segment tree code… If you really need it… I will add it up…


2 thoughts on “SPOJ YODANESS LEVEL

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s