Aspergillus's blog

Drop problems which can't be solved without specific data structures
By Aspergillus, history, 2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

APIO14_palindrome

→ Reply
»
2 months 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
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Well the most difficult part of the problem was to keep track of the relative order of the first occurances of the elements in b. Couldn't do it at all, looked st some top submissions and learnt how jiangly did it. Once that was clear, the rest was actually pretty tame.

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

    It is very similar to 2002D2 - DFS Checker (Hard Version), which is around ~2000 difficulty.

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

https://mirror.codeforces.com/contest/432/problem/D

→ Reply
»
2 months 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
  • »
    »
    2 months 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
    • »
      »
      »
      2 months 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
      • »
        »
        »
        »
        2 months 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
        • »
          »
          »
          »
          »
          2 months 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