Hello everyone!

I am happy to announce that "Looking for a Challenge?" book is now available in Spanish as "¿Quieres un reto?". This was possible thanks to great effort of Miguel Revilla Rodríguez who has translated, typeset and edited this publication. Thanks, Miguel! It was a pleasure working with you on this project.

You can check different buying options on BookFinder:

¿Quieres un reto?: Los mejores problemas de los concursos de programación de la Universidad de Varsovia

You can also find more competitive programming books in Spanish on OJBooks website.

¡Feliz lectura!

Hello everyone!

Recently, I've finished writing an article in which I explain how to solve problems from IOI 2018.

In my opinion the problems are really challenging and interesting, and are good learning material. However, the official webpage of the competition provides only sketchy explanations, and they miss implementations.

In the article I try to present detailed approach for each problem, going through subsequent subtasks. I've also prepared full C++ implementations (38 programs in total).

I hope you will find it useful!

Hello everyone!

If you follow Codeforces blogs of Polish contestants like Swistakk and kostka, you know that "Looking for a Challenge?" book is once again available to buy, since the second revised edition was published last year.

If you watch "Algorithms Live!" talk show by tehqin, you may also know that there is a Volume Two of this book, containing solutions to 44 problems from the Polish Collegiate Programming Contest (national qualifications for ICPC) that were organized in 2011–2014 by the University of Warsaw. Up to now the book was available in Polish in limited edition only.

But this changes now! After proposing the idea to the University of Warsaw authorities, they agreed to publish the PDF with the full book. Therefore you can download it for free. The book has been edited by the same team as the Volume One, so you know what quality you can expect.

But this is not all! Since the book in Polish wouldn't get so much international attention (yet we all know that automatic translation services can be much of use here), I have decided to start a project of translating it to English. Currently the first part (out of four) of the translation is ready, and I am planning adding remaining parts in the following months. I will be keeping you updated by sharing the progress in the updates to this post. Hopefully the whole book will be ready before World Finals 2020.

Download the English translation of "Looking for a Challenge 2"

Happy reading and coding!

Standard approach

One of standard ways to implement constant-time LCA queries on a tree is to preprocess it by doing an Eulerian tour which creates an array of pairs (depth, index) for subsequent vertices visited on the tour, and then reduce an LCA query to RMQ query on a certain fragment of this array:

const int N = 1<<LOGN;
typedef pair<int,int> pii;
int n, T;
vector<int> adj[N];  // adjacency lists
pii euler[2*N];  // Eulerian tour of pairs (depth, index)
int tin[N];  // visit times for vertices

void dfs(int v, int par, int depth) {
  tin[v] = T;
  euler[T++] = make_pair(depth, v);
  FORE(i,adj[v]) if (*i != par) {
    dfs(*i, v, depth+1);
    euler[T++] = make_pair(depth, v);
  }
}

dfs(0, -1, 0);

int lca(int u, int v) {
  return query_rmq(min(tin[u], tin[v]), max(tin[u], tin[v]) + 1).second;
}

The RMQ problem can be solved with a sparse table, which after $$$O(n \log n)$$$ preprocessing allows to answer RMQ queries in constant time:

pii sparse[LOGN][N];
int log[2*N];  // binary logarithm

void init_rmq() {
  REP(i,T) { sparse[0][i] = euler[i]; }
  int logT = 0;
  while ((1<<logT) < T) { ++logT; }
  REP(f,logT) REP(i,T - (1<<f)) {
    sparse[f+1][i] = min(sparse[f][i], sparse[f][i + (1<<f)]);
  }
  log[0] = -1;
  FOR(i,1,T) { log[i] = 1 + log[i>>1]; }
}

pii query_rmq(int a, int b) {
  // query range [a, b)
  int f = log[b-a];
  return min(sparse[f][a], sparse[f][b - (1<<f)]);
}

The drawback of the solution above is long preprocessing. We can reduce it to $$$O(n)$$$ by using clever trick: we split the array into blocks of length $$$m$$$ and produce sparse table for array of size $$$O(n/m)$$$ created by taking minimum from each block. Then every query range either is an infix of some block or consists of several consecutive full blocks (which are handled by the new sparse table in constant time) and some prefix and some suffix of a block (which are also infixes).

Queries for infixes of blocks are preprocessed brutally: since the RMQ problem obtained from LCA has a property that differences between consecutive depths in the array are either +1 or -1, we can represent each block as the first element plus a binary string of length $$$m-1$$$ encoding the changes in depths. Thus there are $$$2^{m-1}$$$ different bitmasks and for each of them we have $$$O(m^2)$$$ infixes. For each infix we want to calculate the minimum value relative to the first element. It's easy to show how to preprocess them in $$$O(2^m m^2)$$$ time and memory, and if we take $$$m = \frac{\log n}2$$$, this is actually $$$O(n)$$$.

Conceptually this idea is quite easy, but in terms of implementation it could be rather lengthy (see e-maxx implementation). Now I will present my alternative approach to this problem, which results in a slightly shorter code.

Alternative approach

In the standard approach the details of encoding a block into binary string of length $$$m-1$$$ were not important, as long as we encode them consistently. Now we will fix a certain encoding, namely such that $$$m-1$$$ differences in depth are encoded as consecutive bits (the first difference from the left being the least significant byte), where +1 change is encoded as bit 0 and -1 change as bit 1. Suppose that we want to calculate the relative minimum value for a block described by some bitmask $$$mask$$$. If the LSB of $$$mask$$$ is 1 that means that we have -1 change and after that a mask $$$mask' = \lfloor mask/2 \rfloor$$$ of size $$$m-2$$$ shifted one level down. That means that minimal position for $$$mask$$$ is minimal position for $$$mask'$$$ plus 1. On the other hand if LSB of the mask is 0, the minimum is either on position 0 or in $$$mask'$$$ shifted one level up.

It looks, however, that we still need to calculate values for shorter masks (with $$$m-2$$$ bits and fewer). But observe that extending a mask, by adding bits 0 after MSB, creates a longer mask with the exactly the same value (since bits 0 correspond to series of changes +1 at the end of the block which don't affect the minimum). Thus we can just treat $$$mask'$$$ as mask of size $$$m-1$$$. Therefore we only need to preprocess $$$O(2^m)$$$ bitmasks, and we can do it in constant time per bitmask, thus we will be able to take $$$m = \log n$$$ to get $$$O(n)$$$ complexity of preprocessing.

const int NBYLOGN = N/LOGN;
pii sparse[LOGN][NBYLOGN];
int blmask[NBYLOGN];  // masks for blocks
pii lookup[1<<LOGN];  // minima for all masks as pairs (relative depth, relative index)

void init_rmq() {
  int Tm = (T+m-1) / m;
  REP(i,Tm) {
    sparse[0][i] = *min_element(euler+i*m, euler+(i+1)*m);
    blmask[i] = 0;
    REP(j,m-1) {
      blmask[i] |= (euler[i*m+j+1] < euler[i*m+j]) << j;
    }
  }
  int logT = 0;
  while ((1<<logT) < Tm) ++logT;
  REP(f,logT) REP(i,Tm - (1<<f)) {
    sparse[f+1][i] = min(sparse[f][i], sparse[f][i + (1<<f)]);
  }
  log[0] = -1;
  FOR(i,1,Tm) { log[i] = 1 + log[i>>1]; }
  lookup[0] = make_pair(0,0);
  FOR(mask,1,1<<m-1) {
    pii F = lookup[mask>>1];
    lookup[mask] = min(make_pair(0,0), make_pair(F.first + (mask&1 ? -1 : 1), F.second + 1));
  }
}

If we want to make a prefix query of size $$$k$$$ for a block, we need to take the submask having the first $$$k-1$$$ bits, but as we said before we could just zero the remaining bits. On the other hand if we want to take a suffix, we can just shift the whole mask to the right. Therefore the following code calculates value for a non-empty range $$$[a,b)$$$ contained in one block:

pii query_rmq_block(int a, int b) {
  int mask = (blmask[a/m] >> (a % m)) & ((1 << b-a-1) - 1);
  return euler[lookup[mask].second + a];
}

Finally, we have code for a general query, which takes care of two cases: either the query is inside one block or it spans multiple blocks (and then it separately calculates two border blocks leaving the rest for the sparse table):

pii query_rmq(int a, int b) {
  int A = a / m, B = (b-1) / m;
  if (A == B) {
    return query_rmq_block(a, b);
  } else {
    pii F = min(query_rmq_block(a, (A+1)*m), query_rmq_block(B*m, b));
    if (A+1 != B) {
      int f = log[B - (A+1)];
      F = min(F, min(sparse[f][A+1], sparse[f][B - (1<<f)]));
    }
    return F;
  }
}

As we said before, taking $$$m = \log n$$$ will give us theoretical $$$O(n)$$$ complexity. But for practical approaches it could be useful to make some empirical tests which value would be the best. For instance, we could try setting $$$m$$$ to be a power of two (e.g. 16 when $$$n \approx 10^6$$$), so we can replace costly divisions in queries with shifts.

Hello everyone!

Once again we invite you to participate in the 24-hour team programming contest Asseco Programming Marathon24 Gdynia 2014. Powered by CodiLime. The first edition in 2013 was quite a success: 243 teams of three from over 20 different countries were registered for the contest and 30 teams from 8 countries were qualified for the finals in Gdynia.

In the contest teams of three can participate. There is no limit concerning the age or education of contestants. Also there is no limit in equipment, programming languages or materials you can use during the contest.

The contest consists of two stages. You can check out problems from the first edition to familiarize yourself with the format. This year's tasks will also be prepared (among others) by Tomasz Idziaszek monsoon and Wojtek Nadara Swistakk.

The first stage are qualifications, which will start on 11th October 2014 at 9:00 CEST and will last for 5 hours. There will be 5 algorithmic problems, to which 10 test cases will be provided. You only submit outputs to the tests and you get immediate feedback on your score.

No more than 30 teams with the highest scores will qualify for finals. They will take place in Pomeranian Science and Technology Park in the city of Gdynia in Poland. Finals will begin on 29th November 2014 and will last for 24 hours. There will be 3 problems, which will require you to write a program communicating with the contest server through the TCP/IP protocol.

For three teams with the highest scores in finals there are prizes amounting to over 30 000 PLN in cash. For more information visit our site: marathon24.com. The registration closes on 9th October 2014.

Update: Also be sure to take part in Codeforces Round #270, for the top 25 participants of this round will get Marathon24 T-shirts!

Good luck and have fun!

Hello everyone!

We invite you to participate in a new team programming contest Asseco Programming Marathon24 Gdynia 2013. In the contest teams of three can participate. There is no limit concerning the age or education of contestants. Also there is no limit in equipment, programming languages or materials you can use during the contest.

The contest consists of two stages. If you have participated in Challenge24, you should be more or less familiar with the format.

The first stage are qualifications, which will start on 19th October 2013 at 9:00 CEST and will last for 5 hours. There will be 5 algorithmic problems, to which 10 test cases will be provided. You only submit outputs to the tests and you get immediate feedback on your score. Some problems will have only one answer, and some will be optimization ones.

No more than 30 teams with the highest scores will qualify for finals. They will take place in Pomeranian Science and Technology Park in the city of Gdynia in Poland. Finals will begin on 30th November 2013 at 11:00 CET and will last for 24 hours. There will be 3 problems, which will require you to write a program communicating with the contest server through the TCP/IP protocol. A sample problem could be controlling a team of units which compete with other teams on a virtual arena. On the contest site you will be provided with table, chairs, lighting, one power socket and one network plug. Any other equipment has to be brought by you. Organizer will provide accommodation before finals (Friday/Saturday) for every participant of the finals. Organizer does not pay for or provide transportation to Gdynia.

For three teams with the highest scores in finals there are prizes amounting to over 30 000 PLN in cash.

The problems will be prepared by Tomasz Idziaszek monsoon and Wojtek Nadara Swistakk. Even if you don't have a team of three, you are still able to solve problems for fun during qualifications. Just register yourself and create a single-member team.

For more information or sample problems visit our site: www.marathon24.com. Keep in mind that the registration closes on 17th October 2013.

Good luck and have fun!