### skpro19's blog

By skpro19, history, 5 years ago,

Let's discuss the hackerearth december circuits here.

The link to the competition is this.

• +2

| Write comment?
 » 5 years ago, # |   0 Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).
 » 5 years ago, # |   0 How to solve the 4th question?
•  » » 5 years ago, # ^ |   +1 you mean splitting of array. if yes.i solved it by maintaining inversions of all prefix and of all suffix. Then for each element i m finding how many greater elements are there to the right side. so answer for each k is prefix[i] + suffix[i+1] + no.of element greater to right.
•  » » » 5 years ago, # ^ |   0 Thanks. Can you share your code?
•  » » » » 5 years ago, # ^ |   +4 The solution is much more simple based on a simple observation. Consider the given example — 3 5 2 7 6 It has 3 inversions. Now when 3 gets shifted at back, how many inversions get added? The number of integers greater than 3 i.e 5,7 and 6 add 1 inversion each. And how many inversions get lost? The number of integers smaller than 3 i.e 2 leads to loss of 1 inversion. So for each integer shifted, number of inversion increases by number of integers greater than that integer, and decreases by number of integers smaller than that. Here is the code
•  » » 5 years ago, # ^ |   +1 You can create a new array by appending array A to it self A=A+A and now just you need to find inversions in every subarray of size n this can be done using sliding window of Len N and binary indexed tree .
•  » » » 5 years ago, # ^ |   0 Code please.
 » 5 years ago, # |   0 Wasn't the contest a bit on the tougher side?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 It was, and its due to my problems. I'm sincerely apologetic for this, and I shall be more careful about the difficulties next time.On the other hand, I hope all of you'll read the editorials and the pre-required knowledge links attached to them, and it shall definitely be profit for you'll.Thank You and Sorry again
•  » » » 5 years ago, # ^ |   0 Will do. Thanks man. Some suggestions: 1.There were too little example test cases in the question. 2. The problems difficulty was out of sync
•  » » » 5 years ago, # ^ |   0 Two arrays problem was nice.