Doing cp hahahah

Problem - 2148F - Codeforces (1800)

It’s natural that we can get the answer by greedy, at least for the first digit, we can do minimum of all. Another observation that I found is that:

46
467
468

Consider there are 3 of these with the same prefix, you will pick the shortest one because:

• the longest one can always replace the shortest one
• intuition tells that the next boxes can be replaced with another digits and gives an opportunity for it to be smaller.

Pick numbers in increasing order in terms of length is also natural because those in between will be ignored. Thus giving another observation that the height is max $\sqrt{n}$.

So the algo is simply sort by the first digit, among all available ones

XXXXX$
YYY$$$
ZZZZ$$
AAAAAA

this case, its the same as like pad all into the longest length, and then sort by it, and then pick the smallest ones. Sorting this can use a trie, I think it removes the log factor. After picking that one, essentially now all strings are pruned, now length are changed into of that length. For all of the strings remove those which have length equal or same to the picked one.

And then make a new trie out of the remaining strings.

this iteration will be done sqrt(times), while string building might take 2e5 * sqrt(2e5)

Is this good enough, at least its subquadratic lol.

Needs more observation to remove the sqrt i suppose. NVM, passes.

int solve() {
  int n; cin >> n;
  vector <vector<int>> grid(n);
  trav(cur, grid) {
    int k; cin >> k;
    cur.resize(k);
    trav(el, cur) cin >> el;
  }
  vector <LL> ans;
  while (!grid.empty()) {
    sort(all(grid));
    // Take the first one
    ans.insert(ans.end(), all(grid[0]));
    vector <vector <int>> newGrid;
    int latestLength = grid[0].size();
    for(int i = 1;i < grid.size();i++) {
      if(grid[i].size() > latestLength) {
        newGrid.emplace_back();
        newGrid.back().reserve(grid[i].size() - latestLength);
      }
      for(int j = latestLength;j < grid[i].size();++j) {
        newGrid.back().push_back(grid[i][j]);
      }
    }
    grid.swap(newGrid);
  }
  trav(cur, ans) cout << cur << " ";
  cout << endl;
  return 0;
}

Problem - G - Codeforces （Rating: 1900)