Editorial for Back From Summer '17 P5: Confusing Codeforces Contest

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: kobortor

Subtask 1

Since N \leq 9, we can simply try every single path by doing depth first search, and check if the edge is blocked before proceeding.

Runtime complexity: \mathcal O(K 2^N N^2)

Subtask 2

Since N \leq 1000, we can create a matrix representing links (or blocked links) between people. Note that the ways to get to person #N is the sum of ways to get to person #i (1 \leq i \leq N) where i \to N is not blocked. Therefore, we can use dynamic programming to memorize the solutions for people before.

Runtime complexity: \mathcal O(N^2+KN)

Subtask 3

The big difference from the last subtask is that the number of ways to add has gotten much larger, but the number of blocked links has not increased much. We can take advantage of this by maintaining the sum of all previous elements, and subtracting the blocked links instead. To avoid duplicate deletions, we can use a set or similar data structure to maintain all the unique blocked links for each person.

Runtime complexity: \mathcal O(N \log N \sum X^2)

Subtask 4

Let us mark each person with a bitset (binary number) from 0 to 2^K-1 to indicate the sets covering it. A bit will be on to indicate the person is in the group, and off otherwise. Two people are in the same group only if they overlap on at least 1 bit. In other words, A \mathbin{\&} B \neq 0. After we solve a person, we can store their path count inside an array of size 2^K. When we try to solve for another person, we can loop through the array and subtract from the indices that share at least one bit with the binary number of that person.

Runtime complexity: \mathcal O(N 2^K)

Subtask 5

The same idea is used as subtask 4, however, we can't pass using the same method as 2^{14}=16\,384, which is way too big to run within the time limit. To get around this, we need to create a data structure which can efficient update and query the sums from indices that share at least one bit.

To solve queries, we first need to update. To do this, we can split the 14-bit binary number into 2 pieces of 7 bits each. Let us call those part A and part B.

First, we create an array of 2*2^7*2^7. Let us call it ds[2][2^7][2^7].

To update, we go through each integer i from 0 to 2^7-1. If A \mathbin{\&} i = 0, update ds[0][i][B], otherwise update ds[1][i][B].

This way, ds[0][A][B] contains the sum of all numbers in the form XB where X \mathbin{\&} A = 0. Meanwhile, ds[1][A][B] contains the sum of all numbers in the form XB where X \mathbin{\&} A \neq 0.

First, we add ds[1][A][0 \dots (2^K-1)] since that contains all numbers that share a bit in the first 7 bits. To account for the remaining numbers that do not share the first 7 bits, but share some of the last 7 bits, we go through ds[0][A][j] for all j where j \mathbin{\&} B \neq 0.

Using this data structure, we can update and query in 2^{K/2}=\sqrt{2^K} time.

This is sufficient to solve for the last subtask.

Runtime complexity: \mathcal O(N \sqrt{2^K})


There are no comments at the moment.