Hi! I hope you are doing well.

If you are in love(!) with vectors and you use them a lot, you probably know that defining a multidimensional vector is just a pain in the neck! For example if you are trying to define a 3 dimensional vector with (n, m, k) as dimensions you have to write it like this :

vector<vector<vector<int>>> a(n, vector<vector<int>>(m, vector<int>(k)));

Then you change your mind and realize that your data will not fit in an int. You decide to change it to long long.

vector<vector<vector<long long>>> a(n, vector<vector<int>>(m, vector<int>(k)));

[HITS COMPILE BUTTON] Oops! won't compile (G++ really get's mad at you). Go on and change inner vectors as well.

vector<vector<vector<long long>>> a(n, vector<vector<long long>>(m, vector<long long>(k)));

So if you want a 100 dimensional vector of long longs, you literally have to say it 100 times to the compiler that you want your data to be long long.
Well what's the solution?

N dimensional vector using template meta programming

So yes, there is this thing called template meta programming which I'm not going to discuss here. But you can do cool things with it! One of the cool things is just N dimensional vector (basically D dimensional!). Here's the code:

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
  static_assert(D >= 1, "Vector dimension must be greater than zero!");
  template<typename... Args>
  Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
  }
};
template<typename T>
struct Vec<1, T> : public vector<T> {
  Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {
  }
};

This is essentially publicly inheriting from vector<vector<vector< ... vector<T> ... >>> in which vector appears D times!
It has a constructor which takes dimensions in order and if you want to initialize your multidimensional vector with some value you can pass that value to the constructor as the last argument otherwise it will be initialized with zero (or if it's a class it will be initialized using default constructor). If you provide less than D numbers to the constructor, following dimensions will have length equal to zero.
A few examples :

Vec<2, int> a(10, 50); // int a[10][50] initialized with zero
Vec<3, double> b(n, m, k, 3.14); // double b[n][m][k] initialized with 3.14
Vec<3, long long> c(5, 5); // the third dimension has no value yet
c[0][0].push_back(100); // now c[0][0][0] has a value (100) but others don't
Vec<4, int> d(10, 10);
d[2][3].push_back(Vec<1, int>(100, 12345)); // now d[2][3][0] is a vector with 100 values of 12345
Vec<1, string> e; // just blank vector of strings

Based on C++11 (or above) standard this code will compile.
Template arguments must be compile time constants, for example Vec<n, int> in which n is the user input, won't compile, which makes a lot of sense.

Hi!

I'm a member of the ACM-ICPC community of my university. As this semester started, new students came to our university. The community of ACM-ICPC at my university is quite small. Consequently, we (me and my teammates) decided to advertise these competitions to newcomers and try to attract them. We're mainly focused on ACM-ICPC. I think that most people that are doing competitive programming, are doing it because they find it fun and also they enjoy solving problems (sounds true for me). Now I was looking for some advice on how to actually introduce competitive programming to a person that may have never tried it before. Any opinions on how to attract people to CP are welcomed. Here are mine :

• Explain the joy of solving problems (of course that would be hard if they have never done it before).
• Mention the benefits of being a competitive programmer (e.g. it will be easy to pass coding interviews).
• It worth giving a try! (actually, the whole post is about this!)

But here is the problem. I don't think that these "reasonings" attract people. So what to do?

Hi Codeforcers!
Recently I was trying to solve a query-type problem and after solving the problem I learned something new about C++ that I would like to share. Here's the problem statement:

We have a set that initially contains only a single 0. This set can contain multiple elements with the same value. We are given $$$Q$$$ queries. There are 3 types of queries:
1. INSERT x: Insert number x to the set,
2. DELETE x: Remove one occurrence of number x from the set. It is guaranteed that the number exists in the set,
3. MEDIAN: Print median of the numbers in the set. Median of a set of numbers is the middle element after sorting the numbers in the set in non-decreasing order. If the size of the set is a multiple of 2, among the two middle elements, print the left one.
Number of queries won't exceed $$$2 \cdot 10^5$$$.

I will assume that there is only INSERT/MEDIAN queries for convenience. DELETE operations are handled similar to INSERT in my solution.
Naive solutions won't pass the TL. By naive I mean inserting each element in $$$O(1)$$$ and for each MEDIAN queries sorting the container (probably std::vector) in $$$O(nlogn)$$$. This will lead us to an $$$O(Q\cdot n \cdot logn)$$$ total time complexity which won't pass the time limit with a strong test. I believe there is a solution using some non-STL data structures (e.g. policy based data structures, Fenwick Tree). However, we can solve this problem using std::multiset so we code less.

Solution
We take an iterator (std::multiset<T>::iterator) to the median and we maintain an index which is the 1-based index of the median element in the set.
If we got a MEDIAN query we will immediately print the median by dereferencing the iterator pointing to the median element. If we got an INSERT query we will insert the new element to the set and it is easy to see that by inserting one element the median index will change by at most one. So we can ++ or -- the iterator and keep maintaining the median element.

int main() {
    int q;
    cin >> q;

    multiset<int> ms{0};
    auto med_it = ms.begin();
    int med_idx = 1;

    while(q--) {
        string type;
        cin >> type;
        if(type == "MEDIAN") {
            cout << *med_it << '\n';
        }
        if(type == "INSERT") {
            int x;
            cin >> x;
            ms.insert(x);

            if(x < *med_it)
                med_idx++; // because x is inserted before our median

            int idx = (ms.size() + 1) / 2; // the index of real median

            if(med_idx < idx)
                ++med_it;
            if(med_idx > idx)
                --med_it;
            
            med_idx = idx;
        }
    }
}

At first I thought my solution is not going to work because inserting new element may invalidate iterators, but I was wrong. If you have an iterator pointing to an element of a set/multiset after inserting new elements into the set/multiset the mentioned iterator is still valid and you can use it. Similarly, if you delete an element which is not pointed by this iterator, this iterator is still valid and usable. that's why you can handle DELETE queries in this problem too (if you have understood this method so far that wouldn't be hard). Here are some references:
According to cppreference, std::multiset/insert: No iterators or references are invalidated.
Also, std::multiset/erase: References and iterators to the erased elements are invalidated. Other references and iterators are not affected.
I think it is good to mention that ++ and -- operators run in amortized constant time. (link)

I hope you've learned something new as I did :). Thank you.