Errichto's blog

By Errichto, 10 days ago, In English,

I want to go to Joker's Asylum ER in San Jose (California) on the 7th of August, two days before GCJ finals. It's a difficult escape room and a team should consist of 5-10 people. So far, there's me and my friend — not really pros. I'm looking for more people to go there and maybe grab a beer later. If the date is fine for you and you are good at ER and/or algo, write a DM to me.

This room has very good reviews and the escape room veteran Swistakk recommends it a lot. Sounds promising, right?

Read more »

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

By Errichto, 6 weeks ago, In English,

I recorded a 30-minute lecture about binary search. It should allow you to really understand it and stop guessing about +1 in random places. Enjoy.

https://www.youtube.com/watch?v=GU7DpgHINWQ

Consider watching with captions on and with x1.25 speed.

Read more »

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

By Errichto, 2 months ago, In English,

Which one should we use?

Competitive Programming is used more often but it has stupid abbreviation (Cerebral Palsy and Child Pornography). Some Youtube accounts about Pokemon Go were actually banned for using that because of Combat Points. Here you can read things like "My Club Penguin video had been flagged for sexual content". This also means it isn't cool to write "I'm addicted to CP" in any social media. Urban Dictionary says that SP means Sex Party, but I don't think it's common and at least it isn't something shameful/harmful.

I think the Polish term is "programowanie sportowe" (sports programming) but sometimes we just say English words "competitive programming". The Russian say "Спортивное программирование" (sports programming), in Portuguese it is "Maratona de Programação" (programming marathon). What do you say in your language? In particular, I would like to hear native speakers to state their opinion.

And Sports Programming is arguably cooler.

I'm asking because I want to make videos like "What is Competitive Programming?" and "How to start with ...", "TOP FIVE BEST COMPETITIVE PROGRAMMING PLATFORMS OF 2019, YOU WON'T BELIEVE NUMBER 4" etc. If we prefer Sports Programming, I will use it instead.

EDIT: A huge argument for CP is ofc. that we use it like 99% of time. There are some single occurrences of SP, e.g. "The ICPC is the world’s premiere university sports programming competition" on the ICPC 2019 website, but it's a minority.

Read more »

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

By Errichto, 2 months ago, In English,

Hi.

Even more streams are coming. For notifications, subscribe to my secondary channel for streams Errichto 2, or you can watch me on Twitch.

Stream 1 — Monday at 12:00 CEST, I want to check out coding interview platforms like Leetcode. Here's Youtube link.

Stream 2 — Tuesday at 9:00 CEST. Algo research and writing old editorials. Links to part 1 and part 2 (the stream stopped for a few seconds and the new one started).

Stream 3 — Friday at 12:00 CEST. Solving Codeforces problems, mainly around div1D div2D (sorry, a typo). In particular, I will solve rounds #560, #561 and Edu #65. Links to part 1 and part 2. Again, the stream stopped for a moment and YT splitted it into two.

See ya.


Same plan next week:

Stream 4 — Monday, 27th of May, at 12:00 CEST. Boring stream with planning my future blogs and Youtube videos. Link.

Stream 5 — Tuesday at 9:00 CEST. Coding interview platforms again. Link

Stream 6 — Friday at 12:00 CEST. Some old POI problems. I will choose something and update the post so you could read problems and think about them in advance. Data structures for coding interviews like linked lists. (After an update, Linux stopped working on my PC, so no coding stream.) Link

Read more »

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

By Errichto, 2 months ago, In English,

Hi.

I will make two streams this week. Both will be on my YT channel Errichto 2 and on Twitch. My streams will usually be on that second YT channel, while my main channel is for short educational videos, also outside of competitive programming.

Stream 1 — Thursday at 9am, virtual participation of PSUT Coding Marathon 2019 with commentary, just like Atcoder DP stream. The contest is in GYM (link). The original announcement by 2-SAD is here.

Stream 2 — Friday at 2pm, boring programming stream: maintaining and planning my YT channel, checking out blogs, checking out new game on Codingame (it will start too late), finishing problems from PSUT stream.

See ya.

Read more »

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

By Errichto, 3 months ago, In English,

Google Code Jam round 1A starts in less than 3 hours. https://codingcompetitions.withgoogle.com/codejam

In each of rounds 1A, 1B, 1C, top 1500 participants will advance to round 2 (4500 in total).

I'm not going to participate (because it's the middle of a night for me), but a reminder might help other people.

Read more »

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

By Errichto, 4 months ago, In English,

I will stream tomorrow starting at 9:00 CEST on Twitch, https://www.twitch.tv/errichto. If you miss it, the video will be available for 14 days after that (it's a default value in Twitch).

I'm going to keep boring streams on Twitch. Lectures and short videos will be on Youtube. And I'm thinking about fixing some schedule, we'll see about that.

Read more »

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

By Errichto, 4 months ago, In English,

Hi.

On Wednesday at 9:05 CET / 8:05 UCT you can participate in the GYM version of the finals of 2017-2018 Russian Olympiad in Informatics (ROI), Day 1. And on Thursday there will be day 2, same time.

Links to GYM contets: day1 and day2.

5 hours, 4 problems, IOI-style scoring with subtasks. Statements will be available in three languages: English, Russian, Polish.

We wanted to use those problems in a camp in Warsaw so we had to import the problems to some system anyway. Then why not Polygon+Codeforces and thus allowing everybody to participate? Huge thanks to MikeMirzayanov for helping me with using GYM.

And credits to problem authors: Andreikkaa for Radium, Endagorion for Viruses, pashka for Innophone, Георгий Корнеев and GlebsHP for Quantum Teleportation.

Second day authors: _kun_ for Decryption, "jury" for Quick Sort, GlebsHP for Robomarathon, Endagorion for Addition without carry.

I will post a very short editorial in English here, after the contest.

Extraction of radium
Innophone
Quantum teleportation
Viruses

Second day tomorrow, same time.

Thank you for participation.

Addition without carry
Decryption
Quick sort
Robomarathon

Read more »

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

By Errichto, 4 months ago, In English,

There was a blog that chemthan got hacked, and indeed I got strange messages from his account, asking for help with problems from the next Google Kickstart. The blog is now deleted. It would be nice to hear from some friends of his whether everything is ok now. chemthan1 is allegedly his temporary alt account. Also, ikatanic was mentioned.

I can remove this blog a few days after everything is resolved, if chemthan wishes so.

Read more »

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

By Errichto, 4 months ago, In English,

Hi!

This Tuesday, instead of Boring Programming Stream I will participate virtually in CF Global Round 1. Start at 12:00 CET. After that, I might upsolve some other problems too. Watch me live on Youtube or Twitch.

Cheers.

Read more »

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

By Errichto, 4 months ago, In English,

Hi.

https://www.codingame.com/ regularly holds 10-day long competitions where you should write a program that plays a 2-player game. Sometimes you must move units/soldiers in a grid, sometimes it's a card game. The next game starts tomorrow (Friday) and then we'll see what's the topic (well, it must be food related).

I'm going to stream my approach from scratch on Youtube and Twitch. Start on Friday at 9pm CET (3pm EST). Btw. I streamed the previous game three months ago, link.

No prerequisites needed. I will explain my thoughts and give general advice for this type of contests. Feel free to ask questions in chat.

See you!

Read more »

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

By Errichto, history, 5 months ago, In English,

The qualification round starts in 50 minutes. Let's share scores and discuss the problem after the contest. Useful links below.

Judge System
Official livestream
FAQ

Good luck!

Read more »

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

By Errichto, 5 months ago, In English,

EDIT: BPS #5 will be yet again on Tuesday, 10:00-16:00 CET (Youtube link or Twitch). I will mainly continue researching good tutorials about topics like segment trees, bfs, combinatorics. Maybe I will read some part of Competitive Programmer's Handbook.

Hi. The Boring Programming Stream #4 will be again on Tuesday, 10:00-16:00 CET (Youtube link or Twitch).

This time I will work on Linux and I can do some coding instead of writing editorials. So, more "programming" and less "boring", I hope. Some of the things I might do are:

  • Finding good tutorials about Gaussian elimination.
  • Researching good tutorials about other topics too, e.g. to know what to recommend for segment trees, knapsack, etc.
  • Practicing Burnside's Lemma.
  • Upsolving 1109C - Sasha and a Patient Friend and other problems (virtual participation maybe?).
  • Reading IOI syllabus.
  • Planning the next lecture (or Facebook posts).
  • Answering people's questions and comments, also from Codeforces blogs.

See you!

My Youtube channel: https://www.youtube.com/errichto.
I will stream on Twitch at the same time: https://www.twitch.tv/errichto.
Follow me on Facebook, Twitter and Discord.

Read more »

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

By Errichto, 5 months ago, In English,

Sadly, after spending a few hours learning about quantum programming, I decided to cancel the stream. Maybe I would be able to solve some problems in the warm-up round, but certainly, I don't have enough knowledge to make a stream about it, and I'm afraid I would say something incorrect multiple times and thus cause damage to viewers. I'm extremely sorry for that.

Instead, I will talk about the Google Hash Code competition. I competed last year with a success. Our team won the qualification round and we were 6-th in the final round (I hope I remember that correctly because I can't find the standings). I'm going to go through the problems from that 2018 edition, talk about my codes, and I will give general advice for the contest. If you want to participate this year, you must hurry — the registration closes tomorrow (on Monday)! Registration link.

The stream starts at 12:00 CET.

My next stream is this Sunday at 12:00 CET, and I will try to solve problems from the ongoing warm-up of Q# Coding Contest by Microsoft's Quantum team. Read more details about that contest in the announcement.

I'm very excited about this because it will be something unusual, just like distributed algorithms that were new and amazing for me. mareksom competed in the first edition and he said it's very cool. If it turns out boring, let's blame him.

PS. I have no idea what quantum programming is, but I watched Ant-man and Ant-man 2. I hope this is enough. (yeah...)

You can watch me on Youtube or Twitch.

Read more »

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

By Errichto, 5 months ago, In English,

Hi. The next Boring Programming Stream will be on Tuesday, 12:00-16:00 CET (youtube link with countdown or Twitch) and some of the things I might do are:

  • Rearranging videos on my channel.
  • Answering comments under videos.
  • Writing editorials for my old problems.
  • Learning Burnside's lemma.
  • Upsolving 1109C - Sasha and a Patient Friend.
  • Reading IOI syllabus.
  • Adding timestamps to my lectures on Youtube.
  • Planning the next lecture (or Facebook posts).
  • Choosing graphics (banner and thumbnails) for my channel.
  • Answering people's questions and comments, also from Codeforces blogs.

See you!

My Youtube channel: https://www.youtube.com/errichto.
I will stream on Twitch at the same time: https://www.twitch.tv/errichto.
Follow me on Facebook, Twitter and Discord.

Read more »

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

By Errichto, 5 months ago, In English,

Hi.

On Sunday, I'm going to solve problems from the Educational Dynamic Programming contest on AtCoder — https://atcoder.jp/contests/dp. Start at 10:00 CET (check your timezone), expected duration 5 hours. Watch me on YT or Twitch: https://www.youtube.com/errichto, https://www.twitch.tv/errichto.

There will be 26 problems, all on dynamic programming. More info here.

See you tomorrow!

Read more »

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

By Errichto, 6 months ago, In English,

What to do when you need help with a problem?

  1. If there is an editorial, read it. If you don't know some technique, google it and read a tutorial.
  2. Ask a friend for help. It's very useful to find someone in your university/country who also does competitive programming.
  3. "I'm getting WA and don't know why."
    Try to find a counter-test. Take an accepted code if it's available, and write a brute force otherwise. Test it against your solution on thousands of random tests, especially small ones.
  4. "My code doesn't work on this test."
    Use some debugging tools (google them for your OS/IDE) or just print values of everything you compute. I use gdb and valgrind. Simulate the program on paper too. This way you should find an exact place where something incorrect happens, or you will see that your approach is completely wrong.
  5. "The output differs on my machine and in Codeforces/anotherPlatform."
    It's likely "undefined behavior", e.g. you don't initialize a local variable or you don't return anything from a non-void function. It doesn't happen often if you know the language well. Avoid non-integer values if possible, because real values involve the precision error. Try running your program in a few places online like ideone.com or Codeforces custom invocation. Don't use ideone during a contest or somebody will see your code and you will be disqualified! If it's C++, use compilations flags that catch more errors. I use g++ -std=c++17 -Wshadow -Wall -o a a.cpp -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -g. It increases the running time though, so compile in a different way if you need the speed.

General advice:

  1. Practice by solving problems with editorials, especially if you don't know people doing CP, e.g. in your university.
  2. Solve problems slightly above your level, not something extremely hard. If the solution/editorial is overwhelming, maybe get back to this problem in a few months.

Still want to ask for help?

  1. If you think your question is small and easy to answer, consider asking in the discord channel, link.
  2. Write a blog instead of asking some random red guy in priv. This way more people can see it and more people can read the answer and learn something.
  3. Provide a source of your problem.
    If there is no link and a person is not well known in the community, I'm assuming it's from an ongoing contest or it's your homework. I think such blogs should be answered too, but not immediately.
  4. Describe what you already came up with.
  5. If you have some code, use meaningful variable names and put comments. If you know which part doesn't work, mention it.
  6. Either put the code in "block" and "spoiler" tags (you can see them next to bolding and enumeration), or give a link to a submission or an upload in pastebin/ideone/etc.
  7. Use proper English. Full words, dots to finish sentences, uppercase to start them. Use a browser that checks your spelling in English.
  8. You can read more here.

Also:

"Can I ask a question?"

This happens often in priv. Just ask your question instead of wasting my time. Also, http://www.nohello.com/.

Using "bro/sir"

Don't use that. See how others write in Codeforces or any other international forum.

"Why is my blog downvoted?"

You shouldn't care about it. Codeforces votes are strange and random sometimes. Still, use your main account. I prefer answering people that use Codeforces and have some non-empty contest history.

"How to train, get better, etc.?"

Google your question. There were plenty of those in Codeforces and Quora. If you don't want to do that, just read this.

What should I add here? Suggestions in comments or priv, please. And when you see a badly asked question or somebody bothers you in priv, feel free to link to this blog.

Read more »

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

By Errichto, 6 months ago, In English,

I got a private message in Codeforces:

"hey u r on cf and toc both . how r problems at toc div1 for gcj and fb hc ? for practicing."

I told the guy to use full words and to start the beginning of a sentence with uppercase, so it would be easier to understand him. And he indeed sent me a version that is easy to read!

"ok ! Hey , you use both codeforces and topcoder ! I wanna know How are problems at topcoder division 1 for practicing for google code jam and facebook hacker cup !
Which is the best Platform for it !"

So much better! Remove an unnecessary space character before punctuation marks (dots, exclamation marks, etc.) and you have proper grammar and everything. I also recommend using uppercase for abbreviations like CF, TC, FHC, GCJ. My English isn't perfect either, but I'm learning. And I use Grammarly (a free add-on with optional premium) that finds a lot of errors, typos, and missing commas. For example, I've just written "grammarly" and it suggested correcting it to "Grammarly". Fair enough. Btw. my answer was: Topcoder and Atcoder for GCJ, Codeforces and Codechef for FHC.

Anyway, what did make you proud of Codeforces recently? Did you see some post that asked for help with a problem and wasn't downvoted into oblivion? Or maybe somebody wanted to share their private videos for free? Share your stories!

Read more »

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

By Errichto, 6 months ago, In English,

Hi.

Thanks to kostka, this weekend you can participate virtually in an old edition of Polish olympiad: POI XVIII, stage 2. There are two days of a contest, Saturday and Sunday, 9-14 CET (check your timezone here). An hour after the contest ends on Sunday (so, 15 CET), I will talk about problems from both days in a stream. You can watch me on Youtube and Twitch.

Create an account in Szkopul first, link. The statements will be both in Polish and English, or the link to the English version will be provided as an announcement.

If you can't participate, I still recommend you to read the problems and try to solve them yourself before my stream.

Read more »

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

By Errichto, 6 months ago, In English,

Hi. I'm finally done with organizing Algorithmic Engagements, and I have time to go back to my streams!

Other Twitch programming streamers usually just do their job/project and they stream that. I'm going to do a similar thing. So, apart from my lectures and problem-solving streams, I will do a weekly longer stream, maybe around 6 hours.

My first Boring Programming Stream will be on Wednesday Tuesday (10am to 4pm CET, youtube link with countdown) and some of the things I might do are:

  • Writing editorials for my old problems.
  • Adding timestamps to my lectures on Youtube.
  • Planning the next lecture (or Facebook posts).
  • Reading the "Segment tree beats" blog (I know that tree, but I've never read examples and tasks given there).
  • Learning how to edit videos.
  • Reading Codeforces comments and maybe helping someone with a problem.
  • Learning how to use OneNote for drawing.
  • Choosing graphics (banner and thumbnails) for my channel.
  • Answering people's questions and comments.

This is something that I would do anyway, and it isn't confidential (unlike preparing problems), so I can stream it and allow people to hang out with me. Feel free to suggest something via discord or in the comments below this blog, but please notice that I will mainly do things that I need/want to do.

Cheers.

My Youtube channel: https://www.youtube.com/errichto.
I will stream on Twitch at the same time: https://www.twitch.tv/errichto.
Competitive Programming Discord: https://discordapp.com/invite/UzaURu7.

Read more »

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

By Errichto, history, 7 months ago, In English,

Wednesday evening (check your time zone) I will stream solving an AI bot problem on Codingame, https://www.codingame.com/ide/challenge/xmas-rush. As usually, I will talk a lot about what I'm doing. The goal is to show you how to approach this kind of problems.

Link to the stream on Youtube (and currently just the countdown): link.

If you want to chat with me before or after the stream, visit the Competitive Programming discord, link.

Read more »

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

By Errichto, 8 months ago, In English,

Hi. I'm back from USA!

I will do a new lecture tomorrow (Thursday) at 2pm CEST on my Youtube channel: https://www.youtube.com/watch?v=7hFWrKa6yRM. Watch me live (and ask questions), or just watch the video later. This will be part 1, and I will do part 2 in a few days (maybe Tuesday).

UPDATE — part 2 is coming on Thursday, same time. Link: https://www.youtube.com/watch?v=gXxu-Cr4b4c.

There are no prerequisites this time. I recommend reading the materials below in advance, and trying to solve problems 1 and 5. If you are strong, just read problems and see if you can't solve something (maybe problem 8?).

Technique "Exchange Arguments"

If we're given n items and we should choose some of them and choose their order, we should sort them with some strange/tricky comparator, and then do O(N2) dynamic programming. The dp should be dp[pref][used] — best possible result (balance) if we chose used items so far (in the prefix pref).

"Strange/tricky comparator" checks which of the two elements should be earlier, usually just solving the problem for N = 2.

Read more »

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

By Errichto, 9 months ago, In English,

Instruction

I recommend this blog also for red users. Read the theory and problems below, try to solve them. For solutions and extra insight/tips, watch my stream on Monday or watch the video later. If you aren't familiar with EV or summing problems, see part 1 first: http://codeforces.com/blog/entry/62690.

I will stream a lecture on Monday at 14:00 CESThttps://www.youtube.com/watch?v=HDk6zQw0Rdo (also Twitch). I will go through theory and problems from this blog.

Expected Value theory, part 2

We roll a 6-sided die. Remember, EV of square of the number of pips is something different than square of EV:

Two events are independent if the result of one doesn't affect the distribution of p-bilities of the other. Results of throwing two dice (or throwing one die twice) are independent, but the amount of rain and the strength of wind are dependent.

Read more »

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

By Errichto, 9 months ago, In English,

Watch my lecture-stream tomorrow (Thursday) at 14:00 CESThttps://www.youtube.com/watch?v=qdlPY37MBPo https://www.youtube.com/watch?v=U_h3IjreRek. I will go through theory and problems from this blog. The only prerequisite is knowing what is probability. The next (harder) part on Monday.

The video will be available later, with timestamps for each problem — so you don't have to watch everything.

Definition of EV

Let's say we bought a lottery ticket for 2$. We will win 10$ with probability 10%, and 20$ with p-bility 2%. On average, it gives us 0.1·10 + 0.02·20 = 1.4, so we are worse off after buying the ticket. The computed average is called the expected value.

The expected value (EV, expectation) is the average value of an event/experiment. For example, EV of the number of pips rolled on a 6-sided die is 3.5:

Linearity of EV (super important theorem):

Read more »

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

By Errichto, 9 months ago, In English,

If you use Facebook, you might want to check out my new page https://www.facebook.com/errichto. I will post some short problems, puzzles I know/heard (maybe also not-algo puzzles, who knows), mention upcoming contests or cool problems from recent ones, sometimes share my thoughts about an algorithm or a contest. Kind of a blog, but likely with shorter but more frequent posts. Cheers!

PS. next Competitive Programming stream will be on Monday, div2 C-D problems from recent CF rounds, 12pm CEST.

Read more »

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