Home » Sports programming

I like sports programming: time-constrained contests comprised of algorithmic puzzles.

My profiles on some well-known sports programming websites: Codeforces, AtCoder, Topcoder.

Achievements

• I participated in ICPC World Finals twice, together with Wojciech Nadara and Marcin Smulewicz.
  5th place (silver medal) in 2016 (Phuket, Thailand)
  2nd place (gold medal) in 2017 (Rapid City, USA)
• I have the rank of Legendary Grandmaster on Codeforces [profile] and (at the moment of writing this) top10 highest ranking on AtCoder [profile].
• I was a finalist of:
  • Google Code Jam [link], three times: 2016 (New York, 6th place), 2019 (San Francisco, 4th place), 2022 (online, 5th place).
    I also was a Distributed Code Jam finalist in 2016.
  • Facebook Hacker Cup [link], three times: 2015 (Menlo Park, 21st place), 2021 (online, 10th place), 2022 (online, 3rd place).
  • TopCoder Open Algorithm in 2019 (Houston, 3rd place).
• Slightly off-topic: I won a bronze medal in the International Mathematical Olympiad in 2013 (Santa Marta, Colombia).

Coaching

In the previous years, I used to coach the teams from the University of Warsaw and prepare them for team programming competitions (ICPC-style, like AMPPZ, CERC, ICPC World Finals).

Our current ICPC trainings website: [ link]

Teaching and organization

• Algorithmic Engagements (Potyczki Algorytmiczne)
  contest website: [link]
  Jury lead in 2017, Jury member in 2019, 2020, 2021
• Polish Olympiad in Informatics (Olimpiada Informatyczna)
  contest website: [link]
  Jury member since 2014
  Task committee member since 2022
• Polish Olympiad in Informatics camp (ONTAK)
  Jury member in 2015 [problems], 2016 [problems]

Selection of my problems

Hike (Algorithmic Engagements 2020)

Submit here: [link]

Statement: A group of people decided to hike in the Grid Mountains. The map of Grid Mountains is – well – an n × m grid with some cells passable and the others impassable. The top left and the bottom right corners of the map are both passable.

A total of k hikers decided to scale the Grid Mountains today. Each hiker starts their hike in the top left cell of the map and finishes in the bottom right cell, without ever entering an impassable cell. For each hiker, you know two numbers: a – the number of seconds the hiker takes to move to the cell neighboring their current cell from the right or the bottom, and b – the number of seconds the hiker takes to move to the cell up or to the cell left. Determine, for each hiker, how quickly they can finish the hike if they choose an optimal route.

Limits: n, m ≤ 2000, k ≤ 1 000 000.

Bytemon Collector (Polish Olympiad in Informatics 2014/2015, 3rd stage)

Submit here: [link]

Statement: You are given a long stream of integers. You can read the stream integer by integer, but you have insufficient working memory to store the entire stream. Also, a priori you do not know the length of the stream; you only know the stream has ended when you attempt to read past the end of it.

It is guaranteed that all distinct numbers appear in the stream the same number of times, apart from one number that appears less frequently. Find that less frequent number. For example, if the stream comprises the numbers: [13, 40, 26, 26, 13], then all numbers appear twice in the stream – apart from 40 that appears less frequently. The result is 40.

Limits: The stream has at most 60 000 000 numbers, each a positive 32-bit integer. You have 8 MB of memory available to your program (including all the runtime libraries). In order to get full marks, you must read the stream exactly once. Partial score is available if you read the stream twice.

Mosaic (Algorithmic Engagements 2017)

Submit here: [link]

Statement: A two-dimensional, integer-sided axis-aligned rectangle is tiled with n integer-sided axis-aligned squares. However, as input you are only given the lower-left corners of these squares (so the shape of the original rectangle is not on input). Recover the tiling from only this information (actually, find any tiling consistent with the input).

Limits: n ≤ 2000.

Social Media (Polish Olympiad in Informatics 2022/2023, 3rd stage)

Submit here: [link]

Statement: Consider a social media network with n users. Some pairs of users are in a mutual relation of friendship.

The Algorithm™ wants to increase the engagement in the social network about some Hot Topic. By serving carefully chosen ads, The Algorithm™ can convince every user on the platform to any opinion on the topic. A person's opinion on the Hot Topic should be an integer from 1 (absolutely loathing the Hot Topic) to k (massively loving the topic). The Algorithm™ wants to assign opinions to the people so that:

• Every person sees that their friends have similar, but slightly different opinions on the topic. Formally, for each pair of friends, their opinions on the topic should differ by exactly 1.
• The number of people with extreme opinions on the topic (1 and k) is maximum possible.

What is the maximum possible number of people with extreme opinions? Reconstruct one optimum solution.

Limits: 3 ≤ k ≤ n ≤ 200. Partial score for k = 3 and for k = 4.

Probe (Algorithmic Engagements 2019)

Submit here: [link]

Statement: A probe wants to examine all n nodes of an unknown connected undirected simple graph. The nodes have identifiers from 1 to n; at the very beginning, the probe is at node 1. The probe can explore the graph by issuing the MoveProbe command, and examine the current node by issuing the Examine command. However, the probe's firmware was sloppily implemented, so these commands behave as follows:

• MoveProbe(v): attempts to move the probe to node v. If the probe currently is at node v, the probe gets confused and explodes (and you lose). If there is no connection between the current node and v, the probe stays in place and returns 0. On the other hand, if there is such a connection, the probe moves over to node v. If it is an even successful move (the second, fourth, ..., successful move) of the probe, the probe returns 1. Otherwise, the probe returns 0. (So the answer 0 means that either the move was unsuccessful, or it was successful but it was an odd such move.)
• Examine(): causes probe to examine the current location of the probe. Each node of the graph must be examined exactly once.

Limits: 3 ≤ n ≤ 400. You can execute MoveProbe at most 1 000 000 times (regardless of whether the calls were successful).

The Bold and the Beautiful (Olympiad in Informatics Summer Camp 2016)

Submit here: [link]

Statement: In a long-running soap opera, there are n male characters and n female characters, each assigned an identifier from 1 to n. Initially, the i-th male is in a relationship with the i-th female, for each i from 1 to n.

After each episode of the show, the identifiers are shuffled: the male with identifier i now gets identifier p_i, and the female with identifier i now gets identifier q_i. All numbers p_i are distinct integers from 1 to n, analogously for q_i. After the identifier reassignment, the relationships are reformed so that the male with (the new) identifier i is together with the female with (the new) identifier i.

The current run of the show will only finish when the relationships return to their original assignments all at once. How many episodes will this take? This number is large, so please print it modulo 10⁹ + 7.

Example: If n = 6, p = (2, 3, 4, 5, 6, 1) and q = (6, 1, 2, 3, 4, 5), then after three episodes, each male will be in a relationship with their original partner (even though they both may have different identifiers now).

Limits: n ≤ 1 000 000 (partial credits for smaller values of n).

Nim With a Twist (Polish Olympiad in Informatics 2015/2016, 1st stage)

Submit here: [link]

Statement: Recall the mathematical game of Nim, in which we play with a number of heaps, each containing some stones. Two players – Alice and Bob – play the game. In one move, a player chooses a nonempty heap and removes one or more stones from it. Players move alternately, starting with Alice. Whoever cannot make a move loses (equivalently, removing the last stone from the game yields a win). Determine the winner of the game if Alice and Bob play perfectly.

However, we consider a variant of the problem with a twist: before the play starts, Bob may choose to remove some heaps in their entirety from the game. He cannot remove all the heaps, and the number of heaps he removes must be divisible by some number d (1 ≤ d ≤ 10) given on input; however, he can choose not to remove any heaps. In how many distinct ways can Bob remove some heaps so that he can ensure he wins? The answer might be large, so report the remainder of the division of that number by 10⁹ + 7.

Limits: At most 500 000 heaps, each containing at most 1 000 000 stones; but the heaps contain at most 10 000 000 stones in total. Also 1 ≤ d ≤ 10. Your working memory size is 64 MB (or 256 MB for partial score).