Let's discuss the hackerearth december circuits here.
The link to the competition is this.
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 11:31:49 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
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.