nns2009's blog

Any cool algorithms/data-structures to re-invent?
By nns2009, history, 4 hours ago, In English

(since I don’t have any following, this post will probably only get a few views, so in case you find it months/years later — yes, still relevant)

I am looking for some cool algorithms or data-structures, which are ingenious, clever and interesting, but also not prohibitively complicated, so it’s possible to re-discover them while solving some specific task.

My current knowledge for context

Re-invented before:

(stuff I came up with before I ever read or been taught about it)

  • Polynomial string hashes
  • Convex-Hull
  • Persistent data structures like trees (by familiarity with functional programming, immutability and such)
  • Graph min-span tree

Know-well:

  • Various graph algorithms
  • Various trees
  • RMQ
  • Prefix function, Aho-Corasick
  • Dynamic programming
  • DSU
  • Parsing by recursion

Remember in general details:

  • Suffix array

Coded previously, but never put effort to understand deeply and forgot:

  • Graph min/max flow
  • Suffix automaton
  • Some limited RMQ-like structure, which can only do a subset of operations, but has a lower constant and lower memory usage (don’t remember the name)

This is not an exhaustive set of what I know, but hopefully it gives you a general idea to suggest stuff, which I likely don’t know and will find interesting.

Ideally looking for:

  • CodeForces problem links
  • a name of the algorithm/data-structure needed to solve it (which I’ll try not to use/Google before solving myself)
  • Estimated difficulty to re-invent the algorithm and solve the corresponding problem(s)
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
3 hours ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

https://codeforces.me/problemset/problem/1949/B

Try to solve this in a time complexity that is not $$$O(n^2)$$$ or beyond. With this, you would reinvent:

Spoiler

Pardon me if I failed to meet your constraints due to my inexperience.

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

    Thanks for the suggestion!

    Wouldn't a simple min(sort(aa) — sort(bb)) work? Ha-ha-ha. That would be too easy, and they'd certainly make n>=200 000 in such a case.

    I'll think

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

      Hehe, that's not it :). The solution is something way cooler !

      → Reply
»
3 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Not codeforces, but I like this problem a lot. It is in romanian but translation should be relatively simple. Try to do it in $$$O(N)$$$.

Problem

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

    but translation should be relatively simple

    Then translate it, what's the problem?

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

      The problem gives you a tree. A node is either a know-all that can answer queries or a know-nothing and has to ask one of its ancestors for the answer to the query. Each know-nothing might have a different ancestor they need to ask (for each node there is a $$$k$$$ that specifies that you should ask the $$$k$$$-th ancestor).

      The task is to find for each node how many jumps a query makes (starting from that node) until it is answered.

      The actual interesting part
      → Reply
      • »
        »
        »
        »
        63 minutes ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Micro macro tree.

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

          ?

          → Reply
          • »
            »
            »
            »
            »
            »
            51 minute(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            That's the solution to the 'The actual interesting part'.

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

              I don't know what a micro macro tree is (although, I would not mind an explanation/resource).

              The intended solution is
              → Reply
»
30 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

  • Aliens' trick (the one that appeared in IOI16_aliens specifically). Do APIO10_commando first. Only person who managed to came up with that blind in-contest was LiTi ([user:jvcb] is only in-contest AC, but that was because he've known about the trick before)

  • Kruskal Reconstruction Tree/ Reachability Tree (online solution to that "How many nodes can be reached form node X using edges with weight <= W" common parallel binsearch problem). Very intuitive when you actually see it

→ Reply
»
16 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

I suggest you to re-invent factorization algorithm which works in $$$O(poly(\log(n)))$$$ time where $$$n$$$ is the number to factorize.

→ Reply