Hello Codeforces,

It's been a while since my last activity / contest participation on here! I've largely moved on from competitive programming to machine learning, but still tried to keep up with the vibrant community of sport programmers whenever possible.

Recently I've decided to orient my focus in ways in which we can combine the representational power of neural networks (great for handling big, noisy, "real-world" data) with the incredible robustness of algorithms (provably correct, trivially generalisable across problem instances, compositionality w.r.t. subroutines and functions). One way forward is teaching neural nets the execution steps of algorithms -- i.e. replicating the intermediate outputs on classical competitive programming algorithms and tasks.

I produced the following slide deck (gave as keynote at WWW'20 Workshop on Deep Learning for Graphs) which outlines the recent explosion of work in the area (including my own). There is credit to Codedorces in one of the slides -- as one of the places that really got me into algorithmic programming / computer science in general -- including a photo of the ACM-ICPC team from Cambridge I coached (dd__, MeinKraft, zDule98) that won NWERC'17. :)

Hope you'd find it interesting!

Recording: https://www.youtube.com/watch?v=IPQ6CPoluok

Slides: https://petar-v.com/talks/Algo-WWW.pdf

Cheers, Petar

Codeforces Round #169 — Unofficial Editorial

I really enjoyed this round, the tasks required more thinking than coding and that's always a good thing. I'd like to share my solutions to the problems here. Hope you enjoy them!

A — Lunch Rush

This problem was the easiest one in the competition, and the solution is just the simple implementation of what is given in the task statement — calculate the fun level for each restaurant, and output the maximal value.

My code: http://www.codeforces.com/contest/276/submission/3180631

Time complexity: O(n)

Memory complexity: O(1).

B — Little Girl and Game

The key thing to notice in this task is, if we can arrange the characters of the string we have into a palindrome, then there can be at most one character with an odd amount of occurences. This easily gives us the answer: if there are <= 1 characters with an odd amount of occurences in the initial string, then the winner is the first player. Otherwise, the answer is dependant on whether the amount of characters with odd amounts of occurences is even or odd; if it's even then the second player wins, otherwise the first player wins (since the one who is forced to get this amount to one first is going to lose).

My code: http://www.codeforces.com/contest/276/submission/3181475

Time complexity: O(n)

Memory complexity: O(n).

C — Little Girl and Maximum Sum

In this problem the sensible thing to do is to count the amount of times we are going to add some index of this sequence; then the maximal number gets assigned to the index that is added the most, and so on. In order to count the amount of times we referenced each index, we can use the Binary Indexed Tree structure to store cumulative sums with update and retreival times of O(log n) (a great tutorial for this structure can be found here: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees).

My code: http://www.codeforces.com/contest/276/submission/3182445

Time complexity: O(n log n)

Memory complexity: O(n).

D — Little Girl and Maximum XOR

A XOR of two numbers has the value of the i-th bit set to 1 if and only if their values on this bit differ (i.e. one is zero and the other is one). We can be certain that we can pick two numbers with differing bits on the i-th position and conform to the rest of our solution, if the difference between R and L is greater than or equal to 2^i (because the zeroth bit changes state every 2^0 values, the first one every 2^1 values and so on). When this difference is lesser than 2^i, we use another key observation: within one of those blocks of length 2^i, the sequences of values where the i-th bit is zero and where it is one are contiguous; i.e. we just have to check whether the i-th bit of R differs from the i-th bit of L, and then we know whether or not they're in the same subsequence with respect to that bit. If they are not, we can add 2^i to our solution. We carry on until 2^i is lesser than or equal to R.

My code: http://www.codeforces.com/contest/276/submission/3183526

Time complexity: O(log n)

Memory complexity: O(1).

E — Little Girl and Problem on Trees

A key observation on this problem is that when we perform the operation 0 on any node which isn't the root, we increase the nodes at [depth[X] — d .. depth[X] + d] along its chain. Of course, if depth[X] <= d, this will also affect other chains, namely, all depths lesser than d — depth[X] + 1 will be increased as well. To handle this we can store information about each chain in a BIT structure — one for each chain (this structure was mentioned already in solution for task C), and also store information about the global depth updates in another BIT. When we query a particular node, we simply add up the BIT value of its relevant chain and of its depth.

My code: http://www.codeforces.com/contest/276/submission/3187958

Time complexity: O(q log n)

Memory complexity: O(n).