codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

271.md (3659B)


      1 Source: https://codeforces.com/blog/entry/6662
      2 
      3 [271A - Beautiful Year](/contest/271/problem/A "Codeforces Round 166 (Div. 2)")
      4 
      5 This is a very straight forward problem. Just add 1 to a year number while it still has equal digits.
      6 
      7 [271B - Prime Matrix](/contest/271/problem/B "Codeforces Round 166 (Div. 2)")
      8 
      9 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.
     10 
     11 Now for each *a**ij* (element of the given matrix) we can easily calculate *add**ij* — how many do we have to add in order to make *a**ij* prime. After that all we need to do is to find row or column with minimal sum in this new matrix.
     12 
     13 [271C - Secret](/contest/271/problem/C "Codeforces Round 166 (Div. 2)")
     14 
     15 If 3*k* > *n* there is no solution (because each of the *k* sets must have at least 3 elements). Otherwise we can divide first 3*k* words in the following way:
     16 
     17 `1 1 2 2 3 3 ... k k 1 2 3 ... k`
     18 
     19 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 2*k* - *i* - 1 for the *i*-th set). So each set doesn't form an arithmetic progression for sure.
     20 
     21 For this solution it doesn't matter how we divide the rest *n* - 3*k* words.
     22 
     23 [271D - Good Substrings](/contest/271/problem/D "Codeforces Round 166 (Div. 2)")
     24 
     25 At first, build a [trie](https://en.wikipedia.org/wiki/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.
     26 
     27 There is also an easier solution, where instead of trie we use [Rabin-Karp rolling hash](https://en.wikipedia.org/wiki/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.
     28 
     29 [271E - Three Horses](/contest/271/problem/E "Codeforces Round 166 (Div. 2)")
     30 
     31 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 (*a**i* - 1) must be divisible by *d*, i. e. *d* is a divisor of *gcd*(*a*1 - 1, ..., *a**n* - 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 2*d*, or 4*d*, 8*d*, 16*d*, ... 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*.
     32 
     33 The resulting solution: sum up (*m* - 2*l**d*), where *d* is any odd divisor of *gcd*(*a*1 - 1, ..., *a**n* - 1), and *l* is such, that 2*l**d* ≤ *m*.