cheesepotato73's blog

dsa knowledge vs rating

By cheesepotato73, history, 8 months ago, In English

i am at the moment still a newbie actively looking to increase my rating as much as i can ,can someone tell me what kind of data structures will i require at various rating levels ?or will my knowledge in data structures even matter ?please let me know of this .Thanks in advance!

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it -22 Vote: I do not like it

what are data structures ? Can you please give example?

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

learn segment tree

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    learning segment tree only made me a specialist , that whole learn binary search thing is a lie. go learn everything you encounter in your life and maybe you will touch master/gm is the real answer.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You had to use Seg-tree to reach specialist?!, I have never been able to use a seg-tree in a contest as of now. (I know the idea and have implemented in practice, but never in a contest, sometimes I don't reach that difficulty, other times I don't find a clear approach).

      I would suggest DFS/BFS, some permutation combination, some number theory, basic DP ideas, (and ofc) binary search are enough to reach Expert (1600). (Side note: Go through STL functions/data structures they do a lot for you).

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it -28 Vote: I do not like it

        you go learn what is sarcasm

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it -7 Vote: I do not like it

          The probability of it being a sarcasm is low. Because of the following reasons:-

          1) Given that the OP would be satisfied (for the time being) if he was told something that would help him reach "Specialist".

          2) He says the binary search thing is a scam and you need to study everything in order to reach Master/GM, which is more towards the truth if you want to reach Master/GM.

          Analysis
          1) --> seems like it's saying learning seg tree would help your thinking enough to reach Cyan. Which is not true. But Cyan is not a great achievement. (You start with a real rating of 1400). Hence the intent of the comment/reply to the main comment is unknown.
          Verdict — Neither rejected nor accepted (as a sarcasm)

          2) --> is more towards truth.
          Which does make me inclined to conclude that the user debugging_since_epoch is NOT saying it as a sarcasm as it lacks the presence of irony (Though the original comment by wavelets is more likely to be a sarcasm)
          Verdict — Rejected (as a sarcasm)

          If they do, it's poor humour and confusing for the OP and they should probably not do that.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            my comment was not sarcasm bro segment tree is the only ds you need though you may need to learn algorithms

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              actually maybe dsu too and if you wanna go more advanced binlift/lca/hld

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I agree, but I think telling a Newbie to learn Seg tree right off the bat seems sarcastic.
                If you were implying that this is "all you need" to reach GM or something (after adding DSU/LCA/Binary Lifting/HLD) then I understand it's not a sarcasm as I heard similar advices before and do believe that's the prerequisite.

                → Reply
          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            no comments

            → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In this contest

        problem E it is just a segment tree problem

        so I think if someone know segment tree and solve ABC fast then he will become specialist.

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          ← Rev. 2   Vote: I like it +7 Vote: I do not like it

          There is much easier solution to this problem than segment tree. You don't need to know anything besides basic topics(dp, binary search, dfs etc.) to reach specialist

          → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I would suggest to still learn stuff like segtree. For a lot of even easy problems, you can use more advanced algorithms/data structures to solve them even when they were not intended solution. Often solutions require more advanced algorithms are easier to think of compared to intended solution, which might require some unique insights.

        → Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You do not have to start with advanced data structures such as the segment tree. Start gradually learning the STLs such as map, set, and priority queue. Then move on to learning graph algorithms such as dfs and shorttest paths, and after that comes the role of some solving tactics such as dp and the segment tree, gradually you will find that it has become easier and smoother

→ Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Not much DSA needed. Learn basic sorting/searching, graph, DP and that's enough for expert.

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

at your rating you should know:

  • how to read input/write output in such a way, that it does not TLE (can be done by using a good template)
  • how to sort in O(n log n). Using templates/libraries is fine. Sorting an array/vector in a certain range (for example via std::stable_sort in c++ will become important soon. Being able to write custom comparators will become needed as well).
  • binary search is important right now. Even if it is not being used often, it is the basis of many solutions and approaches.
  • knowing the time complexities of all common data structures. adding elements, deleting elements, changing elements, finding elements. (Hash)set, (Hash)map, array, dynamic array (Vectors/Lists), multidimensional array, queue, stack
  • graphs become important at like 1200+ rating, its up to you if you wanna look into them. Also, you really only need DFS and BFS
  • segment trees are good to know for 1200+ rating as well. But only the basics. No need to learn circular segment trees unless you are aiming for yellow (probably, I may be wrong)
  • dynamic programming is important now, but there is no need to go indepth yet
  • prefix sum and suffix sum arrays should be something to read about, these are very very commonly used techniques
  • sieve of eratosthenes will become important for 1400+ rating. Giving this a read before is advicable (the same approach can be used to precalculate the divisors for all numbers until N. Which is a technique that helps with 1750+ problems) https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
→ Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

To, become pupil: U,dont need any advanced data structure u should have good knowledge of stl(maps,sets etc). Learn basic algorithm of binary search,number theory,bitwise operators. What u need is practice to reach pupil.(Solve 2 question fast / Solve 3 question) in div 2 can easily promote u to pupil. To, become specialist: U,need basics of dp,binary search,trees(basics) and dfs and bfs(basics). Well having the knowledge of these data structures and algorithms can help u to find a solution of problems of rating 1500- 1600 , u will be comfortable with them most of the time. .But, again u dont need to go in depth with these topics , practice maters more . Solving 3 questions in Div 2 constantly will grant u a promotion to specialist with ease. One, more tip i will recomend to reach specialst is to almost solve all problems of Div : 4 in a contest(highest difficulty will be 1600-1700) because u are officially the participant with highest rating (taking part in the contest).So, try to get a good rank. Again, i have experienced that only brutal practice can make u faster and better no other choice!!.

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

For now learn only prefix sums, 2D prefix sums(extended), binary search, very basic hashing, dp, bfs/dfs, number theroy and combinatorics. And solve more and difficult problems of them step by step.

After them you can go to learn some sorting, shortest distance, dsu and stuffs like that.

→ Reply