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

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

285A - Немного убывающие перестановки

В качестве ответа можно было предложить такую перестановку: n, n - 1, ..., n - k + 1, 1, 2, ..., n - k. Например, если n = 5, k = 2, то ответ: 5, 4, 1, 2, 3. Если k = 0, нужно вывести 1, 2, ..., n. Такое решение можно написать в два цикла.

285B - Найди шарик

Известно, что перестановку можно представить в виде множества циклов. Число i переходит в число p[i] для всех i (1 ≤ i ≤ n). Можно было начать двигаться из стартового числа s по циклу до тех пор, пока мы не дойдем до конечного числа t, либо же не вернемся назад в s. Если мы вернулись в начало, нужно вывести  - 1, иначе вывести длину пути.

285C - Получаем перестановку

У этой задачи решение очень простое. Нужно отсортировать последовательность a, а затем первое число свести к числу 1, второе к числу 2, и так далее. Число a[i] добавит к ответу величину |a[i] - i|. Ответ нужно считать в 64-битном типе данных.

Почему это решение верно? Разумеется, до этого легко догадаться. Чтобы в этом убедиться, попробуем это показать методом от противного. Рассмотрим, например, числа x, y, z. Пусть x < y < z и мы хотим свести число x к числу z вместо числа y. Однако, после некоторого количества операций  + 1 число x окажется равным y. После этого можно считать, что мы будем сводить первоначальное число y к числу z, а первоначальное число x к числу y. То есть, сведение числа x к числу z было равносильным по количеству операций. Различные подобные рассуждения приводят к решению, описанному выше.

285D - Сумма перестановок

Опишем сначала переборное решение. Во-первых, всегда будем считать, что перестановка a тождественная, то есть a[i] = i. В таком случае, полученный ответ просто домножим на n!. В противном случае ваш перебор не досчитается. Во-вторых, с помощью нашего перебора заметим, что для четных n ответ равен 0.

Что теперь нужно сделать, чтобы сдать задачу. Первый вариант — это посчитать на вашем компьютере все ответы и записать их в константый массив, иначе говоря сделать прекалк. Вариант второй — пытаться ускорять ваше решение. Решение, использующее подход meet-in-the-middle успевает для n ≤ 15. Поскольку для четных n ответ 0, то такое решение также проходит. С другой стороны, другие простые переборы и динамики на map-ах в 3 секунды не уложились.

285E - Позиции в перестановке

Разбор задач Codeforces Round 175 (Div. 2)
  • Проголосовать: нравится
  • -29
  • Проголосовать: не нравится

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

У вас опечатка. В задаче А если k = 0, нужно вывести 1, 2, 3, ..., n.

И не могли бы вы пояснить, как работает решение с meet-in-the-middle?

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

А можно ссылку на код решения по Д чем нибудь кроме константного массива?

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

    вот, пожалуйста!

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

      Ну да, все-то мы посчитали честно, кроме n=15. А почему? Потому что на n=15 свалится.

      150347555

      =====

      Использовано: 9999 мс, 312128 КБ

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

We want E, please :(

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

    State Compress Dynamic Programming ... O(n^2 2^3) ...

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

      What dynamic? I don't know what to do with positions, that we haven't taken.

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

        Just do res[i] *= (n-i)!, where res[i] is a result with i good position without some position (such that, as you say, "we haven't taken"). Now res[i] may contain some permutations with more than i good positions. But consider that you have correctly caclulated res[i+1], res[i+2], ..., res[n]. Then each of res[i+1] permutations was overcounted in res[i] exactly С(i+1, i) times, each of res[i+2] — C(i+2, i) times and so on. After that you will also have res[i] caclulated correctly.

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

          My idea in problem E is the same as witua :D

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

          Thanks for such a nice solution. It's sad that I came so close but didn't figure out how to exclude the overlapping part.

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

          Could You explain dynamic programming part more precisely, please. I mean part where your in process of creating res[] array.

          (as I understood, according to your code smth like

          res[i] ~ R[n][i][][] , right?

          ).

          Else seems more-less understandable =)

          Thank you

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

            Can you explain it a bit more? I really don't understand the english from the sentence:

            Just do res[i] *= (n-i)!, where res[i] is a result with i good position without some position (such that, as you say, "we haven't taken")

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

      could you explain your solution ? and what is State Compress Dynamic Programming ?

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

    no offence bro, but i'm still scratching my head reading D!!

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

Как и следовало ожидать, Е-шки в разборе нет( Ждем ее с нетерпением!

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

    Это нормально, что у тебя разные аватарки здесь и в профиле?))

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

      Я прост только что поменял ее, видимо не обновилась

      UPD: Теперь совпадают

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

Can you proof D-Permutation Sum ? Pls...

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

    If you mean in the "proof" why answer for even n-s is 0, I will explain it here.

    First of all, let's subtract 1 from each permutation. Than our problem becomes: How many permutations a,b exist for {0,1,...n-1} such that the sequence ((a[i]+b[i])%n, 1<=i<=n) is also a permutation of (0, 1, ... , n-1). Assume we have permutations a,b. Than, if ((a[i]+b[i])%n) is also a permutation, considering modulo n, we have: n(n-1)/2 = 1+2+...+n = (sum_of_all (a[i]+b[i])%n ) = (sum_of_all(a[i]) + (sum_of_all(b[i])) = (0+1+...+(n-1)) + (0+1+...+(n-1)) = n(n-1) = 0 (mod n). So, n(n-1)/2 = 0 (mod n), which simply implies that n should be odd.

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

Can Anyone Describe Meet-In-The-Middle Idea For D, Please?

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

At A, if k = 0, shouldn't it be 1, 2...n-1, n? :o

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

I can't understand how one can use brute-force for n = 15 because it'll take O(n!) operation which for n = 15 it'll need almost three hours to be done. Is there another approach?

Edit: It seems there is another solution for this problem. The answer for odd n when we fix our first permutation, is equal to " Number of toroidal semi-queens on a (2n+1) X (2n+1) board". May somebody explain why?

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

    Set numbers one by one and every step check if the answer still can be correct.

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

    I guess you looked up sequence A006717 in OEIS. It's also "the number of good permutations on 2n+1 elements", which seems more related to this problem. Thats how I solved the problem. Just computed the first few examples by bruteforce, looked up in OEIS and copied the sequence into my code. No need to optimze the brute-force in any way for N=15 ... actually I only calculated until n=7 and had enough trust, that i found the right sequence.

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

For problem D, it is mentioned that answer would be equal to 0 if n is even. Can someone tell my why this is true ? I am thinking on the lines that there would be some number that we won't be able to generate when the length of permutations is even but haven't succeeded as of yet.

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

    Consider the permutations on set 0,...,n-1, and let's work modulo n. The sum of any permutation is 0+1+...+n-1 = (n-1)n/2 (mod n), which is n/2 because n is even. But if a,b,c are permutations and c = a+b (mod n), then sum of elements of c is also 2*(n-1)n/2 (mod n) = 0, a contradiction.

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

I got a wrong answer on D just because of printf !!

how come does this line

printf("%I64d\n", 0);

produce 1174031664003678208 !!

I don't know what kind of compilers are you using, I'm really frustrated :(

3373779

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

    0 has type int, but your printf was trying to print long long. So the behavior is undefined.

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

      :'( :'(

      guess I will never use printf again, thank you :-)

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

        No , its better to use printf. It's a lot faster than cin . If you want to print a constant just do it like this : printf("0 \n");

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

          cin isn't so slower as you think, if you use it in right way.

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

            Well it sure makes a big difference if the output has many lines and you use endl instead of "\n": it flushes the output after every line, and that can easily get TLE.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -29 Проголосовать: не нравится
    printf("%I64d\n",0ll);
    

    is expected.

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

I coded problem 'C' correctly, but it seems that the C# Sort function was not fast enough to finish within the 2 second time limit for test #23. Is it possible to appeal this, or will I be penalized for using C# language?

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

Solution for problem C: «You can simply guess why such solution is correct.»

Can you give me any hint on how to prove this? I had to take that for granted during the contest, but was wondering what is the most elegant way to prove it...

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

    since all numbers from 1 to n must be there (in any order), the number of changes done are minimized when the lowest input is converted to the lowest output, and so on, till the highest input to the highest output! if you are not yet convinced, try it for test cases for upto n=10 or 15...

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

      This is not answering his request for a proof.

      If you have |a[x] — i| + |a[y] — j| in your sum, where i > j but a[x] < a[y], then swapping i and j will make the sum not larger (try it). So if you have any sequence which isn't sorted, then it you can transform it into a sorted sequence using these inversions, and you will get a result which is no worse.

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

    Take a random i, the amount needed to add to the total sum is abs ( i + 1 — a[i] ), assume that it is not the minimum, and try instead to use some other possibility of a[i], if you take smaller number, you immediately see that you obtain bigger sum, in the case a[k] = a[i] for some k < i, it's still true that the minimum is the firstly calculated one because the amount is the same). Now suppose you take a number of the right of a[i] say a[k] for some index k > i (greater one), the differences abs((i+1)-a[k])) and abs((k+1)-a[i]) in the best case will be equal ( otherwise the first calculated sum is always less) and still we don't have improvement. So we conclude that the best choice is to use abs ( i + 1 — a[i] ), keeping in eye that the elements of a[] are from [1:n] and a[] is sorted.

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

По D даже путевый прекалк не нужен) http://oeis.org/search?q=3%2C15%2C133%2C2025&language=english&go=Search

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

    Проще вбить прекальк для всех нечетных, чем сначала для нескольких, а потом бежать в oeis.

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

For Problem B: There is no need that we return to s. For example: 5 1 5 2 3 4 2 5

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

    yeah even i thought about this and felt a bit disappointed after i had submitted and locked my solution, but the problem statement says that all Pi's are distinct so he cant loop around any cycle containing neither the start nor the end point!!

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

Как доказать, что в D для любого четного n ответ 0?

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

Could someone please give me some idea on how to generate the array using meet in the middle approach for problem D? Thank you.

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

can anyone please explain how to precalculate the answers for odd n in Problem D

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

    Just search.. Notice that you only need to calculate b array for a[]={1,2,3,...,N} Then multiply this result with N! I was wondering how to solve this problem without precalculation but got no clue...

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

deleted

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

"The soltuion using meet-in-the-middle idea works fast for n ≤ 15" " But other simple bruteforces and dynamic programmings on maps work slower than 3 seconds." Could you explain them?:) I think the tutorial should be more detailed and accurate

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

Can you explain problem D in detail ?

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

Не люблю задачи на прекальк. Особенно в Д. Особенно с решением в OEIS

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

I am seriously hoping that codeforces does something for better tutorials . I am scratching my head for problem 4 and 5 with only precomputed codes in front of my eyes. Something like codechef tutorials would be very good .

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

I don't think problem D is suitable for algorithm competition. However, thank the author of the problem. It's a really good mathematic problem.

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

Problem D: how i can get ll arr[]={1, 3, 15, 133, 2025, 37851, 1030367, 36362925}; please anyone help in post details; every coder do the same way,but i can't understand. Al..helal

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

    Just do the normal brute force recursion 2^n*2^n*n (memoize in a map if u want) compute the answer offline for all 1<=n<=15 and u will get a similar array with the actual answers. I believe that the array u presented doesn't account for the factorial thing so u should account for it somehow before u print the answer.

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

WRITE PROBLEM E TUTORIAL !!!

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

I would appreciate it if someone explain the details of using DP or meet-in-the-middle approach to solving problem D.

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

Where is the official solution for E?

this is the worst editorial I've ever seen no official solution for E and no explanation how to use meet in the middle for D.

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

E can also be solved more generally using rook polynomials.

First, compute the rook polynomial R(x) = r[n]x^n + r[n-1]x^(n-1) + ... + r[0]. The coefficients of R can be computed with an O(N^2) dp.

We define the hit number h[k] = number of ways to place the rooks such that exactly k of them are in the restricted positions (i.e. number of permutations such that there are exactly k good poistions). In other words, h[k] is the answer to this problem.

Define the hit polynomial H(x) = h[n]x^n + h[n-1]x^(n-1) + ... + h[0]

There's the following relationship between H(x) and the rook coefficients:

H(x) = sum(r[i] * (n-i)! * (x — 1)^i, i = 1..n)

There's a nice proof for the above relationship here http://www.math.ucsd.edu/~remmel/files/Book.pdf.

Given R(x), H(x) can be computed in O(N^2) using the above identity.

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

How should we precompute aray for odd numbers in problem D? I am getting a TLE if done naively and have no clue how to optimise it