Let's discuss the hackerearth december circuits here.

The link to the competition is this.

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 185 |

2 | adamant | 177 |

2 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 153 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

Let's discuss the hackerearth december circuits here.

The link to the competition is this.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/31/2023 18:57:44 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).How to solve the 4th question?

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.

Thanks. Can you share your code?

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

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 .

Code please.

Wasn't the contest a bit on the tougher side?

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

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

Two arrays problem was nice.