### Errichto's blog

By Errichto, 2 years ago,

Meet in the Middle lecture & problem-solving starts in an hour https://www.twitch.tv/errichto. See the problem list below. I will later update this blog with codes and written explanations.
UPD, video recording: https://youtu.be/18sJ3mK173s, some codes from the stream: https://ideone.com/1uScID

P1. Knapsack with $n \leq 40$ and values up to $10^9$ https://cses.fi/problemset/task/1628

P2. Given a sequence $a_1, a_2, \ldots, a_n$ ($n \leq 2000$), count increasing subsequences of length 3.

P3. 4-SUM, find four values that sum up to the target value https://cses.fi/problemset/task/1642

P4. Find a string with the standard polynomial hash equal to the target value $X$ modulo $10^9+7$. The hash is computed by converting characters a-z into 0-25 and multiplying every character by the next power of 26. Find a solution without just converting $X$ to base $26$.

P5. You're given a graph: $n \leq 300$, $m \leq n\cdot(n-1)/2$. Count paths made of 5 nodes. Nodes and edges can be repeated.
Bonus 1: Count simple paths only. No repetitions allowed.
Bonus 2: $n, m \leq 2000$
Similar problem: https://codeforces.com/blog/entry/94003

P6. You're given a sequence $n \leq 10^6, 0 \leq a_i < M = 10^9$. Find two subsequences with equal sums modulo $M$. https://quera.ir/problemset/olympiad/34090. The two subsequences can have common elements.

P7. Number Clicker https://codeforces.com/contest/995/problem/E. You start with the number $a$ and want to get $b$ in at most 200 moves. You can increment, decrement or change the current number into its modular inverse, all modulo prime $p$. Find any valid sequence of moves.

• +242

| Write comment?
 » 2 years ago, # |   +48 Such streams are much appreciated. Please bring such streams more frequently.
•  » » 2 years ago, # ^ |   +3 Once a week or once every two weeks is fine I guess. He does problem solving streams also for both divisions, so it's the right balance in my opinion. There have been other such educational streams in the past (in case you didn't know) which you can find at his other youtube channel.
 » 2 years ago, # |   0 Thanks for this!Just a heads up, using an unordered_map TLEs on the 4-SUM problem whereas a map gets AC
 » 2 years ago, # |   0 I only knew about the version of birthday paradox where sampling O(sqrt(M)) values from [0, M) will have a high chance of finding two numbers that are equal. In the stream, the version of birthday paradox you used (for both p4 and p6) was that you will have a high chance of finding two numbers such that (x+y)%M == C for some target number C. I can see why the second version is true too (still trying to hit M possibilities out of M*M, using sqrt(M)*sqrt(M) samples) but it doesn't seem derivable from the regular form of the birthday paradox.Was that second version just a well known fact? Or is there a stronger form of the birthday paradox that you're using that can make such variations "obvious" to see? Are there any other variations of the birthday paradox that you've seen in problems besides x==y and x+y%M==C?
 » 22 months ago, # | ← Rev. 2 →   +3 thanks very much for this educational contest
 » 22 months ago, # |   0 today i found a problem related to this blog(Kickstart2021 Round G 3rd problem). problem link is below. (https://codingcompetitions.withgoogle.com/kickstart/round/00000000004362d6/00000000008b44ef) below is the link to my solution. (https://pastebin.com/2Svgwwen)
 » 5 months ago, # | ← Rev. 2 →   +2 What is the solution to P6? I tried to random shuffle the input, then generate all subset sum of the first 19 elements and the last 19 elements but it failed on around 7 tests. Here is my code: Code#include using namespace std; const int N = 1e6 + 5; const int SZ = 19; int n, m, a[N]; pair b[N]; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); map> mpl; int sum = 0; vector cur; void answer() { // found answer? vector oth = mpl[sum]; vector ans(n + 1); int cnt = 0; for (int i : oth) { ans[i] = 1; cnt++; } for (int i : cur) { if (ans[i] > 0) { ans[i] = 0; cnt--; } else { ans[i] = 2; cnt++; } } if (cnt == 0) return; cout << "alhamdolellah\n"; for (int i = 1; i <= n; i++) { cout << ans[i] << ' '; } cout << '\n'; exit(0); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; b[i] = {a[i], i}; } shuffle(b + 1, b + n + 1, rng); int szl = min(SZ, n); int szr = min(SZ, n); for (int msk = 0; msk < (1 << szl); msk++) { sum = 0; cur.clear(); for (int i = 1; i <= szl; i++) { if (msk >> (i - 1) & 1) { sum += b[i].first; if (sum >= m) sum -= m; cur.push_back(b[i].second); } } if (mpl.count(sum)) { answer(); } else { mpl[sum] = cur; } } for (int msk = 1; msk < (1 << szr); msk++) { sum = 0; cur.clear(); for (int i = n; i >= n - szr + 1; i--) { if (msk >> (n - i) & 1) { sum += b[i].first; if (sum >= m) sum -= m; cur.push_back(b[i].second); } } if (mpl.count(sum)) { answer(); } } cout << "laelahaellallah\n"; } Thanks in advance!
 » 4 months ago, # | ← Rev. 2 →   +5 Why does this give TLE? Is it because of the hashmap performance?