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

Автор Edvard, 8 лет назад, По-русски

Привет, Codeforces!

22 августа 2016 года в 17:00 MSK состоится шестнадцатый учебный раунд Educational Codeforces Round 16 для участников из первого и второго дивизионов.

Это будет последний учебный раунд поготовленный мной. Как я уже ранее писал я начал работать в замечательной компании AIM Tech и теперь у меня стало заметно меньше времени на подготовку раундов. Не хочется из-за этого терять качество и интересность раундов, поэтому вскоре вы узнаете кто будет продолжать подготовку раундов.

Комплект задач был частично предложен участниками сообщества. Задачу C предложил Resul Hangeldiyev Resul. Задача E — это очередная задача предложенная Zi Song Yeoh zscoder. Задача F была предложена пользователем Александром Кульковым adamant. Оставшиеся задачи некоторое время крутились в моей голове и я наконец решил их дать на раунд (они являются достаточно стандартными, но важно уметь их хорошо решать).

Задачи для вас подготовил я (Эдвард Давтян). Спасибо Татьяне Семёновой Tatiana_S за проверку английских текстов условий. Большое спасибо Ивану Поповичу NVAL за вычитку и тестирование задач A-E и Александру Кулькову adamant за вычитку и тестирование задачи F.

На раунде вам по традиции будет предложено шесть задач. Надеюсь они вам понравятся! Думаю комплект задач получился чуть сложнее, чем обычно, но уверен это вас не остановит :-)

Good luck and have fun!

UPD 1: Завершено тестирование на взломах. Спасибо за участие!

UPD 2: Опубликован разбор задач.

  • Проголосовать: нравится
  • +249
  • Проголосовать: не нравится

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

Your rounds are always interesting, We'll miss these rounds :D

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

Good luck at AIM Tech!

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

what a sticker !!!!!!!!!!!!!!!!!!!!!!

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

I love the ECR,because it's unrated,so I can enjoy the competition's process rather than the result!

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

моё увожение

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

Rated?

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

Guys , is AIMTech round rated ?

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

Is this rated?

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

This does not stimulate without rating

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

    This is a good opportunity to train your skills. And you have to train in order to get nice rating anyway. Here you still can compete with passion and without any risk to your rating. What else?

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

    Our goal is to improve ourselves,

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

Wish good luck to all :)

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

Hacking friends code is the funniest part :D

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

Why late ?

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

10 min late!!!!!!!!!!

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

Codeforces: " Contest has started. Proceed? OK? ".

Me: " OK! ".

*Page Refreshes"

I travel back 10 minutes

Codeforces: " 10 minutes remaining ".

and people said time travel is not possible :)

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

Now that the contest has been delayed there's a even shorter gap between this and csacademy's round...

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

wish there be no long queue...

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

Спасибо авторам за качественные и интересные задачи!

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

Didn't understand Problem B at all, can someone explain what was supposed to be done?

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

    google it "goemetry median"!

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

    All, you have to do it`s sort array and print middle element.

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

    there are dots in a line the x are the dots you have to choose one of the dots and then, you should find the dot that as the smallest sum of distance to other dot example 4 1 2 3 4

    if you choose 1st -> dis=1+2+3=6; else if you choose 2st -> dis=1+1+2=4; else if you choose 3rd -> dis=1+1+2=4; else if you choose 4th -> dis=1+2+3=6;

    therefore, the ans is the left one, 2

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

    For each point with coordinate x you calculate sum S of the distances to other points, namely S = sum{|x - x_i|}. Then choose the point with the smallest S.

    The most straightforward solution is O(N^2) — N times you calculate the sum of N integers. You can improve complexity if you first sort all points by coordinate. Then if you move from point i to point i + 1, the difference between S_i+1 and S_i is (2*i - n) * |x_i+1 - x_i|. Then you can calculate all S_i in O(N).

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

      "For each point with coordinate x you calculate sum S of the distances to other points"

      So like this?

      For input

      4

      1 2 3 4

      1st would be 1 + 2 + 3 = 6

      2nd would be 1 + 1 + 2 = 5

      3rd would be 1 + 1 + 2 = 5

      4th would be 3 + 2 + 1 = 6

      The output would be 2 since it is the left most and has the smallest sum, is this how we have to get the output?, I wish there was output explanation like in other contests.

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

Awesome, it could be great Div2 round!

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

Did someone pass E using segment tree?

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

Please someone explain us the "E" problem!!

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

    It`s simple dynamic programming. Create an array of positions,and then use this method to calculate next position.

    dp[1]=x; dp[i] = min(dp[i — 1] + x, dp[(i + 1) / 2] + y + (i % 2) * x);

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

      Why is this correct?

      EDIT: Nevermind, I see it now.

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

        Well, DP is like magic :).

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

        In optimal case the sequence of operations could never have a Delete operation just after an Add operation. As they'll cancel each other's effect and will increase cost, so we could just remove those two.

        Also, there can't be two remove operations consecutively in optimal case as before any consecutive chain of remove operations, there will be copy operation (As add is not allowed before any remove and the sequence couldn't start from a remove). So, the operation string will have a sub-string like (Copy, Remove, Remove), and we can always reduce such a sequence to (Remove, Copy) to have the same effect with reduced cost.

        So finally we have two rules :

        1) There can't be any add operation before remove operation.

        2) There can't be any remove operation before remove operation.

        So if there's a remove operation, then we can be sure that the previous operation to it was a copy operation. And hence we can merge those two to a single operaton.

        So the modified operations are :

        1) Copy : (cost y)

        2) Add : (cost x)

        3) Copy (Double entire string) and Remove one character. : (cost x + y)

        The modified operations are incremental and will always increase the size of the string so a O(N) DP is easily possible now.

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

          So, the operation string will have a sub-string like (Copy, Remove, Remove), and we can also reduce such a sequence to (Remove, Copy) to have the same effect with reduced cost.

          I don't see how the cost will always be reduced with (Remove, Copy). Aren't you assuming that cost(p)<=cost(q) , p<q ?

          n=8 => 1->2->4->8
          n=7 => 1->2->4->8->7, 1->2->3->6->7

          If x==y, then clearly cost of 7 > cost of 8.

          Can you please explain how you arrived at your conclusion?

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

            He doesn't make that assumption anywhere.

            If you have Copy then k times Remove you can as well have (k/2) times Remove then Copy. Ta-dam you just saved (k/2) remove operations. Now you can repeat that until you get 1 remove operation ( k -> k/2 -> k/4 ... k==1 ).

            Example:

            Case 1: x letters -(copy)-> x*2 -(remove k times)-> x*2-k letters

            Case 2: x letters -(remove k/2)-> x-(k/2) -(Copy)-> (x-(k/2))*2 == x*2-k

            Case 2 will always be cheaper since you just remove fewer times.

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

      Nice DP!!!

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

      Please, can you explain why if write "dp[i / 2]" solution gets wa6, but if write "dp[(i + 1) / 2]" solution gets ok?

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

        dp[(i+1)/2] + (i%2)*x + y represents a duplicate operation and a remove operation (when i is odd), if you use dp[i/2] you won't consider those operations

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

          Thanks, I understand.

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

          Lets say , we currently have 2 a's in the string, if we duplicate and add element we get 5 a's in the string. Similarly, if n=5, if we remove and are going to de_duplicate we will get 2 a's right. But why are we going to a string having 3 characters.(5+1)/2 after spending x+y.

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

      why my recursive dp solution not working 20081091

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

        Your solution is wrong, your recursion as cycles.

        dp(x+1) -> dp(x-1) for example

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

Is there no open hacking this time?

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

I have no clue how people managed to come up with logic of building odd matrix without googling the solution,this algorithm is way confusing on first look.

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

Statement for B problem asked for a a which may or may not exist in the array. The question statement was ambiguous. Many coders faced the difficulty that they understood that it may any integral point and they were giving the geometrical median, whereas the question was asking for any x in the array. Please make clear statements.

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

    No, the answer doesn't require to be exist in the array, but you can prove that the minimum answer always exist in the array.

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

I asked in problem B if the point X is one of the input points but even the answer didn't show that it must be one of the input points

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

    It doesn't follow from the task, but this can be proved.

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

      how to prove that ot will be the optimal if we take the point from the input there are many optimal solution we could have by other points not in the input !

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

        The sum changes monotonically between x[i — 1] and x[i].

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

        Obviously that the answer point can't be to the left of the left input point and to the right of the right input point. Then assume the answer point is not one of input points and distance to the nearest point in the left is d1 and in the right — d2, the amount is S and also there are k points to the left of out. Then if we choose the nearest point in the left the sum is S — k * d1 + (n — k) * d1 = S + (n — 2 * k) * d1. And if we choose the nearest right point the sum is S + k * d2 — (n — k) * d2 = S + (2 * k — n) * d2. One of these numbers is less than S. So choosed point is not the answer.

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

    if N is odd then there is only one answer and it is in the input.

    if N is even there can be many answers but there have to be at least one of them in the input.

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

    that's because the left most answer is always one of the given points

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

Can we solve F with trie data structure?

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

Скажите, пожалуйста, можно ли было сдать F Ахо-Корасиком? Я сдавал несколько раз, но стабильно получал WA7, и до сих пор не понимаю, в чем ошибка.

http://mirror.codeforces.com/contest/710/submission/20056721

UPD. В чем ошибка понял. Но как исправить не очень представляю.

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

looking at tourist's solutions makes me feel so stupid

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

can anyone hack this solution, as the value for accumulating sum is taken as int. http://mirror.codeforces.com/contest/710/submission/20059546

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

    I think it can't be hacked. Because count1 will always equal to count2, so it doesn't matter whether they overflow or not. And the code will always output coords[N/2 — 1] if N is even, and that's the correct answer.

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

Was it possible to solve problem D using ternary search?

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

Tests of problem C are all possible inputs! and someone are trying to hack !!!

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

problem B ) please guys now i understand the optimal solution is to get a point from the input to be the optimal .ok ! but i don't know why the element in the middle of the array is the answer not the middle of the all distance ? proof please!

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

    You could also try out all the points and pick the best one.

    http://mirror.codeforces.com/contest/710/submission/20051324

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

      i did saw it before and i liked it but i want to understand why the middle element ? i can do ternary too can't i ?

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

        For example if you have n = 7 and the following points

        1 3 5 7 9 11 13

        Let's say we choose the middle point ( 7 ). If we try to move it to the left we'll end up adding 2 ( 7 — 5 ) to the total distance 4 times while decreasing 2 from the total sum 3 times which means that the total distance will be greater than the distance we would've had by choosing the middle element.

        Same goes for moving the element to the right.

        EDIT: If you meant why the middle element and not the middle of all the distances, that's because you need to choose an element from the array.

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

          why the middle element and not the middle of all the distances?

          that was my question ..but thinking in it i think selecting a point from the array will be better

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

            Suppose you have two points, you can easily see that while you are in between them the sum of distance is constant and the smallest and the leftmost point is the point on the left(and an integer as it is an input point), but if you go right of the right, sum of distance increases and so is if you go left of the left. Now consider 3 points, for the extreme points the answer lies between them, now forget them and consider the middle point, for a single point the answer lies on the point itself because deviating from it will increase the value of distance from it to a nonzero value and since it is in between other two points it is the answer. Next, consider 4 points for the extreme two points least sum points lies between them and for the middle two between them and points between middle two also lies in the middle of extreme so the answer is left of the two middle points as it is the leftmost satisfying above conditions. And so on...

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится -15 Проголосовать: не нравится

hi there , i think there is a problem in your judge , during the contest i submited the true answer , but i received the wrong answer , i checked that answer and there is no wrong thing in my output , here is my code :

http://mirror.codeforces.com/contest/710/submission/20061137

any ideas ?

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

    The sum on the main diagonal for n = 3 is 8 + 9 + 7 = 24 which is even.

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

      Oops , i didn't check main diagonals in my code , all my focus was on rows and columns , sometimes brain doesn't work during contest ...

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

What is the idea behind problem F? A dynamic Aho-Corasick?

I'm struggling with this! :-(

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

    My approach is SQRT decomposition. Lets have a constant B equal to about 2000.

    If a query of 3rd type has length less than B we can simply check all substrings and get the answer. The complexity is , where L is the length of the text.

    If a query of 3rd type has length greater than B we can make an O(N) or O(L) approach, because there are at most such queries. We can build a tree of the suffix links (if we use suffix automaton) or failure links (if we use Aho Corasick). The edges are of form "link[u] -> u". Then to for every such query we will build such a tree. Now for every string in the set D, we update its end state's subtree with 1. Now to get the answer to the current string, we go through all of its prefix states and query them (vertex query). So the problem becomes subtree update and vertex query. The whole query can be done in time.

    The overall complexity is . We want to have almost the same complexity for the 2 types of queries of 3rd type. Thats why we pick B about 2000.

    I solved the problem with a generalized suffix automaton during the contest but it can be easily replaced with an Aho Corasick. Link to submission: 20062687.

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

      If a query of 3rd type has length greater than B,for each query,you will build a tree,what's the complexity about making a tree,is the total length of strings in suffix automaton? And there are L/B queries,how to calculate complexity?

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

        If the query is of 3rd type and it's heavy (has length  ≥ B) we build the tree on all string in the automaton. We can easily build it in O(L). There are at most heavy queries because every heavy query has length  ≥ B. This means that to solve all heavy queries we have complexity of .

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

    Another interesting way to solve it is to keep logM automata. When adding a string, you create an automaton of size 1, consisting of that string. While you have two automata of the same size, merge them, obtaining one of double the size. The merge can be done using the typical Aho Corasick build procedure. To handle the erase operation, we can keep another logM automata, composed of the erased strings. We will handle these the same way we did for the above. Therefore, the answer of a query will be query(all) - query(erased). This achieves a complexity of O(sumlengths * logM). This idea was discussed here. 20053668 implements it, to some extent.

    If you prefer not to use SAM or Aho Corasick, you can insert the strings of length < SQRT into a trie, and for each of the rest you build the KMP automaton. This method achieves O(sumlengths * sqrt(M)). You can check out 20058436 for more details.

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

      Wow! The first solution is really cool! Thanks for explaining it :)

      By the way there is another possible solution with hashes. We can see that there are different lengths of strings. That means that we can store all hashes for a given length in a hashtable for the corresponding length. This way we can simply create a solution with hashes.

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

        But there may be more than sqrt(L) hash values, so the time complexity may be more than O(Lsqrt(L)) I guess?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 5   Проголосовать: нравится +15 Проголосовать: не нравится

          There can be at most O(sqrt(L)) distinct lengths because the sum of the lengths doesnt exceed L, so in the worst case, which is 1 + 2 + .. + k = l equivalent to k * (k + 1) / 2 = l, k is of order O(sqrt(L)). To answer a query we will traverse all the O(sqrt(L)) hash tables, which we can query in O(1), along with some partial substring hashes on our query string.

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

          Oh I understand now. Thanks for the explanation.

          But I think this method might not be fast enough. My submission get TLE.(20105952) Maybe if the time limit is 10s then I can pass?

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

            You can pass it, if you are careful when implementing it. Try to get rid of unnecessary modulo operations, instead of keeping an unordered_map of unordered_maps you can keep a set or an unordered_set of fixed size, and one set to keep track of the distinct lengths.

            L.E.: 20106642 is my accepted code, following this idea.

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

I'm a rank beginner. Can somebody shed some light on the arithmetic progression problem? I brute forced it and it gave me several TLEs. I have a hard time figuring out just by looking at other people's submissions.

I'd appreciate it if someone could point me to the correct number theory algorithm or lemma. Thanks.

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

I think E can also be solved using bfs with priority_queue. Did anybody try it?

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

    I've already done it in C++ and got TLE.

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

    I treat this problem as the shortest path problem. At first I got TLE when x is small and y is large, that's because the distances of the nodes are updated quite frequently. Then I set the initial distance of the i-th node as i*x, so the distances won't be updated too frequently. Then I got AC.

    You can also see my submission for details 20059443

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

      Nice idea!when I got TLE,I thought it cannot get Accepted by Spfa!Help a lot!

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

    It can be solved with Dijkstra after a few observations.

    • First of all, make a list of relevant states. N is relevant. Then, if x is relevant, x - 1 and x + 1 are relevant if x is odd, and x / 2 is relevant if x is even.
    • If we're gonna do many add operations in a row, it makes sense to do it only before our first copy operation, otherwise we could just replace two of them for only one before the last copy operation. So we set D[i] = X * i for all relevant positions x.

    Once we're done, we push all relevant states with their initial distances to the Dijkstra's queue and run it. It runs instantly. See here -> 20087826

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

Fuck Editor

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

For the problem B

a same position could have more than one points?

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

    Yes. But since we only need to output the position of the optimal point so it doesn't matter.

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

Where can I find the editorial please?

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

Did anybody solve problem D? Can anybody give me an approach for this problem?

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

    We can assume that b1 <= b2 (otherwise let's just swap(a1, a2) and swap(b1, b2))

    Sequence 1: b1, b1+a1, b1+2*a1, b1+3*a1, ...

    Sequence 2: b2, b2+a2, b2+2*a2, b2+3*a2, ...

    1) Let's find minimum K>=0 such that b2+K*a2 belongs to the sequence 1.

    b2+K*a2-b1 must be divisible by a1. It's enough since b2+K*a2-b1 >= 0.

    K*a2 = b1-b2 (modulo a1)

    Let's denote GCD(a1,a2) = a_gcd

    1.1) If (b1 — b2) is not divisible by a_gcd, there is no solution to this. The sequences do not have any common numbers, thus the answer to the problem is 0.

    1.2) If (b1 — b2) is divisible by a_gcd:

    K*(a2/a_gcd) = (b1-b2)/a_gcd (modulo a1/a_gcd)

    We can use any algorithm to find "modular multiplicative inverse": https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

    2) The first common element of Sequence 1 and Sequence 2 is A = b2+K*a2

    Next elements will be A+LCM(a1,a2), A+2*LCM(a1,a2), ...

    If you know A and LCM(a1,a2), it's easy to find how many of these numbers belong to interval [L, R]

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

    I solve it with 2 brute force solutions.

    0) if a1 < a2 swap a1/a2 and b1/b2

    Brute force #1: a1 > 1000 iterate first sequence and check if point in second.

    Brute force #2 a1 <= 1000, if b1 < b2, required increase b1 to be >= b2 Scan b1, b1+1, b1+2*a1, ... b1+1000*a1 to find a first common point, if not exists answer will be 0 As we know first common point and also need know a step it will be lcm(a1,a2) Now we have one progression and need know count of points in interval [l,r] it possible done in O(1).

    That's all.

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

Problem D, test 84: 1643097 -1745072283 4818 -1699409409 1391770030 14101637

How about constraint L <= R?

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

IT WILL BE NOT EASY! BUT I WISH EVERYBODY GOODLUCK!

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

I implemented aho corasick algorithm on problem F and I got idleness limit exceeded on test 1, I wonder what is the cause? It's the first time I encounter this problem so I don't have an idea where the problem lies. =/

[submission:http://mirror.codeforces.com/contest/710/submission/20107516]

UPD: Didn't noticed the solution is required to be online. =P"

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

When will the editorial be posted?

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

Будет ли разбор?

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

Here is my solution to Problem D,may be easier to understand.

Some restriction like:

If we combine these,we can get some scale like L1 <  = k' <  = R1

Then,we need k' be integer which means a1 * k' - a2 * l' = b2 - b1 has integer solutions and . This can be solved used exgcd.

If u are still confused,here is my code.

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

This round is important and must have an English Editorial.
Codeforces is a good international site.
Please don't limit us by only releasing in Russian. I kindly request you to release an English version.

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

Who will continue to prepare next educational rounds?

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

When will the next educational round start? It is a good idea to have a educational round on every Sunday.