Suiiinaldo's blog

By Suiiinaldo, history, 14 months ago, In English

1866C - Completely Searching for Inversions

What is leading my solution to go memory limit exceeded? Please Help. And Can Anybody give hint about the correct approach. I am going with the complete brute force approach of calculating the Z Array and then finding the number of inversion in linear time. I was calculating the Z Array according to the given question.

My Submissions are as follows: 221686347 221686896

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The array can become extremely big (for example, if the graph is dense).

Hint: try to compute the size of $$$Z$$$ first. Then, use a similar approach to count the inversions.