I’ve never used a linked list in a CP problem. Was wondering if it is ever useful?
I’ve never used a linked list in a CP problem. Was wondering if it is ever useful?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Yep used it a few times but u can instead link elements using prev and next arrays!
Yeah that sounds like a simpler way to implement it than struct
I remember the idea of Doubly Linked List being used in this problem 1922D - Berserk Monsters (by keeping track of left and right indices similar to prev and next pointers in DLL). So yeah the idea can definitely be used in some problems
I see, but i did it using ordered set in cpp (302954264). So ig linked lists aren't necessary there. Are there any problems where linked lists are inevitable?
Can you please share your solution ?? BambooTree
313533768 Here the Left and Right arrays represent the indices of the leftmost and rightmost alive monsters.
Maybe. You might check my blog: https://mirror.codeforces.com/blog/entry/140442
you can write solutions fast in some problems if you learn link list (next and prev arrays)
https://mirror.codeforces.com/gym/105789/problem/I according to the official standings if you solve this problem, which is mostly about maintaining a linked list, you should be basically at the level of Latin America ICPC Champion!
Being completely fair the hardest part of this problem is reading it properly and it's not the problem's fault, it gives you multiple chances to understand it.
https://judge.yosupo.jp/problem/st_numbering
https://mirror.codeforces.com/blog/entry/71568#comment-559304
I remember using it only once, in this problem: https://mirror.codeforces.com/contest/1131/problem/F
Yes. Sometimes setters give a problem on a linked list, but as participants don't know how to use it they code treap instead.
99% solutions for problem L in this contest are treaps (linked list is replacable by deque there though).
Linked list is close to the best graph representation method.
Linked list is the objectively optimal (figuratively) way (both memory and constant factor efficient) to represent $$$m$$$ integers distributed across $$$n$$$ sets in $$$O(n+m)$$$ memory. It needs the assumption that each integer can appear in at most one of the sets at any time.
A doubly linked list is present as a standard SQRT-structure that supports arbitary insertions and removals.
In many fastest CSES solutions ammojamo loves linked lists, for example https://cses.fi/problemset/stats/2416/
Just checked out linked lists for sqrt functionality. Very cool. Thanks!
The only linked list problem I saw in a contest was Atcoder abc344_e Insert or Erase, but it was solvable using a map
Task from Educational Codeforces Round 161 — https://mirror.codeforces.com/contest/1922/problem/D