HolkinPV's blog

By HolkinPV, 11 years ago, translation, In English

285A - Slightly Decreasing Permutations

As the answer you can print such permutation: n, n - 1, ..., n - k + 1, 1, 2, ..., n - k. For example, if n = 5, k = 2, then the answer is: 5, 4, 1, 2, 3. If k = 0, you should print 1, 2, ..., n. Such solution can be written in two loops.

285B - Find Marble

It is known that a permutation can be considered as set of cycles. The integer i moves to p[i] for all i (1 ≤ i ≤ n). You can start moving from integer s along the cycle. If you find integer t, then print the length of the path. If you return to s, then print  - 1.

285C - Building Permutation

The solution of the problem is rather simple. Sort all integers a and then make from integer a[1] integer 1, from integer a[2] integer 2 and so on. So, integer a[i] adds to the answer the value |a[i] - i|. The answer should be count in 64-bit type. You can simply guess why such solution is correct.

285D - Permutation Sum

For a start, describe bruteforce solution. Firstly, we will always assume, that a is identity permutation, that is a[i] = i. In this case, the answer should be multiplied by n!. Or in other way your bruteforce will not be counted. Secondly, using our bruteforce we can see, that for even n the answer is 0.

What do you also need to get accepted? First case is to calculate answers for all n on your computer and write them in constant array. In other words you can make precalc. Second case is to make you solution faster. The soltuion using meet-in-the-middle idea works fast for n ≤ 15. If you remember that for even n answer is 0 then you can get accepted using such solution. But other simple bruteforces and dynamic programmings on maps work slower than 3 seconds.

285E - Positions in Permutations

  • Vote: I like it
  • -29
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it +29 Vote: I do not like it

We want E, please :(

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

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

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 9   Vote: I like it +36 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          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 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    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.

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

      Can you please explain this — "c = a+b (mod n), then sum of elements of c is also 2*(n-1)n/2 (mod n) = 0"

»
11 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

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

      :'( :'(

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

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

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

            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 years ago, # ^ |
    Rev. 2   Vote: I like it -29 Vote: I do not like it
    printf("%I64d\n",0ll);
    

    is expected.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    anti-quicksort test

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    As I understood from here http://msdn.microsoft.com/en-us/library/aa311213(v=vs.71).aspx C# uses QuickSort. QuitSort does O(n2) in worst case. So you should randomly shuffle array before executing Arrays.sort().

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

      Thank you! I'll make a note of that, yet it still seems that using C# here was a disadvantage.

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

        Nah, its the same for Java. Just remember now for future contests :)

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

          Same problem with java. But I found a really interesting solution in my contest room, just swap some elements and it runs in about 300-400ms. Code here: http://codeforces.com/contest/285/submission/3367901

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

          i did nothing about the original sequence, and still got ac in java 6

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          for the problem C i used long array in java 6. but it took TLE. Arrays.sort() took so much time to sort long array.

          then I saw someone used Long array instead of long array. I used it and it finished under 1.5s.

          Can anyone explain why this different ??

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

            Arrays.sort on Objects uses merge sort which has a wost case of O(n*log(n)). Arrays.sort on primitives uses quicksort which has a worst case of O(n^2) This happens if you build the array in a certain manner otherwise quicksort on average is also O(n*log(n)).

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it +17 Vote: I do not like it

      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 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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 years ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

deleted

»
11 years ago, # |
  Vote: I like it +19 Vote: I do not like it

"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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you explain problem D in detail ?

»
11 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is problem D a mathematic problem ?

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

      Maybe we'll have a faster solution by using combinatorial mathematics theory. Or somebody proves it's impossible.

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WRITE PROBLEM E TUTORIAL !!!

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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