Codeforces Round #166 Tutorial

Codeforces Round #166 Tutorial

By RAD, 11 years ago, translation,

271A - Beautiful Year

This is a very straight forward problem. Just add 1 to a year number while it still has equal digits.

271B - Prime Matrix

Precalculate the next prime for every integer from 1 to 105. You can do that in any way. The main thing is to test all the divisors up to square root when you are checking if a number is prime.

Now for each aij (element of the given matrix) we can easily calculate addij — how many do we have to add in order to make aij prime. After that all we need to do is to find row or column with minimal sum in this new matrix.

271C - Secret

If 3k > n there is no solution (because each of the k sets must have at least 3 elements). Otherwise we can divide first 3k words in the following way:

1 1 2 2 3 3 ... k k 1 2 3 ... k

For each of the k sets, the difference between the first and the second elements will be 1. And the difference between the second and the third elements is definitely not 1 (more precisely, it is 2k - i - 1 for the i-th set). So each set doesn't form an arithmetic progression for sure.

For this solution it doesn't matter how we divide the rest n - 3k words.

271D - Good Substrings

At first, build a trie containing all suffixes of given string (this structure is also called explicit suffix tree). Let's iterate over all substrings in order of indexes' increasing, i. e. first [1...1],  then [1...2], [1...3], ..., [1...n], [2...2], [2...3], ..., [2...n], ... Note, that moving from a substring to the next one is just adding a single character to the end. So we can easily maintain the number of bad characters, and also the "current" node in the trie. If the number of bad characters doesn't exceed k, then the substring is good. And we need to mark the corresponding node of trie, if we never did this before. The answer will be the number of marked nodes in the trie.

There is also an easier solution, where instead of trie we use Rabin-Karp rolling hash to count substrings that differ by content. Just sort the hashes of all good substrings and find the number of unique hashes (equal hashes will be on adjacent positions after sort). But these hashes are unreliable in general, so it's always better to use precise algorithm.

271E - Three Horses

It could be proved, that a card (x, y) (x < y) can be transformed to any card (1, 1 + k·d), where d is the maximal odd divisor of y - x, and k is just any positive integer. So every (ai - 1) must be divisible by d, i. e. d is a divisor of gcd(a1 - 1, ..., an - 1), and we can just iterate over all possible divisors. Let's take a look at all the initial cards (x, y), which have have d as their maximal odd divisor: these are cards with y - x equal to d, or 2d, or 4d, 8d, 16d, ... Don't forget that the numbers x and y must not exceed m. It means that the total number of cards with some fixed difference t = y - x is exactly m - t.

The resulting solution: sum up (m - 2ld), where d is any odd divisor of gcd(a1 - 1, ..., an - 1), and l is such, that 2ld ≤ m.