Aspergillus's blog

Drop problems which can't be solved without specific data structures
By Aspergillus, history, 7 weeks ago, In English

Hello all today I struggled a lot with C2, especially because I am not used to using sets, actually not used to using any data structure other than map or vector, I have used queues for BFS only. So I have decided to spend a few days with them.

Please suggest some problems, which are not higher than maybe 2000 rated on CF equivalent, which cannot be solved in desired time or memory without specific data steuctures. One example is stacks for finding the nearest element smaller in the left/right using stack (or vector with push back). Another example maybe using sets to maintain indexes of appearances with updates, which was used in C2. Some people say some sorts of balanced paranthesis substring problems can be solved only using stack but I have only ever used a map for that purpose at best.

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

APIO14_palindrome

→ Reply
»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

C2 was crazy. I don't wanna say that that sort of problem is boring, but there is a time and a place for those sort of things. Certainly the appropriate place isn't a div. 2 C, is it?

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/432/problem/D

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure what you're complaining about for C2. AFAIK the problem doesn't need any advanced techniques. My solution only uses basic understanding of arrays and a set. 284778921

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

    No part of the post is complaining about C2. Also not sure what part of the post mentioned it uses "advanced techniques", only that I am not familiar with using even sets as a data structure.

    Also, I prefer Jiangly's solution.

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

      In that case I'm not sure what the point of the post is. Does your title not suggest that setters should drop problems such as C2 or those that require advanced data structures? I think that instead of making setters conform to your skill issues, you should git gud. Creating interesting problems is already hard without imposing more restrictions.

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

        You are misunderstanding things. By "drop" I mean "comment below" and not drop from the set.

        PS: You known what, I'm sorry for being rude in the last edit, it was just a misunderstanding, I overreacted. I'll just apologise and move on.

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

          I see, in that case all is fine. If I remember correctly this is a nice problem that doesn't anything more than what you mentioned

          → Reply