Please read the new rule regarding the restriction on the use of AI tools. ×

Aspergillus's blog

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

»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

APIO14_palindrome

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

    Thanks!

    → Reply
»
20 hours 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
  • »
    »
    15 hours 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
  • »
    »
    14 hours ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
»
15 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 hours 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 hours 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
    • »
      »
      »
      6 hours 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
      • »
        »
        »
        »
        6 hours 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
        • »
          »
          »
          »
          »
          5 hours 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