Errichto's blog

By Errichto, 3 weeks ago, In English

Hi, I'm going to teach competitive programming classes this Summer, starting with a 4-week batch to see how it goes. I hope to make 2 or 3 groups of ~12 students, each group aimed at some CF rating. We will use problems from Codeforces, CSES, Atcoder, Polish olympiad (only higher group), and my modifications and follow-ups. There will be homework, some to be discussed next lesson.

  • Dates: June 24 to July 19 (4 weeks)
  • Time: morning-noon in Europe
  • 2-3 lessons per week, 1.5h or 2h each
  • Price: around 20 USD per hour, 260-440 USD total per person
  • Platform: Discord and/or Google Meet

Please fill this form to get a 5% early-bird discount. I will use the results to choose and announce groups (difficulty and frequency) in 1-2 weeks.

Feel free to ask questions in the comments, or DM me.

regarding the idea of USACO classes

Update (6.06.2024): We will do 2 x 1.5h lessons per week, with total cost of 260 USD for 8 lessons, every Monday and Thursday from June 24 to July 18 (or up to July 25 if we skip a lesson or two). There will be three groups:

  1. 8:00-9:30, CF max rating 1000-1400 (time in CEST, Poland)
  2. 10:00-11:30, CF max rating 1500-1800
  3. 12:00-13:30, CF max rating 1900-2200

You can pay via Paypal https://paypal.me/errichto or contact me for details of Revolut, Wise or EUR wire transfer. The transfer title should be "CF Classes yourcfhandle" or similar. After paying, contact me with your Discord handle and group preference. Remember about the 5% discount if you have filled the form before.

Full text and comments »

  • Vote: I like it
  • +156
  • Vote: I do not like it

By Errichto, 7 weeks ago, In English

Hi, I'm back from the ICPC finals (and proud of Harbour.Space Barcelona for a gold medal!). I have a few announcements for those preparing for an olympiad.

USACO Platinum weekend camp by AlphaStar

A free online olympiad camp for USACO platinum students and CF 1800+ users. Both days start at 9:30 am Pacific / 18:30 CEST. Thanks to AlphaStar for organizing the event. https://alphastar.academy/events/

May 11 (Saturday)
The first day will be two medium-difficulty 3-hours contests with analysis. Skip this if you're an experienced platinum contestant.

May 12 (Sunday)
For stronger participants: 5-hour contest + analysis
For others: lectures on centroid decomposition, EV and summation, randomized algorithms. Then you have 30 minutes to get familiar with the 5-hour contest problems so you could attend the analysis.

I will use existing problems from Polish olympiads, and there'll be a guest problem by bmerry.

Huawei IOI camp in the Summer

This is not finalized yet. Just like two previous years 2022 2023, I will likely organize a free online camp for IOI participants, sponsored by Huawei. This year, I think about using old IOI contests (from around 2014) instead of POI and CEOI. Is August a good month for this? Any collisions that we should avoid?

My USACO classes / school

I'm thinking about teaching USACO bronze/silver/gold classes this July. It would be one month of learning all the important topics and solving a bunch of problems. Groups of around 10 students, 2-3 lessons per week, 1.5-2h per lesson, Discord group to talk between classes. Price around 35$ per hour, so the total should be 500-900 USD. The lesson time would be morning/noon Pacific (afternoon/evening in Europe).

If you're interested, fill this form (link) about your preferences for a 5% early-bird discount (if I actually do organize this). You can register for general olympiad preparation, not just USACO. It's normally difficult for me to work with students from the US because of the timezone difference. It's more viable during their Summer break, hence the focus on USACO here.

Full text and comments »

  • Vote: I like it
  • +119
  • Vote: I do not like it

By Errichto, 10 months ago, In English

Here's the previous edition and the video recordings (CEOI 2016, 2017, 2022, two lectures).

Hi. I'm again conducting an online IOI preparation camp in collaboration with Huawei. Every day will be a 5-hour virtual contest, the problem analysis, and sometimes a lecture. Contests will consist of POI problems, and there might be a single day from BOI or CEOI. The example lecture topics are those from Range Queries or Trees in Usaco Guide Platinum.

The camp is free for IOI 2023 participants and coaches. You can register a few extra students if you're a country team-leader (then send me a msg in CF or email at erri..to@gmail.com). There will be a Discord server and a leaderboard. For everybody else, the video recordings will be posted on Youtube after the camp.

Dates: around 8-16.08
Time of every analysis/lecture: 14:00 UTC / 16:00 CEST
Platform: Discord, Szkopul, CSES
Registration: write a message to gupta_samarth with your name, country and Discord handle (necessary!), and information if you're an IOI participant. Or you can reach via Discord directly, same username. UPDATE: Reach out to me directly if you're a coach and you want to register multiple students.

Schedule: (work in progress)
8.08 — POI 2019
9.08 — POI 2013
10.08 — day off
11.08 — POI 2017
12.08 — POI 2019
13.08 — day off
14.08 — CEOI 2021? Or maybe 2017/2018/2020?
15.08 — maybe CEOI 2023 mirror
16.08 — CEOI 2021?
17.08 — maybe CEOI 2023 mirror

Big thanks to Huawei UK R&D for sponsoring this camp.

Full text and comments »

  • Vote: I like it
  • +220
  • Vote: I do not like it

By Errichto, 11 months ago, In English

Hi. I offer classes for groups of 2-3 students. I teach competitive programming with a focus on problem-solving. There won't be many lectures because I can send you an article/video link instead. The lesson cycle is usually: I choose a problem, you say your thoughts and ideas, I comment on incorrect ideas, and we talk about the valid solution(s), possibly with drawings and pseudocode. In beginner groups, I might ask you to implement something, C++ or Python preferred.

There's a lot of homework and you're expected to practice a few hours per week. We might spend half a lesson talking about 1-2 homework problems from last week. This is intended.

We use Google Meet, shared whiteboard, and a collaborative editor Codebunk. After a lesson, you get a video recording and a codebunk with code/text history like this one https://codebunk.com/pb/3501100331621/. This allows you to copy links and code easily. There's a Discord group chat to ask questions between classes.

  • 1.5h lesson once per week.
  • Price per person: 66 USD per hour, 400 USD a month.
  • Payment: Paypal, wire transfer, Wise, Revolut. I can send you an invoice.
About me
Free lesson?
Why groups of size 2-3?
How to join?

I also offer:

Interview preparation
Corporate workshops

Full text and comments »

  • Vote: I like it
  • +132
  • Vote: I do not like it

By Errichto, 17 months ago, In English

For the next few days, I will do live streams of virtual participation (or casual problem-solving) of CF div1 rounds. The first one is starting in less than 2 hours. You can watch on Twitch and Youtube.

I'm back to practicing because there's a big Polish competition in two weeks and I'm certainly out of shape.

maybe around Wednesday: 1770G - Koxia and Bracket, 1774G - Segment Covering, 1787I - Treasure Hunt

See you in the Twitch chat.

Full text and comments »

  • Vote: I like it
  • +128
  • Vote: I do not like it

By Errichto, 23 months ago, In English

Hi. I'm organizing an online IOI-preparation camp in collaboration with Huawei. Every day will be a 5-hour virtual contest, then my problem analysis, and sometimes a lecture. There will be at least 4 contests and 2 lectures.

We will do some old IOI contests (2013?) from the IOI archive, CEOI (2015-2016?), or maybe JOI/JOISC — to be decided this weekend. I don't want to do recent years like 2021 because most participants already covered it. The example lecture topics are those from Range Queries or Trees in Usaco Guide Platinum.

The camp is free for IOI 2022 participants. For everybody else, the video recordings will be posted on Youtube after the camp. By participating you get the live experience (Discord, asking questions, competing with others, leaderboards).

Dates: 25.07-2.08 (updated)
Time of every analysis/lecture: 14:00 UTC / 16:00 CEST
Price: free for IOI participants, 40 USD for everybody else
Platform: Discord & Codeforces & uj.oz (?)

How to register?

Big thanks to Huawei UK R&D for sponsoring this camp.

EDIT: I'm now aware of CEOI collision. There's nothing I can do about it :(

Schedule:
25.07 — CEOI 2016 day 1
26.07 — CEOI 2022 day 1 + lecture
27.07 — CEOI 2016 day 2
28.07 — CEOI 2022 day 2
29.07 — lecture + homework
weekend off
1.08 — CEOI 2017 day 1
2.08 — CEOI 2017 day 2

Participants voted to cover CEOI instead of IOI to avoid problems that they already know.

Full text and comments »

  • Vote: I like it
  • +448
  • Vote: I do not like it

By Errichto, 2 years ago, In English

When some country organizes an ICPC or IOI preparation camp, they often need a teacher from abroad. When they ask me, I usually decline because of a lack of time. I want to be able to link this blog so they would find a good teacher.

If you teach and want to be reached by camp organizers, leave a comment and say something about your experience.

More info about such camps

Feel free to advertise your 1:1 online coaching too. It's not the main purpose of this blog though.

Full text and comments »

  • Vote: I like it
  • +210
  • Vote: I do not like it

By Errichto, 3 years ago, In English

Target audience: newbies and pupils (rating up to 1400).
Group link: https://mirror.codeforces.com/group/yg7WhsFsAp/contests (hit "join" on the right).

Hi. Enjoy a series of 8 problem lists for beginners. The example topics are strings, arrays, math, and binary search. You are allowed to discuss anything with others, or just look up solutions online. There are also 3 exams, each recommended for a 2-hour individual virtual participation. Use the displayed order, e.g. take exam 1 after day 3. It all should take you 2 weeks of intense bootcamp-like work (or a few months if you take your time).

The problems were originally used two years ago in a Saudi Arabia camp. It's a mix of around 70 existing CF problems and 30 new original problems, mainly prepared by kostka, with some help from me and mustafabar. I asked them for permission to publish everything.

I will put hints to some problems in this blog (or in the group? not sure). Expect a few videos and/or streams for beginners too. You should also read two first chapters of Competitive Programmer's Handbook.

UPD: On Sunday evening I'm making a stream with explanations to a few hard problems: P8, P11, P18, P30, P31, P33. You can try it with hints first:

P08. Cashier
P11. Queens attack!
P18. Mountain peaks
P30. Temporarily unavailable
P31. Shuffle Hashing
P31. Shuffle Hashing, hint 2
P33. Thanos Sort

Full text and comments »

  • Vote: I like it
  • +251
  • Vote: I do not like it

By Errichto, 3 years ago, In English

This is my 100th CF blog!

This is a list of techniques with $$$O(\sqrt n)$$$ time complexity. Watch the lecture https://youtu.be/BJhzd_VG61k, with timestamps!

  1. Square root decomposition — split the sequence into blocks of fixed size.
  2. Splitting objects (e.g. vertices) into light and heavy.
  3. Square root decomposition by the time of queries & rebuilding the structure.
  4. Mo's algorithm — processing queries in proper order and updating the answer by erasing/inserting new elements. https://cp-algorithms.com/data_structures/sqrt_decomposition.html
  5. Strings — if the sum of lengths is $$$S$$$ then there are at most $$$\sqrt{S}$$$ distinct lengths.
  6. Birthday paradox & baby-step giant-step. See P4 and P6 here, and see https://cp-algorithms.com/algebra/discrete-log.html.

P1. 398D - Instant Messanger
P2. 220B - Little Elephant and Array
P3. 86D - Powerful array (actually, skip this one because it's boring)
P4. Count triangles in a graph, i.e. cycles of size 3.
P5. Given $$$N$$$ strings with total length $$$S$$$, find a pair where one string is a substring of the other, in $$$O(S \cdot \sqrt S)$$$.

Homework (will be discussed in a second stream soon)
P6. You are given $$$N$$$ positive integers $$$a_1, a_2, \ldots, a_N$$$ and target value $$$X$$$. Check if there is subset with sum equal to $$$X$$$, in $$$O(X \cdot \sqrt S)$$$ where $$$S = \sum a_i$$$.
P7. 13E - Holes
P8. 455D - Serega and Fun
P9. You're given a sequence $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$). It describes a functional graph: there is a directed edge from $$$i$$$ to $$$a_i$$$. Handle updates U i x (change $$$a_i$$$ to $$$x$$$) and answer queries Q v — if we start in $$$v$$$ and keep following edges, after how many steps do we get to an already visited node?

And two problems from recent contests: 1580C - Train Maintenance and ABC 219 G Propagation.

Thanks to krismaz for letting me use his list of techniques and problems.

Full text and comments »

  • Vote: I like it
  • +463
  • Vote: I do not like it

By Errichto, 3 years ago, In English

Hello. Every week, I will discuss few nice recent problems from CF, AC, CC. I will alternate between div2 and div1 streams, with difficulties [1400, 1800] and ~[2200, 2800] respectively. Try to solve problems on your own before each stream!
You can suggest new cool/interesting/educational problems in comments below this blog.

2.10.2021, Div2 Problems of the Week https://youtu.be/AbeEJvmsx0E

  1. [1800] 1572A - Book
  2. [1600] 1567C - Carrying Conundrum
  3. [1800] 1556C - Compressed Bracket Sequence + O(N) solution

honorable mentions
- [1700] 1579E2 - Array Optimization by Deque
- [1800?] Cross-free Matching https://atcoder.jp/contests/arc126/tasks/arc126_b

9.10.2021, Div1 Problems of the Week https://youtu.be/7rtZEXAVzmk

  1. [2400] 1592E - Bored Bakry
  2. [2700] 1572C - Paint
  3. [3000] 1572E - Polygon

Full text and comments »

  • Vote: I like it
  • +329
  • Vote: I do not like it

By Errichto, 3 years ago, In English

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://mirror.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://mirror.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.

Full text and comments »

  • Vote: I like it
  • +242
  • Vote: I do not like it

By Errichto, 3 years ago, In English

Hi. I think these are nice medium-hard interactive problems. I will discuss solutions in a stream today at https://www.twitch.tv/errichto.

UPD, recording is here https://youtu.be/9oEihYrAR5kUPD and I added text solutions in this blog.

P1. Mostly A — You're given two integers $$$N$$$ and $$$K$$$ ($$$N \leq 50\,000$$$, $$$K \leq 10$$$). You need to find a hidden string of length $$$N$$$ with lowercase English characters a-z. At most $$$K$$$ characters are different than 'a'. You can choose your own string of length $$$N$$$ and you will get info YES/NO whether your string is lexicographically smaller than the hidden one. There is no explicit limit on the number of queries. There's still some time limit (say, 2 seconds).
Hard version: Minimize the number of queries.

slow solution
hint
solution
hard version (optimal number of queries)

P2. Cloyster (https://mirror.codeforces.com/gym/102341/problem/C) — There's a grid $$$N \times N$$$ ($$$N \leq 2000$$$), each cell with some value. You can ask at most $$$3 \cdot n + 210$$$ queries "get value at cell (i, j)". Find the cell with the maximum value. For each of other $$$N^2 - 1$$$ cells, it's guaranteed that at least one adjacent cell has a greater value. Two cells are adjacent if they share a side or a corner.

hint

P3. Moving Car — A car on an infinite line starts at unknown position $$$X$$$ and unknown constant speed $$$V$$$ ($$$1 \leq X, V \leq 1000$$$). After $$$i$$$ seconds, it will be at $$$X + i \cdot V$$$. At time $$$0$$$ and then after every second, you get to ask about some position and you get a response whether the car is on the left, on the right, or at this position. Use at most 1000 queries to find values $$$X$$$ and $$$V$$$.
Hard version: $$$1 \leq X, V \leq 10^5$$$

hint
solution
cool improvement
hard version

If you know the source of problems 1 or 3, please let me know.

Full text and comments »

  • Vote: I like it
  • +235
  • Vote: I do not like it

By Errichto, 3 years ago, In English

In a few hours, I will talk with guests about the upcoming IOI 2021. I will be joined (at least for 10-15 minutes each) by tmwilliamlin168, Petr, kostka and hopefully more.

We might talk winner predictions, stories, tips, training style in various countries. Feel free to post suggestions under this blog too.

See you at https://www.twitch.tv/errichto

UPD, recording: https://youtu.be/XNvcYFvFBls
Thanks to eduardische and jonathanirvings for joining the second part, when we discussed IOI from the organizers's point of view.

Full text and comments »

  • Vote: I like it
  • +116
  • Vote: I do not like it

By Errichto, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +76
  • Vote: I do not like it

By Errichto, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +124
  • Vote: I do not like it

By Errichto, 4 years ago, In English

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!

Full text and comments »

Tags ioi
  • Vote: I like it
  • +466
  • Vote: I do not like it

By Errichto, 4 years ago, In English

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, mesanu, the_white_devil, SlavicG, gupta_samarth, lior5654. 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.

Full text and comments »

  • Vote: I like it
  • +200
  • Vote: I do not like it

By Errichto, 4 years ago, In English

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

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

Full text and comments »

  • Vote: I like it
  • +63
  • Vote: I do not like it

By Errichto, 4 years ago, In English

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.

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

Full text and comments »

  • Vote: I like it
  • +167
  • Vote: I do not like it

By Errichto, 4 years ago, In English

Hi. I invite you to AtCoder Grand Contest 047.

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.

Full text and comments »

  • Vote: I like it
  • +636
  • Vote: I do not like it

By Errichto, 4 years ago, In English

tl;dr — video tutorial https://www.youtube.com/watch?v=eMXNWcbw75E and codeforces GYM training https://mirror.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://mirror.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

C. Fibonacci
D. Count Paths
E. Knight Paths
F. Min Path
G. Recurrence With Square
H. String Mood Updates
I. Count Paths Qeuries

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.

dp in O(1) space

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.

drawing 1

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.

drawing 2

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)$$$.

full C++ solution

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.

Full text and comments »

  • Vote: I like it
  • +606
  • Vote: I do not like it

By Errichto, 4 years ago, In English

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 :)

Full text and comments »

  • Vote: I like it
  • +437
  • Vote: I do not like it

By Errichto, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +706
  • Vote: I do not like it

By Errichto, 4 years ago, In English

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.

(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 UPDATEJune 20, 19:00 CEST solving random problems suggested by viewers

Full text and comments »

  • Vote: I like it
  • +168
  • Vote: I do not like it

By Errichto, 4 years ago, In English

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)

Full text and comments »

  • Vote: I like it
  • +262
  • Vote: I do not like it