Help me solve this hackerrank problem.

general
, ,
1

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
2

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[3] = {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
3

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
4

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

1 Like
5

@vijju123 this is his code.
link:
https://www.hackerrank.com/rest/contests/w34/challenges/same-occurrence/hackers/Vasja_Pavlov/download_solution

2 Likes
6

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

7

After the contest :slight_smile:

8

Damn! I never knew that :confused: . It allows you to view others solution in practice section too?

2 Likes
9

Yes @vijju123

3 Likes
10

You found me :). mp[8000] is actually means mp[0] and mp[0] 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.

11

I edited a para of your answer for clarity. The * * were causing unnecessary italics. Have a check at it :slight_smile:

2 Likes