 # Help me solve this hackerrank problem.

This hackerrank problem was asked in last week of code, I am having a hard time understanding it’s editorial, please help me solve it.

1 Like

Hi there.

This link helped me a lot:

You just need to modify the code so that it finds substrings with only 2 characters with same count instead of 3.

Then you get O(n*logn) complexity per query and yes, this will exceed the time limit for some cases.

Optimizations which i did to get Accepted:

1. Replace map with array ( I used array of size 2*8000 to avoid negative indexes). Now query time is O(n) which is still slow.

2. Compress the values of the array. They are in range 1 to 10^9. You can bring them down to 1-8000 for example. We need this for the next step.

3. For a query (x,y), we are only interested in the positions of the array where x or y occurs, and not other values. For this i created a list (vector) for each element in the array which kept the positions of each occurence of that element.
For example occurence = {0,5,20} means that value 3 occurs at positions 0, 5 and 20. Now, we can ‘jump’ only to positions which contain x or y. This is a huge optimization together with caching (next step).

4. Caching. Once you compute answer for query(x,y) , store it in a matrix or map.

I can’t tell you the actual complexity per query after all the optimizations, but it is fast enough. I got 1.57 on the slowest test case.

3 Likes

Thank you so much for the explanation and I have doubt.If you don’t mind can you explain your calculation part in your code in the “while loop”.Please

Thank You!

1 Like

I was not able to think of compression of values, and that got me . Can you share your code as well? It can clear the implementation doubts !! 1 Like
2 Likes

Wait, hackerrank allows you to see others solution?? Since when? O_O

After the contest Damn! I never knew that . It allows you to view others solution in practice section too?

2 Likes

Yes @vijju123

3 Likes

You found me :). mp is actually means mp and mp means mp[-8000] . In case anyone wonders.

Regarding the calculation in the while loop.

while(ii < N || jj < M) - this means, as long as there are values to jump to, either in the x array or y array do:

The next 2 lines find the position of the next x and y respectively so that i can jump to the smaller position. This is why, if there is no x or y remaining, i set the value to MAX which is just 8002 because i compressed the values.

`````` int xPos = (ii < N) ? occur[x][ii] : 8002;
int yPos = (jj < M) ? occur[y][jj] : 8002;
``````

Lets now look at the case where xPos < yPos. This means we need to jump to an x value. It is basically the same code for y value in the ‘else’.

``````//This here counts other numbers between current x and last position of x or y.
int howMany = xPos - lastPos - 1;
int tmp = 8000 + zc - oc; //Tmp is the difference between xs and ys
``````

Because we jump only to xs’ or ys’, we skip the other values, but in the algorithm in the link provided we still add to the result mp[tmp] for each value that is not x or y. This is why i add mp[tmp]*howMany to the result.

``````As for (howMany*(howMany-1)/2), notice that in the code from the link we do mp[tmp]++ no matter what. So for each number between lastPos and current x (howMany -1 numbers) we add 1 to the result so it becomes: 1,2,3...howMany-1. This sum is equal to  (howMany*(howMany-1)/2).
``````

After the while loop i add to the result once more to account for possible remaining values after the last x and last y.

I edited a para of your answer for clarity. The `* *` were causing unnecessary italics. Have a check at it 2 Likes
//