prokulijander's blog

Segment tree for IOI?
By prokulijander, history, 4 months ago, In English

I go to IOI without knowing to code segment tree.

Edit: Someone else posted this using my laptop while I was gone. Still, it's not far away from the truth.

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

»
4 months ago, # |
  Vote: I like it +26 Vote: I do not like it

I think you should learn it

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

Auto comment: topic has been updated by prokulijander (previous revision, new revision, compare).

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

While it is true in general that you should probably learn it, I think you will be fine. Ability to solve problems (and use binary search) beats knowing any particular data structure or algorithm every day.

Good luck on the IOI!

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

    binary search for the WIN!

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

    Yes, but olimpiad problems usually require data structures just to finish the problem, and many are probably impossible without them.

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

      Worst case scenario you lose maybe 30-40 points in 2 problems. That's not nothing, but it's not the end of the world either. You will lose many more points if you are bad at solving problems.

      I would bet I would perform at a high silver / low gold level if I could only use STL data structures.

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

        Yes, definetly, but those 40 points are basically free for other competitors, and it takes much more time to learn to solve problems better then to learn regular segment tree, also behind every DS are many clever ideas that can be used in many problems. I dont doubt you would get gold on IOI with just stl, but your problem solving skills are light years away from average IOI competitors and probably because you did problem solving for longer than they were alive (not an insult)

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

        I mean you're LGM with a lot of experience, so you prob know a lot of other tricks within STL.

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

      I needed 0 data structures to get ioi silver

      It is only true at the selection stages, but ioi also doesnt like to put data structures in easy problems. And when they do put it, its nit free in any way

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

        You can get ioi silver without full solves on any problem based on my knowledge.

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

          gold is also possible without any full solves. Just look at the standing man, a lot of the gold medalists didn't fully solve any problem, but they are insanely good at partially solve a problem

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

    And guess what the ability to solve problems is?

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

      most definitely IQ

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

        finally you said something correct

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

          If sports programming is just an IQ-gated field, then why not quit if you have concluded that your IQ isn't high enough, instead of spreading IQ-centered propaganda? Realistically, you won't get anyone to quit an activity they have committed a nontrivial amount of time to, with just a few blogs and comments.

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

            mostly because solving these problems is fun

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

          more like a sarcastic statement I made as wrong as possible

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

I think you should learn it because it is important for IOI.

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

    Genuinely, why? Why is this comment downvoted? It is, in fact, important for IOI. There are only a few DSA you would really need for IOI, and the segment tree is one of those. Binary search, basic graph algorithms, dsu, binary lifting, segment tree. It's not a lot to learn, but is extremely beneficial. Even if you never use them on IOI, it's better than regretting you did not learn them. Becoming a better problem solver in a month is not realistic; learning a few basic algorithms is.

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

      Maybe they think I am only specialist so that I can't remark something about IOI.

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

      and the second a red coder agrees with him he gets 20 upvotes.
      I feel like low rateds aren't respected enough, a good teacher of friends of mine is a pupil, but that taught half of the ppl who got medals at inoi; rating doesn't matter.

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

        Both because for the sake of experiment and because I think this comment makes a lot of sense, I will say that, in fact, it's also true

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

          the realest comments are often downvoted unfortunately

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

            Considering everything above, this is also true :)

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

Btw he is not lying, yesterday, instead of using segment tree for a problem, he started coding treap (it was max/min segment tree)

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

FranciscoPinhao u haha

→ Reply