### HolkinPV's blog

By HolkinPV, 11 years ago, translation,

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

• -29

| Write comment?
 » 11 years ago, # |   +29 We want E, please :(
•  » » 11 years ago, # ^ |   +3 State Compress Dynamic Programming ... O(n^2 2^3) ...
•  » » » 11 years ago, # ^ |   +2 What dynamic? I don't know what to do with positions, that we haven't taken.
•  » » » » 11 years ago, # ^ | ← 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 years ago, # ^ |   +5 My idea in problem E is the same as witua :D
•  » » » » » 11 years ago, # ^ |   +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 years ago, # ^ | ← 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 likeres[i] ~ R[n][i][][] , right?).Else seems more-less understandable =)Thank you
•  » » » » » » 11 years ago, # ^ |   +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 years ago, # ^ |   +2 could you explain your solution ? and what is State Compress Dynamic Programming ?
•  » » 11 years ago, # ^ |   +9 no offence bro, but i'm still scratching my head reading D!!
 » 11 years ago, # |   0 Can you proof D-Permutation Sum ? Pls...
•  » » 11 years ago, # ^ |   -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 years ago, # | ← Rev. 2 →   +13 Can Anyone Describe Meet-In-The-Middle Idea For D, Please?
•  » » 11 years ago, # ^ | ← Rev. 2 →   0 can anyone please give a link to some problems related to 'Meet in the middle' idea?
•  » » 11 years ago, # ^ |   +1
•  » » » 11 years ago, # ^ |   0 I'm sorry. I thought just about idea "Meet-In-The-Middle"
•  » » 11 years ago, # ^ |   -12 have you taken Cryptography course? if yes. then it is so easy for you :)
•  » » » 11 years ago, # ^ |   0 would you explain it in more detail?? thanks!!
•  » » 11 years ago, # ^ |   +4 Are you sure that meet in the middle solution exist for problem D? I thought about that problem this way but didn't succeed.
•  » » » 11 years ago, # ^ | ← Rev. 4 →   +7 yes there exist meet in the middle solution with O(C(n,n/2)*(n/2)! ). for maximal N (15) its about 32 432 400 . but my solution needs 7 sec for 15 (I think its because of constant factor)edit: it does about 518 918 400 . but even that is not too mach for codeforces if constant is small..
•  » » » » 11 years ago, # ^ |   +3 Thanks a lot :)
•  » » » » » 11 years ago, # ^ |   +6 if you cant get my code I can say you how it works but not in english..
•  » » » » » » 11 years ago, # ^ |   0 No thanks, it's clear :)
•  » » » » 11 years ago, # ^ |   0 Oh! i had that solution O(C(n, n/2)*(n/2)!) but i thought it takes too long for N=15
 » 11 years ago, # |   +2 At A, if k = 0, shouldn't it be 1, 2...n-1, n? :o
•  » » 11 years ago, # ^ |   0 Yes, fixed)
 » 11 years ago, # | ← 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 years ago, # ^ |   0 Set numbers one by one and every step check if the answer still can be correct.
•  » » 11 years ago, # ^ |   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 years ago, # |   +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 years ago, # ^ | ← 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.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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"
•  » » » » 5 years ago, # ^ |   0 Ok i got it Thanks
 » 11 years ago, # | ← 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 years ago, # ^ |   +19 0 has type int, but your printf was trying to print long long. So the behavior is undefined.
•  » » » 11 years ago, # ^ |   0 :'( :'(guess I will never use printf again, thank you :-)
•  » » » » 11 years ago, # ^ | ← 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 years ago, # ^ |   +5 cin isn't so slower as you think, if you use it in right way.
•  » » » » » » 11 years ago, # ^ |   +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 years ago, # ^ | ← Rev. 2 →   -29 printf("%I64d\n",0ll); is expected.
 » 11 years ago, # |   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 years ago, # ^ |   +1 anti-quicksort test
•  » » 11 years ago, # ^ |   +1 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, # ^ |   0 Thank you! I'll make a note of that, yet it still seems that using C# here was a disadvantage.
•  » » » » 11 years ago, # ^ |   0 Nah, its the same for Java. Just remember now for future contests :)
•  » » » » » 11 years ago, # ^ |   0 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, # ^ |   0 i did nothing about the original sequence, and still got ac in java 6
•  » » » » » 11 years ago, # ^ | ← Rev. 2 →   0 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, # ^ |   0 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, # ^ |   +1 Yeah. you're right. My solution http://codeforces.com/contest/285/submission/3376657
 » 11 years ago, # |   +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 years ago, # ^ |   -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 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # |   0 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, # ^ |   +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 years ago, # |   +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 years ago, # |   0 can anyone please explain how to precalculate the answers for odd n in Problem D
•  » » 11 years ago, # ^ |   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 years ago, # | ← Rev. 2 →   -10 deleted
 » 11 years ago, # |   +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 years ago, # ^ |   +2 Agree with you!!!
 » 11 years ago, # |   +3 Can you explain problem D in detail ?
•  » » 11 years ago, # ^ |   0 Agree!!
 » 11 years ago, # | ← 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 years ago, # |   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 years ago, # ^ |   0 How is problem D a mathematic problem ?
•  » » » 11 years ago, # ^ |   0 Maybe we'll have a faster solution by using combinatorial mathematics theory. Or somebody proves it's impossible.
 » 11 years ago, # |   +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 years ago, # ^ |   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 years ago, # |   0 WRITE PROBLEM E TUTORIAL !!!
 » 11 years ago, # |   0 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 →   +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 years ago, # | ← 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 years ago, # |   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