Introduction

This last weekend, I took part in the Southeast Asia Team Selection Test (SEATST). On day $$$1$$$, to grab a $$$28$$$ point subtask, I used a interesting trick involving cache-optimisation and square root decomposition that I thought was cool, so naturally I am writing my first CF blog to talk about it.

The Problem

Suppose we have an array of $$$N$$$ vectors, $$$V_1$$$ to $$$V_N$$$, and we wish to perform $$$Q$$$ insertion operations of the form $$$(x, y)$$$, where we insert the value $$$y$$$ to the back of vector $$$V_x$$$. For instance, you might want to do this for a counting sort if the log factor from sorting is too large.

For the rest of this blog, we shall assume $$$N=10^6, Q=10^8$$$.

The naive solution

Below is the code I used for testing the naive solution. ~~~~~

include <bits/stdc++.h>

using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 1e6; const int Q = 1e8; vector V[N]; main(){
int x, y; for(int i=0;i<Q;i++){ x = rng() % N; y = rng(); V[x].push_back(y); } } ~~~~~ For the other pieces of code in this blog I will not include the boilerplate (i.e. everything outside of main).

Of course we need a control to see how much time generating random numbers took. Below is the control ~~~~~ main(){
int x, y; for(int i=0;i<Q;i++){ x = rng() % N; y = rng(); } } ~~~~~