RAD's blog

Codeforces Round #166 Tutorial
By RAD, 12 years ago, translation, In English

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.

  • Vote: I like it
  • +39
  • Vote: I do not like it

Comments Comments (35)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any background in problem E?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In 4rth q after so many TLE's I have drawn an inference that generally map is slower than set though both being dynamic memory allocation....

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm quiet new in Java,I keep getting TLE and use trie data structure,any advises?(Though the same code written in C++ got AC) code

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It's not because you use Java, it's because you make a lot of substring() calls.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks,so is there a faster way to remove the first character from string?Or i should use array of chars instead of strings or something like that

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just remember where the string really begins.

        → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i m not getting the problem E' editorial can any one explain ?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem 4, suffix array with lcp can also be used. We can first pre-compute the bad character count for all the substrings and store it in a table. Then, iterating through the suffix array and avoiding duplicate substrings using the lcp table, we can find the answer.

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Hello. I am having trouble with the problem D (getting TLE). I am using the trie to solve the problem. When I build it, I already keep track of the current number of bad characters. If it is bigger than k, I leave the recursion. The final answer is the number of nodes of the tree.

Could anyone help me please? What am I doing wrong? Code

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Why do you have these 2 nested loops in main() function? You are not really using i anywhere.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      OMG, thanks RAD. It was something I was trying and forgot to remove.

      for (int i = 0; i < n; ++i)
{
    put(t, s + i);
}
      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C: in each set Ui, its elements ui, 1, ui, 2, ..., ui, |Ui| do not form an arithmetic progression (in particular, |Ui| ≥ 3 should hold). What's the meaning of it ? Does it means when Ui < 3 there is no necessary to hold this condition ?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me what's wrong of my code ? Problem D: 3145554

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Complexity

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think so, I learned from this AC submission? Why his is ok ? 3105181

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Try to find out what is the complexity of string comparisons

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          so you're saying that insertion in set is taking time??

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can implement it using sets but I think you have to iterate for len =1 to len=n and index 0 to n-len; after every len you have to clear your set to prevent it from exceeding memory limit

    → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem D 271D - Good Substrings : This is my code. I've used the concept of Rolling hash/Rabin Karp algorithm. But I guess there are some collisions happening and it's failing on test case number 8. Any help is greatly appreciated. Been trying this for a long time.

Code: 27820412

Update: Solved! I tried many different ways. Initially, I used two hash moduli instead of one, but this exceeded the Time Limit on test #8 (Which is weird!). I ended up using a really large prime (About the size of 2^50) which just passed the time limit for Testcase #8 and passed the cases as well. :)

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ya i was also getting wrong answer due to collisions so just used two different numbers 31 and 67 with modulo 1e9+7 and it got accepted

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D can be solved using 2 pointer and little bit of a lcp array.This is my solution. https://codeforces.net/contest/271/submission/44768791

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D is like using 2 hashes of 10^9 size-TLE Using 1hash of 10^9 size -WA and using a very big hash and multiplying recursive -TLE

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Beautiful Year https://github.com/arsalanhub/CodeForces/blob/master/Beautiful%20Year

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hey. Please stop spamming on every tutorial blog with your solutions of Div2 A problems. There are already many solutions available in the submissions section. You're not helping anyone at all. You're just spamming and also unnecessarily bringing old posts in the Recent Actions section.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

271D using Z algorithm: https://codeforces.net/contest/271/submission/68098565

prereq: distinct substring using Z ( read it from CP algo ).

Implementation: Now I am assuming you know distinct substr using Z, then: we start counting the answer for a prefix after the zmax of that prefix. ( because we'll have distinct substring only after zmax)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can enyone help me with D problem? I am tring to sove it with hash but it has wrong answer on testcase 8;

https://codeforces.net/contest/271/submission/243292259

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, you will get WA because there are more than 1e6 sub-strings that you will compare using hashes, which gives a very high chance of collision. So you should use two hashes instead of a single one, I used two by just changing the modulo.

    Here is my AC submission : https://codeforces.net/contest/271/submission/245638497

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks

      → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      try submitting the same solution again, it will TLE in tc8

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes you are right. I tried with some optimizations like using arrays instead of vectors and bit operations inside Exponentiation and it passes but barely

        → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, in sample test case 1 explanation, bab is given as a good substring but not aba. As b is a bad letter, bab should be a bad substring and aba should be a good substring. In sample test case 2 also, the solution is limiting only to two characters but there is no such constraint in the problem statement. please help me understand the question.

→ Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you will read the question carefully, it is given that If the i-th character of this string equals "1", then the i-th English letter is good, otherwise it's bad. In the first testcase, the value of k is 1 , i.e., we can have at most 1 bad letter, in this case which is 'a'. So, "aba" is a bad substring because it contains two 'a', whereas "bab" is a good as it contains only 1 'a'.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i have facing problem with D (good substring) i am facing time limit exceed but i have implemented trie and still it is slow here is my solution 272082061 any help is appreciated

thank you!!

→ Reply