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. Такое решение можно написать в два цикла.
Известно, что перестановку можно представить в виде множества циклов. Число i переходит в число p[i] для всех i (1 ≤ i ≤ n). Можно было начать двигаться из стартового числа s по циклу до тех пор, пока мы не дойдем до конечного числа t, либо же не вернемся назад в s. Если мы вернулись в начало, нужно вывести - 1, иначе вывести длину пути.
У этой задачи решение очень простое. Нужно отсортировать последовательность 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 было равносильным по количеству операций. Различные подобные рассуждения приводят к решению, описанному выше.
Опишем сначала переборное решение. Во-первых, всегда будем считать, что перестановка a тождественная, то есть a[i] = i. В таком случае, полученный ответ просто домножим на n!. В противном случае ваш перебор не досчитается. Во-вторых, с помощью нашего перебора заметим, что для четных n ответ равен 0.
Что теперь нужно сделать, чтобы сдать задачу. Первый вариант — это посчитать на вашем компьютере все ответы и записать их в константый массив, иначе говоря сделать прекалк. Вариант второй — пытаться ускорять ваше решение. Решение, использующее подход meet-in-the-middle успевает для n ≤ 15. Поскольку для четных n ответ 0, то такое решение также проходит. С другой стороны, другие простые переборы и динамики на map-ах в 3 секунды не уложились.
У вас опечатка. В задаче А если k = 0, нужно вывести 1, 2, 3, ..., n.
И не могли бы вы пояснить, как работает решение с meet-in-the-middle?
А можно ссылку на код решения по Д чем нибудь кроме константного массива?
вот, пожалуйста!
Ну да, все-то мы посчитали честно, кроме n=15. А почему? Потому что на n=15 свалится.
150347555
=====
Использовано: 9999 мс, 312128 КБ
We want E, please :(
State Compress Dynamic Programming ... O(n^2 2^3) ...
What dynamic? I don't know what to do with positions, that we haven't taken.
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.
My idea in problem E is the same as witua :D
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.
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
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")
could you explain your solution ? and what is State Compress Dynamic Programming ?
no offence bro, but i'm still scratching my head reading D!!
Как и следовало ожидать, Е-шки в разборе нет( Ждем ее с нетерпением!
Это нормально, что у тебя разные аватарки здесь и в профиле?))
Я прост только что поменял ее, видимо не обновилась
UPD: Теперь совпадают
Can you proof D-Permutation Sum ? Pls...
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.
Can Anyone Describe Meet-In-The-Middle Idea For D, Please?
can anyone please give a link to some problems related to 'Meet in the middle' idea?
http://www.infoarena.ro/blog/meet-in-the-middle
I'm sorry. I thought just about idea "Meet-In-The-Middle"
have you taken Cryptography course? if yes. then it is so easy for you :)
would you explain it in more detail?? thanks!!
Are you sure that meet in the middle solution exist for problem D? I thought about that problem this way but didn't succeed.
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)
http://codeforces.me/contest/285/submission/3381386
edit: it does about 518 918 400 . but even that is not too mach for codeforces if constant is small..
Thanks a lot :)
if you cant get my code I can say you how it works but not in english..
No thanks, it's clear :)
Oh! i had that solution O(C(n, n/2)*(n/2)!) but i thought it takes too long for N=15
At A, if k = 0, shouldn't it be 1, 2...n-1, n? :o
Yes, fixed)
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?
Set numbers one by one and every step check if the answer still can be correct.
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.
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.
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.
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"
Ok i got it Thanks
I got a wrong answer on D just because of printf !!
how come does this line
produce 1174031664003678208 !!
I don't know what kind of compilers are you using, I'm really frustrated :(
3373779
0has typeint, but your printf was trying to printlong long. So the behavior is undefined.:'( :'(
guess I will never use printf again, thank you :-)
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");
cinisn't so slower as you think, if you use it in right way.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.
is expected.
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?
anti-quicksort test
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().
Thank you! I'll make a note of that, yet it still seems that using C# here was a disadvantage.
Nah, its the same for Java. Just remember now for future contests :)
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.me/contest/285/submission/3367901
i did nothing about the original sequence, and still got ac in java 6
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 ??
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)).
Yeah. you're right. My solution http://codeforces.me/contest/285/submission/3376657
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...
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...
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.
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.
По D даже путевый прекалк не нужен) http://oeis.org/search?q=3%2C15%2C133%2C2025&language=english&go=Search
Проще вбить прекальк для всех нечетных, чем сначала для нескольких, а потом бежать в oeis.
For Problem B: There is no need that we return to s. For example: 5 1 5 2 3 4 2 5
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!!
Как доказать, что в D для любого четного n ответ 0?
http://codeforces.me/blog/entry/7093#comment-127153
Could someone please give me some idea on how to generate the array using meet in the middle approach for problem D? Thank you.
can anyone please explain how to precalculate the answers for odd n in Problem D
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...
deleted
"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
Agree with you!!!
Can you explain problem D in detail ?
Agree!!
Не люблю задачи на прекальк. Особенно в Д. Особенно с решением в OEIS
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 .
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.
How is problem D a mathematic problem ?
Maybe we'll have a faster solution by using combinatorial mathematics theory. Or somebody proves it's impossible.
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
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.
WRITE PROBLEM E TUTORIAL !!!
I would appreciate it if someone explain the details of using DP or meet-in-the-middle approach to solving problem D.
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.
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.
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
I am in a difficulty with problem "B"...Someone please simplify the problem or explain the solution.