Thanks =)

It is ctrl+B or alt+B, I don't remember which one.

One may speed up the O(nk²) dynamic programming solution by noticing that at any stage of the DP the answer for x = p₁^α₁·...·p_l^α_l depends only on the multiset of numbers (α₁, ..., α_l) and there's only about a hundred different multisets for k ≤ 50000.

UPD. For the n'th stage

The first term does not depend on b, the transitions in the second term depend only on the structure of the divisors of b so the numbers with equivalent structure can be grouped together to speed up the counting.

Denote z_n correct sequences. z_n = kⁿ - w_n, where w_n for incorrect sequences. , where cs_i is the number of sequences of length i + 1 that each pair of adjacent values is bad (so x, x·k₁, x·k₁·k₂, ..., x·k₁... k_i). The last thing can't have the size more than logn, so it can be calculated by simple dp.

Overflows in the first problem (my solution also was challenged with overflows).

In Div1 Easy, there were also solutions which assumed the answer is always a consecutive segment in the sorted array. Such solution passes all examples.

isn't it O(k³)?

I think memory is O(k * k) so if k is reasonably large for example : k = 50000, memory usage is more that 256 MB

First note that for an array to be k-smooth it has to satisfy that the minimum value of the array times k is bigger than or equal to the maximum value. In the case of the problem that min and max is substituted by min and max differences.

I solved it by first sorting the array and then considering all pairs (i, j) where j > i, choosing these as the maximum and minimum, the max difference since it's sorted is now a[j]-a[i]. Now we can greedily choose which elements in the range that we can include in our set, start from i find the first value (let's say it's at position p) iterating towards j that satisfies that (a[p]-a[i])*k >= a[j]-a[i], you know as soon as you reach this that all elements beyond it will also satisfy this because the array is sorted. Then make your new anchor this point and keep iterating forwards until you hit the end.

The proof for the greedy method is something along the lines of it's always better picking the first one because picking a later one would make at least as many values in front of it invalid to pick because the array is sorted.

Any questions to my explanation?

Here is a generally straightforward solution: let's fix smallest difference in our set (n^2 ways) and smallest element (n ways). Now we can implement n^2 DP — what is maximum size of valid subset with largest element being equal to x; you have n states and n transitions from each state (trying new largest element and checking that it's not too small when compared to last element in our set and not too large when compared to smallest element). Resulting complexity will be O(N^5). Not the best one, but at least it is clearly correct and you don't need to prove any assumptions/greedy ideas.

Hmm, the title of the problem (CliqueParty) misled me into thinking it's a graph problem. I actually "reduced" it to trying to find the minimum nodes to remove so that all the edges would disappear (an edge would mean that the two numbers cannot be in the final set together). I couldn't find a good algorithm for this, though.

Solved difficult medium and failed easy. Two fails (also CF345) in a one day :-(

d2 600: come up with a dp solution dp[i][j] = number of sequences of length i ending with the number j. Then, you can write a recurrence like . Naively, this seems like O(nk^2), but see if you show there is someway to do it in O(nk*logk) instead.

d2 900: The first thing that should come to mind is that this is a graph problem. Let's suppose the graph had no cycles. Then, you have this problem: http://stackoverflow.com/questions/16124844/algorithm-for-finding-a-hamilton-path-in-a-dag So, how do we deal with cycles? We compute the condensation of the graph, then apply the algorithm in the link. Easier to code solution (but harder to prove): You can show these 2 conditions are necessary and sufficient. Every node is reachable from node 0. For each pair of nodes x,y, either there is a path from x to y or a path from y to x. So, another solution is to return no if either of those two conditions is violated, otherwise return yes.

Try to look at it combinatorially. As an intermediate step, try to show that the sum of m! / (s[1] * s[2] * ... * s[n]) over all permutations is equal to m! / (x[1] * x[2] * ... * x[n]). I can post a more detailed solution later if you're still stuck.

Another solution. In this explanation means that the sum is taken over all permutations of {a, b, c, d}.

It is easy to verify that . However, in this task we want to compute something like .

Since it's difficult to handle high-degree polynomials of X in denominators, rewrite it as follows:

Let's take a close look at the first term:

Other terms can be simplified similarly, and we get the following formula:

where sum(S) denotes the sum of all elements of S.

Now the remaining part is straightforward. Fix the first element of the permutation and write it as X. a, b, c, d correspond to other elements. Compute the distribution of sum(S) and the parity of S using a simple DP. Compute the answer using the formula above.