B - Counting Arrays Editorial by en_translator


All we need is just to count the number of arrays, but the key to this problem is how to implement the process of removing duplicates.

It is a bad idea to, every time an array is input, scan all the arrays you received before and check if the same sequence exists, which requires for each input of an array an \(\mathrm{O}(n)\) time complexity, where \(n\) is the number of sequences, resulting in a TLE due to the total of \(\mathrm{O}(N^2)\) time complexity.

In order to avoid this, it is convenient to use a data structure that manages a set. For example, in C++ you may use std::set in order to add an element without a duplicate in an O(log n) \(\mathrm{O}(\log n)\) times of comparison between arrays, where \(n\) is the number of elements, so that the overall time complexity is reduced to O(N log N) \(\mathrm{O}( (N+ \sum_i L_i) \log N)\) and you get AC.

A sample code in C++ follows.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
  int N;
  cin >> N;
  set<vector<int>> st;
  for(int i = 0; i < N; i++) {
    int L;
    cin >> L;
    vector<int> v(L);
    for (auto& x : v) cin >> x;
    st.insert(v);
  }
  cout << st.size() << "\n";
}

posted:
last update: