Senku's blog

Are linked lists ever useful in CP?
By Senku, 12 months ago, In English

I’ve never used a linked list in a CP problem. Was wondering if it is ever useful?

  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
12 months ago, hide # |
 
Vote: I like it +37 Vote: I do not like it

Yep used it a few times but u can instead link elements using prev and next arrays!

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Maybe. You might check my blog: https://mirror.codeforces.com/blog/entry/140442

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

you can write solutions fast in some problems if you learn link list (next and prev arrays)

→ Reply
»
12 months ago, hide # |
 
Vote: I like it +22 Vote: I do not like it
Spoiler
→ Reply
»
12 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

https://judge.yosupo.jp/problem/st_numbering

https://mirror.codeforces.com/blog/entry/71568#comment-559304

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I remember using it only once, in this problem: https://mirror.codeforces.com/contest/1131/problem/F

→ Reply
»
12 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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).

→ Reply
»
12 months ago, hide # |
← Rev. 3  
Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The only linked list problem I saw in a contest was Atcoder abc344_e Insert or Erase, but it was solvable using a map

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Task from Educational Codeforces Round 161 — https://mirror.codeforces.com/contest/1922/problem/D

→ Reply