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

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

Всем привет! Этот раунд готовим я и KAN. Надеюсь, многим понравятся наши задачи.

Хочу сказать спасибо PavelKunyavskiy, который тестировал задачи, вычитывал условия и вообще помог. Еще раунд решали alger95, Skird, fdoer, sand-martin, спасибо им за это.

Конечно же огромное спасибо Gerald за организацию нашей работы, MikeMirzayanov за отличную систему и Delinur за перевод условий.

Надеюсь, что в этом раунде будет решено больше задач, чем в нашем предыдущем. Удачи!

Обратите внимание, раунд будет проведен в нестандартное время.

Разбалловка:

div1: 500-1500-1500-2000-2500

div2 : 500-1500-1500-2500-2500

Поздравляю победителей.

div1:

  1. al13n
  2. tomek
  3. niyaznigmatul
  4. voover
  5. Egor
  6. Zlobober
  7. White_Bear
  8. seanwu
  9. wjmsbmr
  10. peter50216

div2:

  1. fotiIe96
  2. zfmdhy786
  3. wzc1995
  4. gjh
  5. mynameisverylong

Разбор на русском: здесь

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

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

although the starting time of the contest is not as usual , I hope it will be a great contest and GL & HF to all participants :)

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

I hope the host could change the start time once again like a last year's contest.

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

I hope the host could change the start time once again like a last year's contest.

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

I expect a very technical and hard round. I liked your last round! :-{)

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

Great, I like the time of the contest! What are the scores? 500 — 1000 — 1500 — 2000 — 2500? or something else?

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

I like this starting time of the contest ^_^

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

I'm not sure if i'm going to stay up all night or take some sleep before this round.

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

Жаль, что придется пропустить раунд — он совпадает с локальным сорвенованием :( Будум писать виртуалку. Всем участникам удачи и высокого рейтинга!

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

    Походу все Алматинцы пропустят этот раунд :( печаль...

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

Starts 450 minutes earlier than the usual time . Hope , there'll be some surprise in the problem statements too as well as the starttime :)

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

@ Mike Mirzayanov

sir, why dont we have variable time for 'codeforces contests' like topcoder? is it because the usual time attracts lot of participants or it's just to distinguish Codeforces from topcoder?

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

    I totally agree.I'm excited because this round is at 12.00MSK.We Chinese coders don't have to stay up at 23.30(Chinse Time) to participate.At first I thought this round is by a Chinese or Janpanese coder,but it seems I'm wrong.Thank you tunyash for this round at such great time!

    I think,if Codeforces can have variable contest times like Topcoder,more coders will participate and Codeforces will become better.It is necessary to do so if Codeforces is to overtake Topcoder and become the first largest online programming competition site.

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

    agree too

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

:(((( at this day, tomorrow i have maths olympics :((( it begins at 10 o'clock and end at 2 o'clock :((((

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

Последний CF перед РОИ. Всем удачи.

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

Зарегился на всякий случай) Вдруг получится написать)

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

I like this starting time of the contest! Hope the starting time will be variant,(not limited to 7:30pm in Russia) so that more US or Chinese coders will attend the contest.

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

Will points distribution be standard or dynamic?

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

last contest was great.I hope it will be great too

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

I hope for a more organized editorial this time ... Guys take 1 day but give us good editorials .

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

As you can see many people couldn't participate this contest ... It might be good for some countries but it's not for most ...

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

    I mean variable contest times.I'm not suggesting we always have contest at 12.00MSK,there's no doubt we need 19.30MSK contest time.For example,I suggest 30% contest set at morning of MSK Time.

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

    As lsmll said, it should be good to everyone, so it's fair enough to variable the time so anyone will have a chance to participate. It's 5 A.M here in Brazil but i'm still gonna participate even though this time I really should be sleeping.

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

Test photo.

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

good for Chinese users.

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

good for Chinese users.

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

By the way, past tense of "read" is "read", not "readed".

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

My first contest in travel! Good luck!

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

Проблема: Chrome 25.0.1364.172, Код в окне взломов исчезает на 1 сек каждые 2-3 секунды. Невозможно смотреть.

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

    У кого-нибудь кроме меня при просмотре кода во время взломов была проблема постоянно появляющегося и исчезающего текста?

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

Time limit for Div2 B is too long :( even brute force from k to 1 can pass :(

Got an Unsuccessful Hacking Attempt when trying to hacking one of those brute force solution :(

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

    can you give me the link of this solution i think brute force will get TLE

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

      Here is one .. Actually it's kinda weird O.o , I implemented this solution in the practice and got TLE , but when I tried mikhail's code got AC .. I think it depend on the optimizer somehow!

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

        same to me got TLE :D with same solution

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

        The reason for TLE in your case is, if I'm not mistaken, the use of long long in the line for (ll i = k - 1; i >= 2; i--) { whereas the AC solution uses int for i. As a long long takes up more space in the memory in comparison with integer, it also takes longer to perform calculations with it (here: 'i--'). In this case it makes the difference between TLE and AC.

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

          Yes you are right about this .. But I think in general the intended solution is binary search , and the brute force should't pass.

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

            You know, there is an O(1) algorithm (as opposed to the algorithm of binary search), if you want to do some math. My submission, for example, is the implementation of the result: 3390910

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

              Is sqrt really O(1)? I guess you could argue it's really fast, but actually it uses binary search (which is O(log k), not O(sqrt(k))).

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

                Square root is O(log k)? I have always assumed that it's (along with the four arithmetic operations) constant. My bad. Thanks for clearing it up!

                Also, yeah, I meant O(log k) for binary search. I must have been in a hurry to type O(sqrt k) instead.

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

                  I think the sqrt function calculates the square root with fixed relative error, so it's O(1).

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

              Here is a c++ implementation:3396062.

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

    Even this Solution passes. Time:2000 ms :SS

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

Как B решать?

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

    Попробуйте выписать последовательности "лесенкой", так, чтобы j-ый элемент i-ой последовательности находился под (j + 1)-ым элементом (i — 1)-ой последовательности. Сразу увидите закономерность.

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

      Мутная какая-то закономерность получается...

      Такая лесенка? http://pastebin.com/raw.php?i=bM9SYafT

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

        Нет. Для 4 последовательность перестановок будет такой

        1 2 3 4
        2 1 4 3
        1 4 2 3
        4 2 3 1
        

        А лесенка — такой:

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

          А можете поделиться, что Вы сделали с декартовым деревом ?

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

            Есть такая вещь, как декартово дерево по неявному ключу. Такое дерево можно воспринимать как массив со следующими свойствами:

            1) разделить массив длины n на куски длиной k и n-k за O(log n)

            2) склеить два массива в один за O(log N)

            Тогда чтобы переставить элемент с позиции i в позицию j (нумирация с 0) (i<j) нужно сделать следующее:

            1) Разделим весь массив A на две части [tmp, B] так, чтобы |tmp|=j

            2) Разделим tmp на [tmp2, C], |tmp2|=i+1

            3) Разделим tmp2 на [E, D], |E|=i

            4) Склеим массив обратно, но в другом порядке E, C, D ,B и получим то, что надо

            Получается решение за O(N log^2). Более подробно про циклические сдвиги при помощи декартова дерева да и про декартово дерево по неявному ключу можете почитать на хабре http://habrahabr.ru/post/102364/

            Это решение было слишком медленным. Поэтому я думал, как его можно соптимизировать и заметил, что можно элементы заменять, а не перемещать и получил обычное решение.

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

    Если каждый раз бесплатно «сдвигать» массив на одну позицию влево, то переставлять нужно только элементы с номерами, кратными k. Получается перемещений элементов в сумме.

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

Those who like permutations should be quite successful this time :)

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

wow! All System Testing was only 4 minutes!!! Thanks for this great testing!!

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

    probably because there were fewer participants than usual....i myself didn't participate as it was at a different time and i forgot about it...

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

Systest complete within just 2 refreshes :D

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

Fast system test... Great!!!!

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

To those who solved div1 A quickly e.g. within 20 minutes, how did you observe the trick(when n%4>1 return -1)? Thanks.

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

    I think writing backtracking may be useful here.

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

    Use next_permutation to do brute-force first.

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

      With this method, did you manage to quickly find the pattern?

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

        Of course, we can use this method to find all solutions (n <= 13) within a minute. And the pattern is very clear. Try it.

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

    Well I didn't solve it within 20 minutes (and I'm div 2 anyway), but I suppose it's pretty simple:

    Suppose f(i) = pi. We have f(f(i)) = n + 1 - i, so f(f(f(f(i)))) = i. So the permutation is effectively cycles of 4, 2, 1. However, there can be no cycle of 2 (otherwise f(f(i)) = i ≠ n + 1 - i if , and if , then it's a cycle of 1), and the only cycle of 1 can only be done if , so there is at most one cycle of 1. Hence everything is in cycles of 4 except for possibly one element. This means or .

    When in the contest, I visualized it by an n × n board where you put a piece on row i and column j if pi = j, and noticing that everything are the vertices of squares except for probably the middle element.

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

      This is a brilliant idea. However, I still have two questions.

      1. What's the meaning of the cycle? Seems like some kind of abstract algebraic construct like group?

      2. I don't understand your last sentence above(i.e. and noticing...), can you clarify it?

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

        First question:

        Let's see a permutation 2, 3, 1, 4, 5. Note that p1 = 2, p2 = 3, p3 = 1. So from 1, we can get to 2, then to 3, then to 1 again, and it repeats forever. So (1, 2, 3) is a cycle, of period (or you can say "size") 3. p4 = 4, so (4) forms a cycle of period 1. Also note that we can multiply the period of any cycle by simply extending it: (1, 2, 3, 1, 2, 3) forms a "cycle" of period 2 × 3 = 6. I'll refer to a cycle with the smallest period (it cannot be broken into cycles) to be a "proper cycle".

        If f(f(f(f(i)))) = i, then i must belong in a cycle of period 4, or in other words, a proper cycle whose period is a divisor of 4, hence why I can deduce that there can only be (proper) cycles of period 4,2,1. If the problem has been made such that f(6)(i) = i (6 iterations of f), I'd look for proper cycles of period 6,3,2,1.


        Second question:

        See the given permutation 2, 4, 1, 3 in the test case and what I made in my scratch paper:

        .O..
        ...O
        O...
        ..O.
        

        As you can see, I put a piece (O) in row 1, column 2, indicating that p1 = 2. Another one in row 2, column 4: p2 = 4.

        After making this, I noticed that everything is vertices of squares except for probably the middle piece (if there is any).

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

          Elegant explanation, thanks.

          I also have an observation, the correct lucky permutation is some sort of self-descriptive, taking n = 4 for instance, the answer is 2 4 1 3, the 2nd(value) element is the 1st(index) largest, the 4th element is the 2nd largest, the 1st element is the 3rd largest, the 3rd element is the 4th largest.

          But I still don't know the meaning of "everything is vertices of squares", which squares?

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

            Well, you can see that the four pieces in the above grid are vertices of a square, tilted a bit clockwise. Another example for n = 9:

            .A.......
            ........A
            ...B.....
            ......B..
            ....O....
            ..B......
            .....B...
            A........
            .......A.
            

            Observe that A's make a square, and so are B's.

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

              I finally understand. It's just a visual way describing the cycle of size 4 phenomenon. However, it's more precise to use the term "parallelogram" instead of square, isn't it:)

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

                Actually you'll find that all the parallelograms will be squares (try to prove it :) ), but you can use "parallelogram" too if you prefer. Yes, it's my visual way of describing a cycle of period 4.

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

            "I also have an observation, the correct lucky permutation is some sort of self-descriptive, taking n = 4 for instance, the answer is 2 4 1 3, the 2nd(value) element is the 1st(index) largest, the 4th element is the 2nd largest, the 1st element is the 3rd largest, the 3rd element is the 4th largest."

            Of course. The pi-th element is ppi, which by condition is equal to n + 1 - i. It is obviously the i-th largest element.

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

    Number of inversions in a square of a permutation is even, and number of inversions in permutation (N, N — 1, ... , 1) is N(N — 1)/2. It is clearly odd for N = 4k + 2 or 4k + 3.

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

      That's correct. But could you explain the reason using no. of inversions to judge? I don't figure out the connection.

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

        I don't quite figure what is the question about. If a permutation has an odd number of inversions, it can't be a square of any permutation. Therefore for N = 4k + 2, 3 answer doesn't exist.

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

          Actually I don't understand what "square of a permutation" means.

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

            A permutation applied twice consequently, like ppi in the problem statement.

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

            The square of a permutation p is the permutation pp; that is, if originally the permutation p has pi = j, pj = k, then the square of p (which I denote q) has qi = ppi = pj = k.

            For example, if p = (2, 4, 1, 3), its square q is:

            q1 = pp1 = p2 = 4

            q2 = pp2 = p4 = 3

            q3 = pp3 = p1 = 2

            q4 = pp4 = p3 = 1

            I assume that you already know "inversion". The square of any permutation has the property that the number of inversions in it is even. Meanwhile, by the condition of the problem, the square of the sought permutation is equal to the reverse identity permutation (n, n - 1, ..., 2, 1), which has an odd number of inversions for or , so they certainly can't be equal. So there doesn't exist any permutation whose square is the reverse identity permutation if or .

            (EDIT: I keep making long comments and getting "ninja-ed" by people -_- But who cares.)

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

              It's clear. All understood except "the square of the sought permutation is equal to the reverse identity permutation (n, n - 1, ..., 2, 1)", the reason?

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

                Because the problem says that ppi = n + 1 - i.

                If we expand this for all i, we get that (pp1, pp2, pp3, ..., ppn) = (n, n - 1, n - 2, ..., 1); in other words, the square of p is the reverse identity permutation.

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

                  About the parity of square of permutation, is there any proof? Given a permutation, how to decide whether it can be a square of some permutation?

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

                  That's the thing. I only recall that it is an established theorem, but I forgot the proof. Searching in Wikipedia also yields no result (although I think I saw the theorem in Wikipedia).

                  ...Ah ya, here it is. I rephrase the (trivialized in Wikipedia) proof:

                  A permutation can be described by a number of adjacent-element transpositions. For example, (2, 4, 1, 3) can be described by (3, 4), (1, 2), (2, 3):

                  From (1, 2, 3, 4), we transpose elements on indices 3 and 4: (1, 2, 4, 3).

                  We then transpose elements on indices 1 and 2: (2, 1, 4, 3).

                  We finally transpose elements on indices 2 and 3: (2, 4, 1, 3).

                  To prove that we can always do so, it's simple: Just build the permutation we're going to make from the end (or from the front). The above sequence uses this algorithm: It constructs the permutation by first moving 3 to the end (as it's the last element), then 1 to the second-to-last index, and so on. (It's just lucky that after we move the 1, the permutation has been built already.)

                  Now, we note that the number of inversions changes by 1 for every adjacent-element transposition we made, so the parity of the number of inversions is equal to the parity of the number of adjacent-element transpositions we made. So, the parity of a permutation is equal to the parity of the number of adjacent-element transpositions. (This number may vary by simply adding something like (1, 2), (1, 2) as many times as you like, but the parity of the permutation always remain the same.)

                  Now, the composition of two permutations is just the product of their transpositions; in other words, the parity of the composition is equal to the sum of the parities of the two permutations used to build the composition.

                  Now, recall that the sum of two equal parities (even+even or odd+odd) is always even, and the square of a permutation is the composition of a permutation with itself. It's obvious that the parity of a permutation is equal to the parity of the permutation itself, so its square, which is the composition of the permutation and itself, must be even (as it's the sum of two equal parities).

                  I'm not sure how to determine whether a permutation is a square of another permutation or not though. I originally suspected that all even permutations are squares of some permutations, but (2, 1, 4, 3) doesn't satisfy it, so I don't know.

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

                Oops, I got it now. Because P(P(i)) = n-i+1, so applying P(P(*)) on 1 through n, the result is the reversing sequence (n,n-1,...1). Thank you for the reply.

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

    Each of the elements, for which i != n -i + 1, needs to be in the cycle of size exactly 4. So we need to partition all elements (or all but one) into such cycles.

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

    I just didn't prove anything and submitted it on 10th minute :) My prove was like «can it be that there won't be any 2 (mod 4) or 3 (mod 4) tests in pretests? :)»

    (Disclaimer: I use this only on contests)

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

    eg. 5

    1 -> ? -> 5
    2 -> ? -> 4
    3 -> ? -> 3
    4 -> ? -> 2
    5 -> ? -> 1
    

    Case1:

    1 -> ? -> 5 -> ? -> 1 2 -> ? -> 4 -> ? -> 2

    merge above

    1 -> 2 -> 5 -> 4 -> 1

    Case2:

    3 -> 3 -> 3

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

It seems that m = n in all pretests of D. That may explain for some WA on test 7 I think.

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

Nicely done problem setters, that was an absolutely amazing contest. It was worth staying up all night.

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

Congratulations to al13n! 2 victories in a row seems impossible if you're not Petr or tourist but he did it!

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

Как решать С? Наличие большого количества палевных идей по ней сильно отвлекает от строгих рассуждений:)

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

    Одна из достаточно очевидных палевных идей верна. Будем идти с конца со стеком. Если можно (если не запрещено входными данными и позволяет содержимое стека), делаем скобку открывающей, если нельзя — закрывающей.

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

Div 1 B can be solved by the naive algorithm...

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

Подскажите, в чем может быть косяк такого решения B div1. Проследим куда будет переходить элемент, который изначально стоит в позиции i, он либо для текущего k является началом цикла и его следует перенести в конец цикла и увеличить k на 1. Либо i будет ходить на -1 некоторое количество раз, которые вычисляется, как расстояние до текущего начала цикла длины k деленное на 2 (я не пишу про отдельные +- 1).

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

This contest was great! nice problems !

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

Div1 B can be solved by Brute-Force?

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

Если не видишь простейшего упражнения на ФФТ за час, то дело совсем плохо...

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

    Да ну, по-моему, это не совсем упражнение. Во всяком случае, мы не придумывали ее, как обфускацию ффт.

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

      Именно из-за естественности условия я, возможно, так и не придумал решение. Тем не менее, можете посмотреть в дорешке, сколько у меня строчек решения (fft есть преднаписанное)

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

        Не, ну там понятно нечего кодить, кроме ффт, но какая, в принципе, разница?

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

        Ну лично мне кажется, что количество строчек в решении совсем не отражает его сложности. Поскольку последняя складывается не только из сложности реализационной.

        Когда я утверждал эту задачу, она мне показалась крайне красивой.

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

        FFT? А это про какую задачу речь?

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

          Про Е

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

            Можно поподробнее, каким образом оно там применяется и почему?

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

              Построим многочлен, в котором будут коэффициенты 0 или 1, 1 у тех степеней, какие у нас есть пакеты. Возведем его в квадрат. Тогда если у какой-то степени не более m у квадрата не нулевой коэффициент, а у самого многочлена — 0, то ответ NO. Иначе базисом будут те степени, где в квадрате 0, а в самом многочлене 1

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

Question could have been little more clear.. at last i figured.. !!

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

У меня в комнате по Div2 B заходило 10^9 за 2 секунды со скрипом. Люблю сервера КФ :) Надо было TL в секунду ставить.

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

ACRush was in my room today and he became WARush today!!!

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

DIV 1 problem C TLE for using cin...

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

    You should use cin with ios_base::sync_with_stdio(false);

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

      why " ios_base::sync_with_stdio(false) " is makes cin fast ?

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

        This link explains that if this flag is true, it maintains the stream state in both cstdio and iostream so you can mix scanf/cin calls (or printf/cout). Turning it off means cin won't advance stdin, so it does less work to read the input.

        I failed the same problem as olimpo because of being slow with input, but it's nice to discover something new like this...thanks, shervinkh!

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

        In default case, cin and cout don't use buffering. This behaviour enables programmer to use scanf, printf and cin, cout in a program simultaneously. Using ios_base::sync_with_stdio(false) tells cin, cout that you don't want to use scanf, printf with cin, cout. So cin, cout use smart buffering with lots of speed up (more efficient than scanf, printf). I think the latter case should be default. but its the decision of C++'s creators.(may be because of ability to use cin, cout in old c programs that use scanf, printf). for large inputs and outputs (1e5 or 1e6 or more words) that is usual in algorithmic contest program buffered input and unbuffered input differ a lot in the speed. so in every algorthmic contest program it is recommended to use that call in the beginning of the program.

        EDIT: It seems that while i was writing this, Quelloquialism has written the answer.

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

Omg, test "1 K" on problem B Div. 2 kills so many solutions...argghh

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

Div2 C says "any integer i" meets the condition, not "every" or "all". I thing it's not even ambiguous, I did the wrong algorithm because of that :s

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

Nice Contest! For 286A - Lucky Permutation, I'm quite interesting on how to prove that there's no solution when n % 4 equals 2 or 3.

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

!!!!!!!!!!!!!!!!!!!!!!!! The problem D has n, m to read, but read m variables next and read n variables next. The pretest do not contain the situation when n is not equal to m... TAT TAT TAT

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

The input format for 286D - Tourists's is a bit strange - {#queries, #events, events, queries} instead of the more usual {#events, #queries, events, queries}.

Typical: The one time I'm good enough at algorithms to write a correct Div1-D solution, I'm also not literate enough to read a Div1-D statement properly.

Upd1. Looks like Martin also had this problem, and I don't type as fast as him.

Upd2. There are 12 contestants affected: Contest Status (look for WA#7)

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

Could someone help me? my submission 3392032 got TL on test 41 in system testing but my next submission after the contest 3392661 got Accepted I just changed the size of my arrays from 1000005 to 2000005, but I think 1000005 was enough! wasn't it?

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

разборчик бы

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

Enjoyed doing this contest.. Nice questions !! :)

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

drop 3 times in a row

lose IGM title so quickly

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

Is today's contest unrated?

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

good problems! thanks :D

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

How did this person become a candidate master even with a rating of 1555 ?

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

Can anyone please explain this to me :-

For every unsuccesful submission , theres -50 so why does a user gets same score as me when he has 4 unsuccesful submission and i have none and the only question we both have solved is done at same time!

More specifically here , user 'abhinav92003' and i have got same score/rank. Hows this possible ?

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

    You don't get -50 when you eventually don't succeed to solve the problem. Here, you both solved one problem in the same time so you have the same score. He tried to solve B unsuccessfully, you didn't try, I don't think you really deserve a better score than him...

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

      @Nicolas16 , okay i get what you have said. And is there -50 for 'Failed System Tests' ?

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

        What do you mean by Failed System Tests? Actually, when you solve a problem, your points for this problem is equal to the score corresponding to the time you took to solve it, minus 50 points by previous failed submission (unless it is on the first pretest). And there is a minimum so that someone who solve a 500 point problem with 10 wrong submissions don't get 0 but 150.

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

          vote ups

          No , i think you got it wrong . By 'Failed System Tests' , i think @IITian meant that one gets AC during the contest and after contest , at final testing , compiler judges it wrong! For that i think he was asking wether or wether not is -50?

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

            I believe that it doesn't give any penalty, much like unsuccessful problems (submissions that don't pass pretests and the problem is eventually not solved) don't give penalty.

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

    Points are deducted for unsuccessful submission only when you have solved the problem. He has not solved the problem.

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

Can anyone explain me solution of problem D div 2 .

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

Can someone explain me how to approach problem D of division 2?

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

it passed almost 2:30 hours after the contest and still the rates are like before!!! why ?

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

ratings were updated

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

I enjoyed this contest very much! Thanks :)

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

Hi everyone! I realized during the contest that problem B Div. 1 could work using a brute-force approach, however I was unable to maintain the cycles without moving too many elements at once. Could anyone who solved the problem correctly give me a hint on how I could achieve this?

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

    If you look at some of the accepted solutions you will notice that you can think of each move which is performed as follows: Let's say that the elements which are the first in their blocks are on positions P(1), P(2), ..., P(Q) (obviously, P(1)=1). Then, instead of thinking about cyclic shifts, imagine that all the elements stay in place, except:

    • the element from position P(Q) goes to position N+1

    • the element from position P(Q-1) goes to position P(Q)

    • ...

    • the element from position P(1) goes to position P(2)

    This way, you only get to move the elements on the positions P(1), ..., P(Q), and your sequence can now be found on the positions 2, ..., N+1 (instead of 1,...,N, as in the beginning). At your next move you will simply have to consider the fact that your sequence does not start at position 1.

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

I got hacked in Div 2 A . this is my solution , can anyone tell me the test case or my mistake

int main() { char a[6][6],c=0;

for(int i=1;i<=4;++i)
{for(int j=1;j<=4;++j)
cin>>a[i][j];}

for(int i=1;i<=4;++i)
for(int j=1;j<=4;++j)
{   int c=0;
    if(a[i][j]==a[i+1][j])
    c++;
    if(a[i][j]==a[i][j+1])
    c++;
    if(a[i][j]==a[i+1][j+1])
    c++;
    if(c==3 || c==2)
    {cout<<"YES";return 0;}
}
cout<<"NO";

}

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

Most of the times i see the code of a problem not solved by me , i notice that around 90% of the code of 90% coders is same . e.g in Div B 2nd problem .

I m a newbie coder , plz tell me something that i m missing .

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

please tell me anyone...>>>>>> at first i submit the problem,then accept. but it hacked. after i submit the problem then accept. when the code check,then all correct. but when given the rating ,show solve is 0; when i see my submission then see that skipped. what's the of the side.not only today,but also before a day can happen. i am very very dishearted.....>>>>>

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

    Maybe rating is not that important, right? The things that you learned is what matters.

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

editorial ?

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

No editorial yeT..!! :(

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

When will the editorial be published?

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

    I think, it will appear tomorrow. We have editoral in russian, but we haven't translated it yet.

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

Can somebody tell me some more problems like Lucky Permutation to practice.

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

Мне очень-очень стыдно, но как решается 287B - Трубопровод ?

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

    Нам нужно набрать сумму n из слагаемых от 2 до k, каждое слагаемое можно брать не более одного раза. Причем сумма зависит не только от самих слагаемых, но и от их количества, то есть n=k1+k2+...+kx-(x-1). Можно заметить, что если уменьшить каждое слагаемое на единицу(т.е. уменьшить k на 1), то n=k1+k2+...+kx+1. Чтобы избавиться от +1, очевидно можно уменьшить значение n на 1. Теперь наша задача сводится к нахождению минимального количества слагаемых от 1 до k, чтобы набрать просто сумму n. Это можно делать жадно: просто брать максимальное доступное слагаемое, и отнимать от n, пока n не станет <= чем текущее максимальное неиспользованное значение k. Однако это слишком долго. Осталось понять, что можно подобрать такое максимальное слагаемое x, что n-sum(от k до x)<=sum(от k-x до 1) бинарным поиском, где sum-просто сумма арифметической прогрессии.

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

please see comments of user: SROPRO ! I think He's Activity isn't good for this site!

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

can't connect the editorial ...would you publish the editorial at codeforces blogs

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

In 287E - Main Sequence can {-1,-1} be correct bracket sequence?

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

There is a problem in the explanation of the C problem in the editorial. You must insert {2,n+4} at the beginning and {1,n+3} at the end as the second step to form a (n+4)-lucky permutation from n-lucky permutation.

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

The editorial page is not working