I and Radewoosh will virtually participate in Swiss-Slovak subregional (announcement, contest) on Tuesday at 16:00 CET. Watch my live stream on Twitch https://www.twitch.tv/errichto. Or later rewatch on YT https://youtu.be/M-xGjXwTXzQ.

Thanks to Xellos for the suggestion and majk for the contest.

This should be a nice warm-up before Petrozavodsk camp, which starts in a few days. I'm going to participate in half of the contests (as a member of mixed Polish Mafia team). I will record screencasts if allowed.

I'm going to solve CSES geometry section live on Saturday (tomorrow) while explaining and drawing stuff to make it educational. There are seven problems. We'll start with the cross-product recap and eventually get to Convex Hull and Closest Pair Of Points. No prewritten code.

Problems: https://cses.fi/problemset

Watch on Twitch or Youtube https://www.twitch.tv/errichto, https://youtu.be/G9QTjWtK_TQ. The latter will be available later to rewatch too.

Let's discuss the idea of IOI preparation in form of weekly contests and classes.

Many programming camps reuse problems from old national camps and contests. What about doing this on a bigger scale and conducting weekly mashup contests open for everybody for free? The problem analysis would be in English, in written or (live) video format, possibly combined with a lecture. Make a discord server for further discussion and questions, encourage students to upsolve, maintain yearly leaderboard and upsolving leaderboard. Once or twice a year, call it a 1-week online camp and organize these mashup contests daily.

I can take part in this initiative but I want to be just one of many teachers. When it's my turn, I would pick some old interesting POI or ONTAK problems because I either know them or can look up the solution in Polish. If I do this once per 1-2 months, I won't run out of good problems anytime soon, and I have enough time to prepare analysis and lecture, and later spend several hours just helping people with doubts and wrong codes. I can oversee this project at the beginning but then I'd prefer somebody else to take over.

Why?

There's clearly a need for IOI training. Almost every month, some country asks me if I can teach their IOI team by conducting a camp or mentoring them for a longer period. Even if a country has strong teachers or former participants, that usually just means one camp a year or classes for a single school. In my opinion, it's very important to train regularly, compete with others, and be able to ask questions. You can now participate regularly in Codechef Lunchtime or COCI but those are rare and neither of them emulates the camp experience.

Div2

If there are enough good subtasks, hard problems aren't a big issue for weak participants because they still have something to do and learn. Still, maybe once a month the contest should be just much easier to encourage everybody to participate? Or always add one more easy problem and recommend strong participants to skip it?

Codechef

I first thought that every contest should happen on its native platform like Szkopul for POI problems. It's easy to conduct such a contest made of old problems but the rules would be inconsistent and participants would need to create many accounts. A seemingly independent issue is money.

I then talked with Codechef and they agreed to pay teachers if it's all conducted on Codechef platform. Keeping track of everything would be much easier. Codechef staff will take care of adjusting the problem package format to the Codechef system but obviously, some problems might become unusable. (I think that CodeChef Lunchtime should then become part of this project too.)

By the way, you could find teachers who can work for free (like CSPrep by geniucos) but this is a time-consuming job, including the translation and helping students by answering their questions. Usually, camps exist because participants pay a fee or it's sponsored by a ministry of education, etc. I think that CodeChef is a good solution here. Nothing is decided yet so let me know if you disagree!

Possible Issues

1. Copyrights — Not every platform or old contest will allow reusing their problems in a different platform.
2. Language barrier — Some high school students don't know English well enough. From my teaching experience, strong participants usually don't have troubles, but weaker ones often prefer to resolve small doubts with a teacher or assistant who speaks their native language.
3. Timezones and collisions — We need a USACO-style long time window (it's supported by Codechef!) so you could choose when to start a 5-hour contest. If analysis or lecture is in live video format, it will still be tricky to find a 2-hour slot on Saturday or Sunday without collisions with regular contests. If somebody misses a live-stream, they should still be able to rewatch it and ask questions.
4. Quality — Just like for any camp, experienced teachers are necessary to ensure the quality of problems and analysis.

Please share your thoughts and suggestions!

Hi. I have a few announcements.

Among Us stream on Sunday, 20:00 CEST (just after CF 675 div2). The current team is me, Egor, kostka, tmwilliamlin168, alexwice, xiaowuc1, SecondThread, Reyna, ssense, the_white_devil, I_Love_YrNameCouldBeHere, gupta_samarth, FiveSixFiveFour. See you in the chat! https://www.twitch.tv/errichto

I stream programming regularly now: every Tuesday (hard Atcoder upsolving), Thursday (coding interviews) and Saturday (easy Codeforces problems), always starting at 9:00 PST / 18:00 CEST / 21:30 IST. You can import my google calendar. I won't announce these streams in Codeforces anymore, so say goodbye to blogs like "My Coding Streams in Month X". I might do an exception for something unusual or guest episodes. The schedule will always be at the bottom of my Twitch page https://www.twitch.tv/errichto.
(So yeah, Saturday easy stream starts in 15 minutes!)

If you are high-rated and I know you, you can join me for a Tuesday stream and we would solve hard AGC problems together. For example, I might be soon joined my mnbvmar for such pair problem-solving. If anybody's interested too, let me know.

Also: past live streams are available here; I'm preparing Gaussian Elimination lessons for CF EDU; join my Discord server.

For the second time (part1) enjoy two videos by me and SecondThread.

• My old problem 611F - New Year and Cleaning we discuss on his channel https://youtu.be/gmdBav_Nuuc
• Facebook Hacker Cup R3 problem B. Railroad Renovations on my channel https://youtu.be/2FlVv4acc2g

I hope you like this format of taking an old cool problem and just discussing it.

You can watch me live on https://www.twitch.tv/errichto or see stored broadcasts on https://www.youtube.com/errichto2. I will start with a week of daily streams and then it's just when I have time.

• September 8, 18:30 CEST — Codeforces Round #668 (recording)
• September 9, 17:00 CEST — chatting with viewers, random stuff (recording)
• September 10, 17:00 CEST — 1v1 lockout against Merkurev (recording)
• September 11, 17:00 CEST — recent Codechef lunchtime and cook-off contests (recording)
• September 12, 17:00 CEST — 2 hours of chill preparation for FHC R3, making a script for parallel computing
• Friday, Sep 18, 10:00 CEST — long boring stream, working on future videos like Guassian Elimination or Merge Sort
• Monday, Sep 21, 10:00 CEST — easy problem-solving: CF, binarysearch.com, ABC (recording)
• Tuesday, Sep 22, 10:00 CEST — coding interviews problem-solving: Leetcode and binarysearch.com (recording)
• Wednesday, Sep 23, 16:00 CEST — 1v1 lockout against gamegame
• Thursday, Sep 24, 10:00 CEST — upsolving AGC 25

I will stream regularly now: hard problems on Tuesday, coding interviews on Thursday, easy problems on Saturday

• NEW Tuesday, Sep 29, 18:00 CEST — upsolving Atcoder Grand Contest 45
• NEW Tuesday, Oct 1, 18:00 CEST — coding interview problems

Hi. I invite you to AtCoder Grand Contest 047.

• Contest URL: https://atcoder.jp/contests/agc047
• Start time: Sunday, August 9, 12:00 UTC
• Duration: 140 minutes
• 6 Problems, 300-700-800-1000-(800+1000)-2200
• Writer: Errichto
• Rated range: 1200+

Statements are very short and I think that problems are interesting. Big thanks to rng_58 for discussing problems with me.

I will likely make a short live stream just after the contest ends. (update: watch the recording here)

UPD, congrats to tourist for winning and Benq for the second full score.

tl;dr — video tutorial https://www.youtube.com/watch?v=eMXNWcbw75E and codeforces GYM training https://codeforces.com/gym/102644 (register by finding this contest in GYM instead of using the link directly)
video editorial: part 1 (ABCDEF) and part 2 (GHI)
codes to all 9 problems: https://github.com/Errichto/youtube/tree/master/matrix-exponentiation

Prerequisites: binary exponentiation and iterative dp (you don't need to know matrices)

The youtube tutorial (link) focuses on intuition and graph-like visualization . Or, if you prefer, below is a shorter (less detailed) text tutorial instead. You can practice by solving a set of 9 educational problems in GYM https://codeforces.com/gym/102644. ABCD are easy, EF medium, GHI are hard. If you are stuck, see hints below or watch the full solution analysis — part 1 (ABCDEF) and part 2 (GHI).

Hints

int n;
cin >> n;
int a = 0, b = 1;
for(int i = 2; i <= n; i++) {
	int new_a = 0 * a + 1 * b;
	int new_b = 1 * a + 1 * b;
	a = new_a;
	b = new_b;
}
cout << a << " " << b << endl;

int n;
cin >> n;
int arr[2] = {0, 1};
for(int i = 2; i <= n; i++) {
	int new_arr[2] = {0, 0};
	new_arr[0] = 0 * arr[0] + 1 * arr[1];
	new_arr[1] = 1 * arr[0] + 1 * arr[1];
	
	arr[0] = new_arr[0];
	arr[1] = new_arr[1];
}
cout << arr[0] << " " << arr[1] << endl;

int variable_array[...]; // create all variables you need
for(int _ = 0; _ < k; _++) {
  do something; // don't use the underscore variable
}

Matrix Exponentiation

Consider this problem:
String Mood — Limak can be either happy or sad. His mood changes (or stays same) when he reads an English uppercase letter. Letters S and D always make him sad, H makes him happy, and every vowel (AEIOU) flips his mood. Other letters do nothing.
Limak is happy right now. Among all $$$26^n$$$ possible strings of length $$$n$$$ ($$$n \leq 10^{18}$$$), count such strings that Limak will be happy after reading that string, modulo $$$10^9+7$$$.

If something can be solved with dp in $$$O(1)$$$ space, we can usually speed it up later with matrix exponentiation. This dp is easy — for length from $$$1$$$ to $$$n$$$ compute the number of strings making you happy and making you sad at the end.

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main() {
	long long n;
	cin >> n;
	long long happy = 1, sad = 0;
	for(long long i = 0; i < n; ++i) {
		long long new_happy = (19 * happy + 6 * sad) % mod; // 19 letters will keep you happy, etc.
		long long new_sad = (7 * happy + 20 * sad) % mod;
		happy = new_happy;
		sad = new_sad;
	}
	cout << happy << endl;
}

Let's visualize that by drawing vertices representing the two moods, and edges with the number of ways to move from one state to the other.

For example, if you are happy, there are 19 ways to make you happy and 7 ways to make you sad (SDAEIOU). Thin edges on the right represent the second letter of a string and the number there should be the same, because they are again 19 ways to make you happy if you were happy, etc. If we were asked about answer for $$$n = 2$$$, we would need to compute the number of ways to get from HAPPY state in first column to HAPPY state in third column, which is they yellow edge below.

That's $$$19 \cdot 19 + 7 \cdot 6 = 403$$$. In a similar way, we can compute all four counts for 2-letter strings: happy to happy (equal to $$$403$$$), happy to sad ($$$19\cdot7+7\cdot20=273$$$), sad to happy ($$$234$$$), sad to sad ($$$442$$$). We'll actually keep these four values $$$[[403,273],[234, 442]]$$$ in a 2-dimensional array, also called a matrix.

Starting from a matrix with four values describing 1-letter strings $$$[[19,7],[6,20]]$$$, in $$$O(1)$$$ we got a matrix describing 2-letter strings. We can do the same to get a matrix for 4-letter strings, then 8-letter strings, and so on. We can do binary exponentiation to find a matrix for any huge $$$n$$$. Formally, we compute $$$M^n$$$ where $$$M = [[19,7],[6,20]]$$$ and multiplying two matrices is exactly what we did above to compute a new matrix $$$[[403,273],[234, 442]]$$$, done with the following code:

for(int i = 0; i < s; i++) { // s is the number of states, s=2 in the String Mood problem
	for(int j = 0; j < s; j++) {
		for(int k = 0; k < s; k++) {
			new_matrix[i][k] += matrix1[i][j] * matrix2[j][k];
		}
	}
}

The total time complexity is $$$O(s^3 \cdot \log n)$$$ where $$$s$$$ is the matrix size (also called order), which is equal to the number of states (variables) you need in space-efficient dp. We had $$$s=2$$$ in String Mood so the complexity is just $$$O(\log n)$$$.

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
#define REP(i, n) for(int i = 0; i < (n); i++)
struct Matrix {
	long long a[2][2];
	Matrix() {
		REP(i, 2) {
			REP(j, 2) {
				a[i][j] = 0;
			}
		}
	}
	Matrix operator *(Matrix other) {
		Matrix product = Matrix();
		REP(i, 2) {
			REP(j, 2) {
				REP(k, 2) {
					product.a[i][k] += a[i][j] * other.a[j][k];
					product.a[i][k] %= mod;
				}
			}
		}
		return product;
	}
};
Matrix expo_power(Matrix a, long long n) {
	Matrix res = Matrix();
	res.a[0][0] = res.a[1][1] = 1;
	while(n) {
		if(n % 2) {
			res = res * a;
		}
		n /= 2;
		a = a * a;
	}
	return res;
}
int main() {
	long long n;
	cin >> n;
	Matrix single = Matrix();
	single.a[0][0] = 19;
	single.a[0][1] = 7;
	single.a[1][0] = 6;
	single.a[1][1] = 20;
	Matrix total = expo_power(single, n);
	cout << total.a[0][0] << endl;
}

Now, try to find the $$$n$$$-th Fibonacci number for $$$n \leq 10^{18}$$$ (problem link) by first implementing space-efficient dp with transitions of form new_variable += old_variable * x where $$$x$$$ is some number you will need to put in the initial matrix (like $$$19$$$ or $$$7$$$ in String Mood).

Footnote

Thanks to tnowak for suggesting and creating one problem, and to mnbvmar for a few problem ideas. For the future, I'm looking for somebody to help me with the preparation of such training contests. If you want to help and you are high-rated and perfectly with experience in using polygon, please write to me. I can pay you a little if you want.

I hope you learned something thanks to this tutorial. Feel free to discuss problems from the GYM contest or give links to more matrix exponentiation problems or useful resources. If anybody wants that, I can make tests public. If you are a teacher and want to use some problems in your classes, I will give you access in Polygon.

I will host my first lockout stream on Sunday, June 28, 19:00 CEST / 20:00 MSK, featuring tourist, Radewoosh, majk and Egor. I'm not sure if we will use Codeforces or Atcoder problems.

You can watch it live on https://www.twitch.tv/errichto and later on youtube.

Watch previous streams organized by ecnerwala (not alone), more info in blogs one, two and format/rules.

EDIT Congratulations to Egor for the win! You can watch the recording on Youtube https://youtu.be/N7ec-OoxvHg
I was a great experience, you should expect the next lockout at the end of July :)

While I have mixed feelings about division 4, I think it perfectly matches introducing the rating lowerbond in division 2.

Maybe 1501 is a good idea, I'm not sure. Or maybe let new participants have 1400 initially (upper bound for div4) and lowerbound for div2 would be 1401.

The benefits are decreased load for the main and rare div1+2 rounds, and possibility to slightly increase the difficulty of div2-abc, thus get back to the format with 5 problems per division (3 are common). Because the contest is then for a group of people with more similar skill level. These arguments aren't that important for div2-only contests so it's ok if those are without lowerbound, I don't care. Or make those div2+3 instead of div2-only, I again don't care.

You can watch me on https://www.twitch.tv/errichto or https://www.youtube.com/errichto2. There is schedule with countdown on Twitch. Most likely I will stream in May on Tuesday mornings and Sunday evenings.

• May 3, 16:45 CEST — Codeforces hard (solving hard problems because the round was moved)
• May 5, 9:00 CEST — Boring Programming Stream (planning videos, fixing chatbot, maybe learning Berlekamp–Massey)
• May 10, 18:00 CEST — Atcoder hard (Grand Contest 43?)
• May 12, 9:00 CEST — Atcoder hard or something similar to practice for Google Code Jam.
• May 17, 18:00 CEST — Chill stream. I will chat with the audience, implement an algorithm to move an elevator (https://play.elevatorsaga.com/) and try to dock Crew Dragon to the ISS (https://iss-sim.spacex.com/).
• May 19, 9:00 CEST — Codeforces hard (recent round #641)
• May 24, 18:00 CEST Atcoder hard (AGC 44, problems C and D)
• May 26, 9:00 CEST Gauss & Matrix expo (preparing future youtube lectures)
• May 31, 18:00 CEST May Leetcode Challenge (I will try to solve 30 problems in 1 hour. This is more mainstream so will be on the main YT channel Errichto https://youtu.be/0yemVXDBbyg)

(updated on May 30)

two recent videos for beginners: Computations Modulo P, Binary Exponentiation
in works: Matrix Expo, Gaussian Elimination, EV in Chain-graph, Berlekamp-Massey

JUNE UPDATE — June 20, 19:00 CEST solving random problems suggested by viewers

On Tuesday, April 14, I will solve random problems live on Youtube, until I hit 100k subs. Suggestions in the chat are welcome.

https://youtu.be/rEGDNd-9PAU (there's countdown to start)

I recently made two mainstream videos which are a good introduction to CP, I think.

How to start with Competitive Programming? https://youtu.be/xAeiXy8-9Y8

About Programming Competitions (Codeforces, Code Jam, ...) https://youtu.be/cpguolx2oms

UPD

What is Competitive Programming? https://youtu.be/ueNT-w7Oluw (by tmwilliamlin168)

HoW tO BEcOmE rEd cOdeR? https://youtu.be/y7169jEvb-Y

UPD2

Steps and Mistakes https://youtu.be/bVKHRtafgPc (by tmwilliamlin168 again)

At 18:00 CET on Saturday, as a warm-up before Google Hash Code qualification round, I will solve a practice problem (or just some old problem?) live together with my teammate kabuszki. You can watch us on YT or Twitch https://www.youtube.com/errichto2/live & https://www.twitch.tv/errichto. I know it collides with SRM but this time is convenient for me.

Maybe I will also record our qualification round performance on Thursday, we'll see.

Unrelated: expect a few short problem-solving streams next week, stay tuned.

I'm back to streaming and I plan the following three problem-solving streams, each lasting around 5 hours:

• At 8am CET on Thursday, February 6 AtCoder easy problems (ABC), including the most recent ABC 153.
• At 8am CET on Monday, February 10 AtCoder hard problems (AGC), including the most recent AGC 41 by tourist.
• At 8am CET on Thursday, February 13 LeetCode recent problems.

I will think out loud and talk about solutions, sometimes with implementation too. Streams 1 and 3 are meant to be educational, while stream 2 will be more of me thinking and struggling. I will not do virtual participation because the pressure of time doesn't go well with explaining anything.

You can watch me on my secondary Youtube channel https://www.youtube.com/errichto2/live or on Twitch https://www.twitch.tv/errichto.

See you in the chat :)

UPD — I will make shorter streams on Monday (the 17th) and Thursday (the 20th). It will be Codeforces div1C-D problems and Boring stream, respectively. I'm updating this old blog so I wouldn't spam with new one.

Part 1 (link) introduces basic bitwise operations. This is part 2 and it's mainly about (in)famous bitsets and example problems. Also, see links to very useful advanced stuff at the bottom. EDIT: here's video version of this blog (on my Youtube channel).

Built-in functions

In C++, __builtin_popcount(x) returns popcount of a number — the number of ones in the binary representation of $$$x$$$. Use __builtin_popcountll(x) for long longs.

There are also __builtin_clz and __builtin_ctz (and their long long versions) for counting the number of leading or trailing zeros in a positive number. Read more here. Now, try to solve these two simple tasks in $$$O(1)$$$, then open the spoiler to check the solution:

While popcount is often needed, I rarely use the other two functions. During a contest, I would solve the two tasks above in $$$O(\log x)$$$ with simple while-loops, because it's easier and more intuitive for me. Just be aware that these can be done in $$$O(1)$$$, and use clz or ctz if you need to speed up your solution.

Motivation behind bitsets

Consider this problem: There are $$$N \leq 5000$$$ workers. Each worker is available during some days of this month (which has 30 days). For each worker, you are given a set of numbers, each from interval $$$[1, 30]$$$, representing his/her availability. You need to assign an important project to two workers but they will be able to work on the project only when they are both available. Find two workers that are best for the job — maximize the number of days when both these workers are available.

You can compute the intersection of two workers (two sets) in $$$O(30)$$$ by using e.g. two pointers for two sorted sequences. Doing that for every pair of workers is $$$O(N^2 \cdot 30)$$$, slightly too slow.

We can think about the availability of a worker as a binary string of length $$$30$$$, which can be stored in a single int. With this representation, we can count the intersection size in $$$O(1)$$$ by using __builtin_popcount(x[i] & x[j]). The complexity becomes $$$O(N^2)$$$, fast enough.

What if we are given the availability for the whole year or in general for $$$D$$$ days? We can handle $$$D \leq 64$$$ in a single unsigned long long, what about bigger $$$D$$$?

We can split $$$D$$$ days into convenient parts of size $$$64$$$ and store the availability of a single worker in an array of $$$\frac{D}{64}$$$ unsigned long longs. Then, the intersection can be computed in $$$O(\frac{D}{64})$$$ and the whole complexity is $$$O(N^2 \cdot \frac{D}{64})$$$.

const int K = MAX_D / 64 + 1;
unsigned long long x[MAX_N][K];
int intersection(int i, int j) {
	int total = 0;
	for(int z = 0; z < K; z++) {
		total += __builtin_popcountll(x[i][z] & x[j][z]);
	}
	return total;
}

So, we can simulate a long binary number with multiple unsigned long longs. The implementation isn't that bad but doing binary shifts would be quite ugly. Turns out all of this can be done with bitsets easily.

Bitsets

bitset<365> is a binary number with $$$365$$$ bits available, and it supports most of binary operations. The code above changes into simple:

bitset<MAX_D> x[MAX_N];
int intersection(int i, int j) {
	return (x[i] & x[j]).count();
}

Some functions differ, e.g. x.count() instead of __builtin_popcount(x) but it's only more convenient. You can read and print binary numbers, construct a bitset from int or string bitset<100> a(17); bitset<100> b("1010");. You can even access particular bits with b[i]. Read more in C++ reference https://en.cppreference.com/w/cpp/utility/bitset.

Note that the size of the bitset must be a constant number. You can't read $$$n$$$ and then declare bitset<n> john;. If $$$n$$$ is up to $$$100$$$, just create bitset<100>.

The complexity of bitwise operations is $$$O(\frac{size}{32})$$$ or $$$O(\frac{size}{64})$$$, it depends on the architecture of your computer.

Problems

P1. Different numbers — You are given a sequence of $$$N \leq 10^7$$$ numbers, each from interval $$$[0, 10^9]$$$. How many different values appear in the sequence? Don't use set or unordered_set because they quite slow.

P2. Knapsack — You are given $$$N \leq 1000$$$ items, each with some weight $$$w_i$$$. Is there a subset of items with total weight exactly $$$W \leq 10^6$$$?

bool can[MAX_W];
int main() {
	int n, W;
	cin >> n >> W;
	can[0] = true;
	for(int id = 0; id < n; id++) {
		int x;
		cin >> x;
		for(int i = W; i >= x; i--) {
			if(can[i-x]) can[i] = true;
		}
	}
	puts(can[W] ? "YES" : "NO");
}

bitset<MAX_W> can;
int main() {
	int n, W;
	cin >> n >> W;
	can[0] = true;
	for(int id = 0; id < n; id++) {
		int x;
		cin >> x;
		can = can | (can << x); // or just: can |= (can << x);
	}
	puts(can[W] ? "YES" : "NO");

P3. Triangles in a graph — Given a graph with $$$n \leq 2000$$$ vertices and $$$m \leq n \cdot (n - 1) / 2$$$ edges, count triples of vertices $$$a, b, c$$$ such that there are edges $$$a-b$$$, $$$a-c$$$ and $$$b-c$$$.

P4. Chef and Queries — https://www.codechef.com/problems/CHEFQUE (easy)

P5. Odd Topic — https://www.codechef.com/AABH2020/problems/ODTPIC (medium), thanks to Not-Afraid for the suggestion

P6. Funny Gnomes — https://www.codechef.com/problems/SHAIKHGN (hard)

Bonuses

1) m & (m-1) turns off the lowest bit that was set to $$$1$$$ in a positive number $$$m$$$. For example, we get $$$24$$$ for $$$m = 26$$$, as $$$11010$$$ changes into $$$11000$$$. Explanation on quora
2) A quite similar trick allows us to iterate efficiently over all submasks of a mask, article on cp-algorithms / e-maxx. This article also explains why masks-submasks iteration is $$$O(3^n)$$$.
3) DP on broken profile (grid dp) — https://cp-algorithms.com/dynamic_programming/profile-dynamics.html
4) SOS dp (sum over subset) — https://codeforces.com/blog/entry/45223 & https://www.youtube.com/watch?v=Lpvsd8WpbWc&t=5m4s
5) _Find_next function and complexity notation for bitsets — https://codeforces.com/blog/entry/43718

I will add links to some problems in online judges, feel free to suggest some in the comments. I think that bonuses 3 and 4 lack some explanation with drawings, maybe I will make some soon.

You can watch my Youtube video (link) with the same content as this blog. Anyway, enjoy.

Introduction

Let's learn bitwise operations that are useful in Competitive Programming. Prerequisite is knowing the binary system. For example, the following must be clear for you already.

Keep in mind that we can pad a number with leading zeros to get the length equal to the size of our type size. For example, char has $$$8$$$ bits and int has $$$32$$$.

Bitwise AND, OR, XOR

You likely already know basic logical operations like AND and OR. Using if(condition1 && condition2) checks if both conditions are true, while OR (c1 || c2) requires at least one condition to be true.

Same can be done bit-per-bit with whole numbers, and it's called bitwise operations. You must know bitwise AND, OR and XOR, typed respectively as & | ^, each with just a single character. XOR of two bits is $$$1$$$ when exactly one of those two bits is $$$1$$$ (so, XOR corresponds to != operator on bits). There's also NOT but you won't use it often. Everything is explained in Wikipedia but here's an example for bitwise AND. It shows that 53 & 28 is equal to $$$20$$$.

53 = 110101
28 = 11100

  110101
&  11100  // imagine padding a shorter number with leading zeros to get the same length
 -------
  010100  =  20

#include <bits/stdc++.h>
using namespace std;

string to_binary(int x) {
	string s;
	while(x > 0) {
		s += (x % 2 ? '1' : '0');
		x /= 2;
	}
	reverse(s.begin(), s.end());
	return s;
}

int main() {
	cout << "13 = " << to_binary(13) << endl; // 1101
	
	int x = 53;
	int y = 28;
	cout << "x = " << to_binary(x) << ", y = " << to_binary(y) << endl;
	
	cout << "AND, OR, XOR:" << endl;
	cout << to_binary(x & y) << " " << to_binary(x | y) << " " << to_binary(x ^ y) << endl;
}

Shifts

There are also bitwise shifts << and >>, not having anything to do with operators used with cin and cout.

As the arrows suggest, the left shift << shifts bits to the left, increasing the value of the number. Here's what happens with 13 << 2 — a number $$$13$$$ shifted by $$$2$$$ to the left.

    LEFT SHIFT                             RIGHT SHIFT
       13 =     1101                          13 =   1101
(13 << 2) =   110100                   (13 >> 2) =     11   

If there is no overflow, an expression x << b is equal to $$$x \cdot 2^b$$$, like here we had (13 << 2) = 52.

Similarly, the right shift >> shifts bits to the right and some bits might disappear this way, like bits 01 in the example above. An expression x >> b is equal to the floor of $$$\frac{x}{2^b}$$$. It's more complicated for negative numbers but we won't discuss it.

So what can we do?

$$$2^k$$$ is just 1 << k or 1LL << k if you need long longs. Such a number has binary representation like 10000 and its AND with any number $$$x$$$ can have at most one bit on (one bit equal to $$$1$$$). This way we can check if some bit is on in number $$$x$$$. The following code finds ones in the binary representation of $$$x$$$, assuming that $$$x \in [0, 10^9]$$$:

for(int i = 0; i < 30; i++) if((x & (1 << i)) != 0) cout << i << " ";

(we don't have to check $$$i = 30$$$ because $$$2^{30} > x$$$)

And let's do that slightly better, stopping for too big bits, and using the fact that if(value) checks if value is non-zero in C++.

for(int i = 0; (1 << i) <= x; i++) if(x & (1 << i)) cout << i << " ";

Consider this problem: You are given $$$N \leq 20$$$ numbers, each up to $$$10^9$$$. Is there a subset with sum equal to given goal $$$S$$$?

It can be solved with recursion but there's a very elegant iterative approach that iterates over every number $$$x$$$ from $$$0$$$ to $$$2^n - 1$$$ and considers $$$x$$$ to be a binary number of length $$$n$$$, where bit $$$1$$$ means taking a number and bit $$$0$$$ is not taking. Understanding this is crucial to solve any harder problems with bitwise operations. Analyze the following code and then try to write it yourself from scratch without looking at mine.

for(int mask = 0; mask < (1 << n); mask++) {
	long long sum_of_this_subset = 0;
	for(int i = 0; i < n; i++) {
		if(mask & (1 << i)) {
			sum_of_this_subset += a[i];
		}
	}
	if(sum_of_this_subset == S) {
		puts("YES");
		return 0;
	}
}
puts("NO");

Two easy problems where you can practice iterating over all $$$2^N$$$ possibilities:
- https://codeforces.com/problemset/problem/1097/B
- https://codeforces.com/problemset/problem/550/B

Speed

Time complexity of every bitwise operation is $$$O(1)$$$. These operations are very very fast (well, popcount is just fast) and doing $$$10^9$$$ of them might fit in 1 second. You will later learn about bitsets which often produce complexity like $$$O(\frac{n^2}{32})$$$, good enough to pass constraints $$$n \leq 10^5$$$.

I will welcome any feedback. Coming next: popcount, bitsets, dp with bitmasks. I will also make a YT video on this. YT video link is at the top.

Part 2 link

Instructions how to setup up Linux and Geany for competitive programming: https://github.com/Errichto/youtube/wiki/Linux-setup

An optional video that shows the process: https://youtu.be/ePZEkbbf3fc

I created this because so many people ask me about my environment and compilations flags. You don't have to follow exactly these steps or actually use Linux at all. Remember that 99% of your performance comes from skills so you should focus on that instead of worrying too much about tools you use.

Previous part: https://codeforces.com/blog/entry/63606

Apparently, one of problems had incorrect output data. Can someone confirm? On the bright side, no huge technical issues this year afaik.

Unpopular opinion here: Prague isn't a good organizer :O

Also, some disqualification in the top happened :O

I and Lewin will do some commentary of TCO semifinal 1, starting in a few minutes. Watch it on TCO Twitch website.

Stream: https://www.twitch.tv/topcoder_official

Statements: https://docs.google.com/document/d/1OjmXL8DMDiWf92XhLch_xjjPVA21-dvIhcnYEh_0CbM/edit?usp=sharing

You can watch the lecture on Youtube: https://youtu.be/0r2D32esF3Y. I will do a second part soon. Some problems are quite vague, it's a nature of this topic.

1. Warm-up: You toss a coin till you get tails. How many tosses there will be, on average?
2. X or smaller — There is a hidden number $$$X$$$. An interactor repeatedly gives you a number, either $$$X$$$ or something smaller than $$$X$$$. All numbers are positive integers. When can you stop and say that you are (almost) certain what is the value of $$$X$$$?
3. Line through N/4 points — Given $$$N \leq 10^5$$$ points, find a line that passes through the maximum number of points. It's guaranteed that the answer is at least $$$N / 4$$$.
4. GCD (364D - Ghd) — given a set of $$$N \leq 10^6$$$ numbers, each up to $$$10^{12}$$$, find the maximum possible number that is a divisor of at least half of given numbers.
5. ACTG prefix — Guess a hidden string $$$S$$$ with characters A, C, T, G. You can choose some string and ask if it's a prefix of $$$S$$$. The length of $$$S$$$ is at most $$$10\,000$$$ and you can ask up to $$$25\,000$$$ queries.
6. How many tails you will get after tossing a fair coin $$$10^6$$$ times? It should be around $$$500\,000$$$, but how far away from this number can you realistically/plausibly get?
7. Don't use a fixed seed in Codeforces or Topcoder because somebody can hack/challenge you.
8. RAND_MAX in Codefoces is around $$$30\,000$$$, so use your own rand() in C++, same for random_shuffle(). More here: https://codeforces.com/blog/entry/61587

More (and harder) problems can be found here: https://codeforces.com/blog/entry/51244

And if you want to learn more about expected value: https://codeforces.com/blog/entry/62690

Save trees: https://youtu.be/TnCVAEsYGKs #TeamTrees

EDIT, part 2: https://youtu.be/GS2MxmorEzc

1. Catch 'em all — When you encounter a Pokemon, it's random out of $$$N$$$ types. How many Pokemon will you encounter (on average) before seeing all $$$N$$$ types? Estimate this value.
2. Birthday paradox — How many encounters before we see the same type of Pokemon twice?
3. Hash collision — what is the probability of hash collision in problems like "given queries, check if this substring is equal to that substring" compared to "given a bunch of strings, find a pair of equal strings". The latter has much bigger probability of collision. Why?
4. How to randomly shuffle an array?
5. Repeated binary search — Find max element in a hidden sequence by asking queries "is $$$a_i$$$ greater than $$$x$$$?" faster than $$$\mathcal O(n \log n)$$$, https://codeforces.com/blog/entry/62602
6. Bonus: estimate $$$\pi$$$ using randomized algorithm.

There are two mainstream contests tomorrow (Google Kickstart and Leetcode biweekly) and I will make a live stream just after them at 18:30 CEST on Saturday. After talking about some problems from those contests, I will upsolve Codeforces or Topcoder problems, maybe from a recent CF round by tourist.

Watch me on Youtube — https://youtu.be/w3W-w0EXEtc.

Hey, hi, hello.

Codeforces Round #584 - Dasha Code Championship - Elimination Round (rated, open for everyone, Div. 1 + Div. 2) starts on Sep/14/2019 16:05 (Moscow time) and lasts 2h30m. The score drain will be adjusted for longer contest duration. It's a combined rated round with around eight problems. It is open and it is rated for everybody. Yes, it's rated. There are Dasha t-shirts for top 30 competitors (not counting later-to-be onsite finalists).

As an extra, this is an elimination round for those who live in/near SPb/Novosibirsk. More info about the championship is in the other blog. Thanks to Dasha.AI for making such an event for the community!

Problems are prepared by MikeMirzayanov, FieryPhoenix, dragonslayerintraining and Errichto. One of these setters also created Codeforces, thanks for that! And huge thanks to cdkrot for coordinating the round, to Merkurev, isaf27, KAN and me for testing, and finally to mareksom, Radewoosh and Marcin_smu for some small help.

I wish you more fun than bugs. Enjoy the contest!

PS. I recorded the process of preparing one problem with commentary, will publish it on Youtube after the contest. EDIT: https://www.youtube.com/watch?v=IaViSV0YBog

UPDATE, points: A 500, B 500, C 1250, D 1500, E 1000+1500, F 2500, G 1500+2250, H 4000. There are 8 problems and 2 of them are split into two versions. Good luck!

UPDATE, huge congratulations to winners!

1. Petr
2. Retired_MiFaFaOvO
3. LayCurse
4. zeliboba
5. 300iq

I was the author of last two problems: Into Blocks (but thanks for cdkrot for preparing it!) and Walkways, hope you liked them.

UPDATE, editorial is out.

I think that all problems looked awful at the first sight but actually all were quite cool :O

editorial (was posted as announcement after the round)

Congratulations to advancers! Results screenshot below (top10 gets to the finals + some early advancers from previous rounds).

I conducted a camp for Kazakhstan via the Internet and I was allowed to record it. I'm putting some of those lectures and problem analysis on Youtube. Maybe it will be useful for participants who are still practicing. See recent videos here, https://www.youtube.com/errichto2.

There are currently solutions for Innopolis Open 2018-19 (cool hard contest in CF GYM), two days of POI 23 (2015-2016) and also a lecture on wavelet trees. Innopolis Open solutions include these two methods:

Will soon add some more, including segment tree beats and Li Chao tree.