0%

Patricia: I hate my life.
Looksmart: I hate Patricia.
Patricia: Why? I taught you how to fish.
Looksmart: You forced me to kill the fish.
Patricia: No.
Looksmart: Yes.
Patricia: Ok maybe yes, but who cares?
Looksmart: I do and also you killed my girlfriend.
Patricia: No.
Looksmart: Yes.
Patricia: Ok maybe yes, but how?

I’m mainly writing this post because there isn’t any (good) editorial for APIO 2013 Robots online. In my opinion, it’s an okay problem, but it’s not particularly interesting.

I’m not going to go over the problem statement because it’s very long and complicated, so I’ll just trust that you’ve already read the problem.

I’ve always found game theory (especially Nim games) fascinating. That’s why I’d like to share a beautiful game theory problem from the 2016 Polish Olympiad in Informatics with you today.

You can find the problem here (the statement is pretty short).

The gist is that you’re given the initial configuration of a classical Nim game with $N \leq 5 \cdot 10^5$ piles and you want to count the number of subsets of piles you can remove so that player 2 can guarantee a win and the number of piles you remove is divisible by $d \leq 10$.

You’re also given that $a_i \leq 10^6$ ($a_i$ is the number of stones in pile $i$) and $\sum a_i \leq 10^7$.

To make it even more challenging, the memory limit is just 64mb.

I’ve recently made 2 Discord bots. PO(I)TD is a bot that sends a daily Olympiad Informatics (OI) problem and Git the lines is a bot that prints out GitHub/GitLab snippets.

Both bots are open-source and you can see their code on GitHub

This post is basically a transcription of my YouTube video explaining Burnside’s lemma. Please consider watching and liking that video as well.

Today, I’d like to share yet another really cool (but also really trippy) programming problem. This problem is Timeismoney from the 2011 Balkan Olympiad in Informatics.

Here’s the gist of the problem:

You’re given a graph where each edge has 2 costs $t_i$ and $c_i$. Find a spanning tree such that $\sum t_i \cdot \sum c_i$ is minimised.

Firstly, if $t_i = c_i$ for each $i$, this is just a normal minimum spanning tree problem that we can solve with Kruskal’s algorithm. However, this is far from the full solution.

When I say this problem is trippy, I mean it.

Afrikaans is a great language. It’s super easy to learn (There are no conjugations and there are only 3 tenses). It sounds great (unless the person speaking it has an Eastern Cape accent). But the thing I like most about it is its vocabulary of funny and creative words that I sometimes wish are in the English language as well.

Here is a list of words I find funny, creative, or anywhere in between.

Update: Ready my explanation of my solution at https://codeforces.com/blog/entry/75726

I finally solved Reverse from IOI 2003! Here’s a brief summary of what the problem is about:

You have an ancient computer that has 9 registers and 2 operations. Each register can hold an integer from 0 to 255. An S operation in the form S A B sets register[B] = register[A] + 1. A P operation in the form P A simply prints register[B]. You may choose the 9 starting values of the registers.

Your task is, for a given N, print out N, N - 1, …, 0 using as few consecutive S operations as possible.

Recently, I’ve come across some unusual types of graphs while solving problems. These graphs often had funny and/or cool names that I thought described what they look like quite well.

Today, I’ll share some of these graphs with you (along with some illustrations). If you feel like there are some other cool graphs I should add to this list, please comment them down below.