I know some common ones(and ones that I have) are Segment Tree and DSU, but what about things like Tries or Treaps? Thanks! :)
UPD 1: Does anyone have a good Trie template? Just out of curiosity since the online ones aren't that good.
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | jiangly | 3578 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | tourist | 3565 |
8 | maroonrk | 3531 |
9 | Radewoosh | 3521 |
10 | Um_nik | 3482 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
I know some common ones(and ones that I have) are Segment Tree and DSU, but what about things like Tries or Treaps? Thanks! :)
UPD 1: Does anyone have a good Trie template? Just out of curiosity since the online ones aren't that good.
Name |
---|
If you below purple, learn binary search first.
above purple you might add segment tree and BIT
Solid advice here haha. I doubt adding templates as green will help with anything.
https://imgur.com/a/iFyYDbR
Justin orz lol
Segment trees are definitely helpful even under purple. There are a lot of problems that are made easier with segment trees and some that require them before becoming purple.
It depends on your rating. While you are green, you'll never use segment tree or dsu on codeforces. Binary search and simple olympiad math are more relevant at this point.
This is funny, cause like a lot of experienced people like you guys talk a lot about binary search and math, but often Div 2. C and D is already asking for more than just that lol. But I will start learning Olympiad math though :) Thanks!
div 2 c/d almost never asks more than that :/
Then I'm skill-issuing
For solving 2D in contests, shouldn't one be practicing problems in the range 1600-2200 from the problemset ?
I have found many dp, segTree/BIT problems in the problemset in range [1600,1800]. There are MST Dijkstra problems too starting from range 1900.
How, would you practice these problems if you don't know them ?
Maybe I don't have enough experience, but I haven't seen a single div2D that absolutely REQUIRES segtree/bit, or even dijkstra/MST. I will admit that DP is probably necessary though
Personally, in my climb to CM the most advanced algorithm I've used was DSU.
Is this your alt account or main account ? You climbed to CM by solving way less problems than me.
It's his main lol
Main. I had experience in my country's computing olympiad before taking part in Codeforces contests, that's why I climbed to expert so quickly and suddenly stalled.
USACO Plat orz
Wait you are Usaco plat but only purple? P.S I have never been able to solve any of them. Or even a lot of gold.
Getting to USACO Plat only requires me to be able to solve 2 gold problems and get some partials in the same contest. As it stands, the only plat problems I can solve are ones known to be very easy.
As a cyan plat, all you really need is to get lucky.
BENAR
As a green gold, all you need is to not have suhas nagar set the silver problems(no offense, im just quoting some of my friends' feedback of his problems).
pathetique orz
nou
pathetique orz
I'm one of those guys who practice the advanced stuff but then get beat up by basic data structure and logic problems. I also don't care about rating so much which is why I solve like 1 to 2 problems and then go to school, which is why I placed from like 7000-10000th place in the last 5 contests.
In my experience, div 2 A-C seem like brainteasers. Div 2 D is where you might get some more advanced stuff but it is still rare to find a segment tree there.
Definitely, that's Div 2 E in most cases
div2c 100% does not ask for more than those things.... MAYBE div2d but probably not
Data structure moments :sighs:
ok but like I don't think there are many div2ds with segtree lol
I meant priority queue, stacks, queues lol mb, I forgot segtree count as data structures, but advanced...
All three of those are in the stl, so no need for templates
Consistently solving div2 D is blue or purple level though
Any tips for uncreative coders like me trying to identify and solve DP problems? Practice is usually what people suggest, but I don't quite find that to be helpful.
Solve CSES DP section. The last few are really hard, so you don't need to do them to be decent at DP.
But the way you phrase it makes me think you're in the mindset of forcing techniques on problems instead of making observations and working from there.
I could be tottally wrong but if you find yourself listing out techniques as soon as you start a problem like "Is it dp? Is it shortest path? Is it greedy? Is it segtree?" then you need to work on avoiding that instead IMO.
Thanks! I feel like you identified the issue very accurately, I'll work on observing > assuming. :)
More specifically for where to stop on the CSES DP section, I'd say everything up and including Projects is good basic DP practice. Elevator Rides, Counting Tilings and Counting Numbers are more specific types of DP that probably won't help for CF.
Good dp problems: AtCoder
permutation tree https://mirror.codeforces.com/blog/entry/78898
Sounds like something you would find in a Div 1 C or D problem :)
I think he was sarcastic
yes lol
things every newbie should know
So true, this is legit why I love the CF community. Great sense of humor :) (Sorry if this was meant to be legit lol)
vector and set.
Auto comment: topic has been updated by Red0 (previous revision, new revision, compare).
If you're less than specialist i will tell you what templates will help you become specialist like me: Suffix automaton All geometric algorithms Max flow algos Heavy light decomp is a must Link cut trees Rotation trees Treaps Sqrt tree Wavelet tree Recently elegia published some algo so new problems on that might come up in upcoming div2 B/C Divide and conquer fft and polynomial approximation algorithms And dont study binary search until you become an IGM cuz its a very hard topic and problems on it are kinda rare
Just sharing the templates you can save:
Permutations and Combinations template (n choose p and stuff) with support for inverses.
Disjoin Set Union (or Union Find)
Templates for working with Primes (Sieve, Primality Check and stuff), factors (smallest prime factor), and Euler Totient Function.
Lowest Common Ancestor template for Tree
Hashing Template for Strings (like Polynomial rolling hash)
Fenwick Tree and Segment Tree for updates and queries.
These are not specific to any Color, just having them handy will be good. Usually, when I am stuck on a problem, I check the next ones. Sometimes one/two such problems seem familiar — having templates handy will save time.
Thanks! Do you have any specific templates you want to share? :)
My templates are derived from online sources. I don't remember the exact sources. Feel free to use them. Or you can build your own as I did.
Disclaimer: Some snippets are not fully tested ;)
Thank you so much!
This YouKn0wWho's collection was once recommended to me by a friend, but I never used it. I code from the scratch, most of the time.
Wow, thanks!
Every code I can put in a C++
struct
I do:My snippets: https://github.com/MuhammadSawalhy/problem-solving/blob/main/cpp.snippets
You should have other templates like input or other things that will help you solve problems quicker. Best way to get to specialist :D
Not exactly data structure, but I find having input mock useful for interactive problems.