I’m confused how the PIE solution works for this problem, explained in here. I understand what the solution by Mark Chen is doing but I don’t get what the PIE code is doing in Ben Qi’s solution.
Also, I thought the style of counting in Mark’s solution is really interesting (counting ways for ALL cycles to be divisible by something, and using that to figure out ways for NONE of the cycles to be divisible by something), are there any problems that you would recommend that also use similar counting ideas (I guess just interesting PIE problems)?
(Also, I wasn’t able to get a Java solution to run under the time limit. I’m ok with that, I’m just trying to learn the concepts, but if anyone has a Java solution could you share it so I can see what things I might be doing inefficiently).
In my solution, dp[i] is the sum of (-1)^{\text{(\# of cycles in }p)+1} over all permutations p of length iz such that all cycles in p have length divisible by z. You should verify that this results in each permutation with at least one cycle with length divisible by z being counted exactly once.
Hmm, I’m still not understanding why that provides the right coefficients.
And just to double-check (correct me if I’m wrong here), when summing res = ad(res,mul(choose[n][n-i*z],dp[i])); to get the final answer, the choose function is really {n \choose n-iz}(n-iz)!, which is just giving us the ways to pick the group of iz to be partitioned into multiples of z and then arrange the remaining values in any way. So the contribution of dp[i] to the term is somehow making the overall result count things only once.
The way I was thinking about it, would be to just think about alternating signs, so we would have instead computed dp[i] in the same way as you have, except using addition instead of subtraction and 1 in the base case, so that dp[i] is the ways to partition iz into groups that are multiples of z. And then computing the answer (ways to have some group of a multiple of z), we have ans = \sum_{i=1}^{n/z} (-1)^{i+1} {n \choose n-iz}(n-iz)! \ dp[i]. Why isn’t this right?
I’m having trouble understanding how you can frame this as PIE. So right now I’m thinking that the property of the elements (in the set of all permutations) that we want is: “total length of cycles that are multiples of z is at least 1z.” So we want to apply PIE on this property.
But that seems kind of clunky. So we want to count ways to have a cycle of length 1z appear somewhere, then remove the ways to have 2z total cycle length (either as 2z or z, z), and so on. Is there a better way of thinking about this?
Well, you still haven’t addressed what I wrote above. A single cycle of length 2z would be counted 0 times in “ways to have a cycle of length 1z appear somewhere,” and 1 time in “ways to have 2z total cycle length,” so you wouldn’t be counting it the correct number of times.
Or I get that the formula I wrote won’t count it correctly, but I’m not sure how to properly add the signs to count things once. I think I’m getting stuck trying to reverse engineer why the formula you used works, rather than directly reasoning it. I can sort of see how the signs line up, but it feels muddled still.
Ohh, wait this is beautiful! In case anyone else gets stuck on this too, here’s the way of thinking that made it click for me:
We can properly add the negative signs by considering things by induction. For any permutation with just a single cycle of length gz, for some g > 0, we should count this once.
Now, for a permutation with two distinct cycles of length g_1z, g_2z, we now have over counted due to the previous assignment of signs, since we will have counted permutations with a cycle of g_1z and permutations with a cycle of g_2z independently once. So, in classic Venn Diagram fashion we subtract out any permutations with both g_1z, g_2z cycles. In general, we can imagine different partitions of the permutation into cycle lengths as being built up with alternating signs as we peel away one cycle at a time (so that for a permutation with k cycles, we will want to get a sign opposite of a permutations with k-1 cycles).
Then, within each dp[i], we’ll have a variety of different permutations with different numbers of cycles, so the PIE is really applied on the number of cycles, not the length! I was getting confused here, but if we think in terms of the contribution from any given partition of cycles (g_1z, g_2z, \dots, g_kz, we’ll see that it adds all permutations with 1 cycle, subtracts those with 2, etc.)
Oh also, interestingly the PIE solution sped it up enough to pass the N = 7500 cases.