Блог пользователя komendart

Автор komendart, история, 12 дней назад, перевод, По-русски,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Проголосовать: нравится  
  • +78
  • Проголосовать: не нравится  

»
12 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Editorial for Problem B Div2 is not translated into english.its showing russian version

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is a fast editorial, thank you!

I noticed my approach differed from the expected way in problem div2 C.

I solved it greedily: if a room that was explored at time ti exists, then do not add to the answer, but update that room so that it is explored at time i. (since you revisited) Otherwise, increment the answer by one and then create a new room visited at time i.

Here is the code: 32262674

»
12 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I am not able to understand div-2 D clearly. Can anyone please explain?

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Your resultant string can not contain similar letters. For example, if you have "aba" where 'a' appears two times, it is already impossible to construct a string where "aba" will be the most frequent string. Now, using this fact, let's build a graph on letters of our strings. If we have a string "curd", that means we need to create 3 edges {'c' -> 'u', 'u' -> 'r', 'r' -> 'd'}. If such directed graph does not contain loops, just restore strings and output them in lexicographical order

»
12 дней назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

After reading this three times, it still doesn't make any sense "Let us note that projection of set of points to line move center of mass of initial set to center of mass of initial set to center of mass of projections multiset" I think it should be that "Let us not that the projection of the set of points to the line moves the mass center of the initial set to the mass center of the projected points". This is in the solution of div1D

»
11 дней назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The definition of D(N) in 886E is a bit confusing. It may be better if it is written in the following way.

Define D(n) as the number of good permutations of length n that have pn = n.

Anyway, thanks for the nice editorial. It is too bad that the contest is unrated(undated?), but I liked the problems.

»
11 дней назад, # |
Rev. 7   Проголосовать: нравится +1 Проголосовать: не нравится

When I got my code on Problem D accepted after the contest, it was more than 100 lines. I was thinking that I finally got accepted and was satisfied. But then when I saw another one's code: http://codeforces.com/contest/890/submission/32272491 It has just 40 lines!!! I was shocked. However, reading that piece of code made me think about the logic of my code and found that there was a lot of redundancy. Then I improved my code and it became less than 60 lines. I feel really lucky about the fact that we can read others' code on Codeforces.

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

886C var ... sort(1,n); for i:=2 to n do if a[i]=a[i-1] then inc(kol); writeln(kol+1); end.

good luck!

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D div 2, how should we print the anwser if we got the graph?

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If there are cycles, answer is NO. Otherwise, restore all strings and output them in lexocgraphical order. 32280888

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain how to restore all string? Reading code is hard for me.

      • »
        »
        »
        »
        11 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Well, your graph should be like a chain. If it is, just start to restore a string from a top of this chain one by one.

        • »
          »
          »
          »
          »
          11 дней назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks for the code. Can you explain the use of the sure array?

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A small addition to the 886C editorial, you also need to add 1 to the summation because the first room is NOT incorporated in the summation. This is because every term of the summation is a result of adding an "extra" room when a particular 'time' reappears in the array, ans since the first room is not added as "extra" room, it is therefore not a term in the summation. So the answer should be: ans = ans + 1

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Объясните пожалуйста, почему в задаче D "Если строка ab или любая аналогичная является самой частой, то после буквы a всегда стоит буква b, перед b всегда стоит буква a."? Если, например, самыми частыми являются строки "ab" и "cb", то строка "abcb" является хорошей, хотя перед b не всегда стоит a. И насчет циклов — если даны две самые частые строки "kek" и "lol", то в графе будут циклы, однако "keklol" все еще является ответом.

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вопрос снят, не подумал, что тогда отдельный символ будет встречаться чаще чем самые частые строки

»
11 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

"If there is cycle in such graph then good string doesn't exist." in Div2 Problem D.Didn't quite get it .... Can anyone explain ?

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    If it were so then the occurrence of a character would be more than once.

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oh yeah.Then the the repeated character will be more frequent than the list of given frequent strings , in the minimal case. That is why the strings should fit after each other or inside each other.

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

In Div I B, why 2nd test case can't have kekpreceqcheburek as answer. If I am not wrong this string contains kek, preceq and cheburek one time which is the most frequent count.

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    According to the question , A string (not necessarily from this set) is called good if all elements of the set are the most frequent substrings of this string.

    Here "kek" , "preceq" and "cheburek" are not the most frequent substrings of "kekpreceqcheburek". The most frequent substring is "k" with frequency 3. Hence it is not good

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      OK, it means that any substring will have part in maximum frequency. I missed that part. If you have solved can you explain me your solution.

»
11 дней назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

You have a typo in analysis for 886 E. The last factorial is right only in the second line, in the first and the third you should fix it to (h-1)!

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How do you derive that equation? Can you show us?

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      First addendum is the number of permutations where number n — 1 is among the first n — k — 1 numbers, all of this permutations are good. There are (n — k — 1) ways to place n — 1 and (n — 2)! ways to place every other number from 1 to n — 2.

      The second addendum is the number of permutations, where n — 1 comes at the h-th place, h >= n — k. Such permutation is good if its prefix of size h is good. So when we decide which numbers appear among the first h — 1, the number of such permutations is D(h) * (n — h — 1)!, because the n — h — 1 numbers between n — 1 and n can come in any order. There are C_n-2_h-1 ways to pick h — 1 numbers from the n — 2. So the result of multiplying is D(h) * (n — h — 1)! * (n — 2)! / (h — 1)! / (n — h — 1)! = D(h) * (n — 2)! / (h — 1)!

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      I will also translate my another comment.

      To find the final answer let's fix where n is placed in the permutation. Let it be the i-th position in 1-indexation. Then the number of such permutation is the number of ways to pick up and place the numbers that come after the i-th position multiplied by the nomber of good permutations of size i, which is D(i). The first multiplier is C_n-1_i-1 * (n — i)! = (n — 1)! / (i — 1)! So, the answer is sum_1_n[D(i) * (n — 1)! / (i — 1)!].

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Very thorough explanation!!! I understand it now. Thank you

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится +28 Проголосовать: не нравится

      Thanks, huesoss. I just want to put your explanation in easier to read format.

      First addendum is the number of permutations where number (n - 1) is among the first (n - k - 1) numbers, all of this permutations are good. There are (n - k - 1) ways to place (n - 1) and (n - 2)! ways to place every other number from 1 to (n - 2).

      The second addendum is the number of permutations, where (n - 1) comes at the hth place, (h ≥ n - k). Such permutation is good if its prefix of size h is good. So when we decide which numbers appear among the first (h - 1), the number of such permutations is D(h) * (n - h - 1)!, because the (n - h - 1) numbers between (n - 1) and n can come in any order. There are ways to pick (h - 1) numbers from the (n - 2).

      So the result of multiplying is

      To find the final answer let's fix where n is placed in the permutation. Let it be the ith position in 1-indexation. Then the number of such permutation is the number of ways to pick up and place the numbers that come after the ith position multiplied by the number of good permutations of size i, which is D(i). The first multiplier is . So, the answer is

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In div 2 D, can anyone explain why we are checking that all the characters of initial strings should be presented in our answer String. I mean that if we are doing dfs for all characters, then why we need to check it separately? If we do not check it, it is giving WA on test 24.

  • »
    »
    11 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    "A string (not necessarily from this set) is called good if ALL ELEMENTS of the set are the most frequent substrings of this string." And it looks like the path found by your dfs doesn't include ALL characters (and sequence of characters) from the set. E.g. 't' whereas the string you found is "crehpuqmbao"

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I am asking for the same reason. Why doesn't it include all characters even though we are checking for the dfs for all character.

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You start dfs only from the characters that have a zero number of incoming edges. If there is a cycle, then you won't start dfs on it.

    • »
      »
      »
      11 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      But for the cycle,the answer is already "NO". So,if there has been any cycle,we won't have reach at that step. I hope you are getting my point. Edit : Understood.Thanks a lot.

      • »
        »
        »
        »
        11 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        If the test case is just string "aba", then you have a cycle with no entry point, so you won't start dfs and figure out it was a cycle. You check that the answer is not empty, but if the input is "aba, xyz" then you will get "xyz".

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

If some string is the most frequent then all its substrings are the most frequent too.

Where in the problem is this stated guys ?

For example if the n=1 and the string is aba why can't we construct the string as aba because the statement only requires the string in the set to be the most frequent substring

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    It's inferred, not stated in the problem. Try the opposite statement: 1. Assume a string "aba" in the set is the most frequent. Inside it there is a substring that appears more than once: 2 "a" => then "a" appears more times than "aba" in the result string. => "aba" is no longer the most frequent string. Hence, the most frequent string (or all strings in the set) must have no duplicated substring in itself, i.e. every substring in it appears at most once. In short, any substring in the most frequent string(s) is only allowed to be inside any one string at most once.

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В задаче E мы нашли D(n) — количество хороших перестановок у которых на последнем месте n. Но не обязательно же что у всякой хорошей перестановке на последнем месте n. Как то можно свести к каждой?

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Переберём, где находится в перестановке число n. Пусть, это позиция i в 1-индексации. Количество таких перестановок – это количество способов выбрать и расставить числа, которые идут после i-й позиции, умноженное на количество хороших перестановок длины i, то есть D(i). Первый множитель равен C_n-1_i-1 * (n — i)! = (n — 1)! / (i — 1)!

    Значит, ответ на задачу равен sum_1_n[D(i) * (n — 1)! / (i — 1)!].

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I'm having trouble with div2(D): the case:

2 ab ac

Should give a NO however, this graph does not contain cycles

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In D, why is 2 ab ba impossible, why can't we form abba or aba?

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как задачу про восстановление строки решать? Может кто-нибудь алгоритм действий сказать?

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Also, map can be replaced with binary search

Could you elaborate on that? I don't really understand what it means.

  • »
    »
    2 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    were u able solve div1d? whats the idea behind the solution..the editorial is not even remotely helpful

»
10 дней назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

It is high time Codeforces started caring about the variation of English used in editorials. I usually don't mind small mistakes, as long as the meaning is not completely lost somewhere inside this modified grammar/vocabulary.

»
7 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

[ UPD : Got it and Solved ]

Can anybody help me in understanding what does exactly Div2 C wants with all possible combination of sample's explanation? I read several times but failed to understand the description as well as samples. ~ TIA

»
7 дней назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Were I can take the author solutions?

»
7 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have read Div2C problem several times.But unfortunately,i don't get the Sample Task even.Anyone please help me.Thanks in advance :)

»
6 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody please explain my why solution at 886E should be correct?

for N = 5 and K = 1

we have d1 = 0, d2 = 0, d3 = 1, d4 = 5 and d5 = 23, but with the formula above you get d5 = 26... d5 = (3! * 3) + 5 * (3!/3!) + 1 * (3!/2!) = 18 + 5 + 3 = 26.... L.E. I got it wrong...

»
5 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In div 1 E solution, can anyone explain hint 1 thoroughly? I didn't understand the state (i, r, k) and the transitions. Also if possible, provide some motivations behind this approach?