What's the most beautiful technique you know about?
source link: https://codeforces.com/blog/entry/117205
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
What's the most interesting beautiful you know about?
|
Using map<int, vector < int >> as a data structure for making several implementation easy |
-
I also sometimes do it but I don't see it generally in the codes of people who are very good. So can anyone tell is this way good or is there any better way that I might be missing.
|
3 days ago, # | |
|
3 days ago, # | Pie for a pie trick. |
|
3 days ago, # | I like monotonic stack. The idea is pretty simple but you can do a lot of stuff with it |
-
recently used this to implement a solution which was not the intended solution (or simplest)
when decreasing s[i] to lower character it will affect only those indices for which next_greater_character index is 'i' (if next_great[j] < i or next_great[j] > i then its contribution is negative irrespective of value at index 'i')
|
3 days ago, # | using map<int,int> :) |
|
3 days ago, # | Grundy Numbers with Infinity |
|
3 days ago, # | Partial sum |
|
3 days ago, # | My fav is LCA with binary lifting, least fav is probably sqrt decomposition |
|
3 days ago, # | Binary search is so intutive and beautiful and how you sometimes use it in real life without realising (like when trying to open some random page number open the lesser one the open the higher and continue till you get the one which want) |
|
3 days ago, # | To be honest, the humble DFS: it's simple, but very flexible and you can do quite a lot of things with it: finding cycles, topological sorting, strong connectivity, finding bridges, tree DP (and a lot of tree calculations in general), Euler tours, some ad-hoc applications etc. etc. |
|
3 days ago, # | Union find all the way |
|
39 hours ago, # | Matrix Exponentiation |
|
35 hours ago, # | the simple binary search |
|
35 hours ago, # | Optimizing bitset memory usage from O(n^2) to O(n) |
|
34 hours ago, # | Linearity of expectation of a sum of dependent variables; in cp it's mostly used to turn the problem "find the expected number of objects" into the problem "sum the probability that an object appears for each object" |
|
34 hours ago, # | Disjoint Set Data structure. |
|
34 hours ago, # | My favourite technique, the Goemans Williamson MAX-CUT algorithm doesn't come from competitive programming, but from the field of approximation algorithms. It's one of the most elegant algorithms I've come across in computer science, so I'd recommend others to check it out too. |
|
34 hours ago, # | The most interesting and beautiful thing I know is Talia Al Ghul. |
|
whenever I come across a question like "print a permutation which satisfies [some] conditions", I usually generate all of the possible permutations using std::next_permutation(c++) and print the permutations which satisfy the given conditions. I analyse all of the correct permutations and search for patterns. |
|
18 hours ago, # | DSU, seg tree, Fenwick, Dijkstra, DP and binary search maybe. |
|
18 hours ago, # | Binary Search. Simple but Gorgeous |
|
18 hours ago, # | Segment Tree and Hashing |
|
18 hours ago, # | Dynamic Programming. |
|
17 hours ago, # | Mo's algorithm. |
|
17 hours ago, # | I never thought Lexicographically Minimal String Rotation could be solved better than — using hashing, but when I tried to do some research and read papers, I then know much more: Spoiler Other than that, I also discover a technique to find a dominant element on in using a segment tree (yes, it also allow for updates) |
|
16 hours ago, # | (Don't know much but)calculating stuff such as square roots and cube roots using binary search. |
|
15 hours ago, # | Finding all primes smaller than n using Sieve of Eratosthenes. The idea is so simple but it is very useful for some problems. Time complexity of Sieve prime algorithm is O(n*log(log(n))). |
|
Beautiful but not that useful: Turtle and hare It has the O(n) complexity, but uses constant memory |
|
14 hours ago, # | Two pointers, easy to control & a lot of features |
|
13 hours ago, # | It's definitely parallel binary search, it's really simple yet appears in the hardest problems |
|
11 hours ago, # | I found dp beautiful |
|
10 hours ago, # | Yarin Sieve when the time/memory limit is strict. It is at least 3 times faster than the standard Sieve. Another one is the Fast Inverse Square root algorithm — the code doesn't make sense at first glance. It's still one of the most widely used algorithms in Game development. |
|
9 hours ago, # | Priority_Queue is beautiful |
|
9 hours ago, # | Segment Trees |
|
9 hours ago, # | I use almost all the times BFS if possible over DFS other than this unordered map and segment tree are the other two which I like the most. |
|
7 hours ago, # | I like treap. Treap is a very powerful structure that can do many crazy things. Also like +-300 dp optimization |
|
5 hours ago, # | I sincerely believe that the dfs/bfs. They are super simple and intuitive algorithms and it is incredible the number of graph algorithms and techniques that are based on a dfs/bfs and some other observations, but which in essence are still dfs/bfs. It is also because they are the ways of traversing a graph, but you understand me XD |
|
38 minutes ago, # | Mo‘s! relatively easy to implement, can support nearly every type of query, can adapt onto trees, supports updates, sqrt(n) time which is ok..., offline... |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK