Comments

• 
  

  1

  

  jeroenopdebeek  commented on April 2, 2023, 1:03 p.m. ← edited →

  I had a different idea, didn't implement because I wanted to do other things that day: I would say suffix arrays are easier than suffix automatons. Subtask 2 can be solved with a max segment tree and a suffix array. There's a cool trick to make some static datastructures into datastructures allowing for insertion. So if you have a solution for subtask 2, you actually have a solution to the full problem, although with a log factor slowdown. You can do it by storing ~\log(n)~ copies of a datastructure. Anytime you want to insert a new word into the data structure, you just add a new datastructure with that one word in it. But to keep the number of copies small, if two data structures have the same number of words in them, you merge them. Anytime you rebuild a data structure with more words, the number of words gets doubled. And at any time you have at most one data structure for each power of two. So this only gives ~\mathcal{O}(\log(n))~ slowdown.

• 
  

  1

  

  Geothermal  commented on April 2, 2023, 4:28 a.m.

  I know very little about suffix automata and I'm curious whether my solution is provably efficient or passed due to weak test cases. My strategy was to build a suffix automaton, inserting the difference array corresponding to each song followed by a filler character. Then, within the suffix automaton I store the maximum rating of a song ending at that node. To update this value, after each song addition, I iterate through the nodes of the suffix automaton corresponding to prefixes of the difference sequence. For each such node, I update its value and replace it with its suffix link, repeating until I reach the root of the automaton and breaking once one of my links gets me to a node I've visited already. The pertinent part of my code is below:

  set<int> vis;
  vis.ins(0);
  ckmax(st[0].val, R);
  int v = 0;
  F0R(i, K-1) {
      if (!st[v].nxt.count(A[i])) break;
      v = st[v].nxt[A[i]];
      int cur = v;
      while (!vis.count(cur)) {
          ckmax(st[cur].val, R);
          vis.ins(cur);
          cur = st[cur].link;
      }
  }

  Does anyone know whether there's a proof that this solution will be efficient? Empirically it appears to be faster than many of the other AC solutions, and my code seems substantially simpler than many other approaches (I don't use a BBST and my solution is quite short once you take out the various incorrect commented attempts), but given that my knowledge of suffix automata is limited to what I googled to solve this specific problem and that I came to this solution as a result of trying various things I guessed might work, I'm not particularly confident that this is actually provably efficient.