Now you can use ACL by default in old contests too.

It's good that they are experimenting with different time. Good for other timezones. Why should asians have all the fun? :P Though still this time is good for Asia.

I guess it is because of GP (thanks!).

Why do you care time if you live in Antarctica?

I have the same problem. As a junior high student,I have to get back to my dormitory before 22:30,which means that I can participate in the contest for at most one hour.

Solution for C:

First find for each subset of camels the minimum separation they should have in order not to break any bridge part --> Complexity O(M*2^N)

Now iterate over all permutations of camels and for each one build an optimal separation

To do this we iterate over all subsequences of camels in the permutation and push the last one in order for the total separation to be as computed above --> Complexity O(2^N)

Answer is minimum over all permutation of the separation between first and last camel.

Total Complexity O(M*2^N + N!2^N)

Can you help me B

For C, try out all possible permutations of the Camels. Construct a DAG where two Camels a and b are connected if the contiguous segment from a to b would make a part of the bridge collapse if they're all in that part. The weight of this edge is the length of the longest such part. Then just find the max distance from 0 to n on this DAG.

Second wins iff n % 2 == 1 or quantity of each element is even.

if n is odd, the second player will always win.

if n is even, the second player only win if the frequency for each number in A[i] is even

example : A = {2 2 4 4 9 9 1 1} then the second player will win.

example : B = {2 2 4 4 9 9 1 2} then the first player will win.

Solution for D:

if n is odd the second player can always win. (think of it this way: in the last move the second player makes he has enough degrees of freedom in order to make it impossible for the first player to get xor 0 with his last move)

if n is even there are two case:

if every number appears an even number of time in the array the second player has a winning strategy which is to always copy what the first player did in his move (You'll see that after each move of the second player XOR of created sequence is 0)

Otherwise the first player can win by the same logic used in the case where n is odd

Yes, you don't need to check every condition every time. Only $$$O(2^N)$$$ constraints are ever actually relevant.

4*(10^9) definitely not good enough for 2 seconds.

for each permutation you can find the minimum distance between every camel in O(N^2 log M) with loops and binary search

total complexity is about O(N! N^2 log M)

$$$2,\space 4,\space 7\space \implies\space 4, \space 5 \space \implies \space 1$$$

If test cases contain 2 1 10^9 the solution will be TLE

I have noticed that "trivial" can mean anything.

What's the definition of logarithm of 'set power series'? Is it a function

, such that

where the inner summation goes over all partitions

? Did I, perhaps, miss some division by some factorial?

This is very cool (but definitely nontrivial!).

For anyone (like me when I first read this comment) who does not know how to implement the operations in $$$O(N^22^N)$$$ (the subset-convolution and the logarithm): think of the standard xor-convolution (via Walsh-Hadamard transform) applied independently on the entries with a fixed number of bits.

More precisely, to compute the subset-convolution between $$$f$$$ and $$$g$$$ (both are functions on the subsets of $$$\{0,1,\dots, n-1\}$$$), one splits $$$f$$$ as $$$f_0+f_1+\cdots+f_n$$$ where $$$f_i(S)=f(S)$$$ if and only if $$$|S|=i$$$ (and otherwise $$$f_i(S)=0$$$) and computes the Walsh-Hadamard transform of $$$f_0,f_1,\dots,f_n$$$. Then, it is not hard to check that the subset-convolution can be obtained easily if one has the xor-convolution between $$$f_i$$$ and $$$g_j$$$ for all $$$i+j\le n$$$.

I am not sure this is the standard way to compute the subset-convolution. If there is a more clever way, I would like to know.

This is so fucking cool, wow.

Do you know any other problems(on some online judge) that can be solved using this stuff? Especially if they require finding exp or square root of "set power series"?

UPD: After reading your solution and Lu Kaifeng's report it seems that the ranked Möbius transform is much more powerful than "Fourier meets Möbius" suggests: looks like you can apply any function to the set power series by applying it to a "ranked" vector for each mask independently. At the very least it works for subset convolution and logarithm so it would be very surprising if this doesn't hold in general.

But what is this witchcraft??? Why does it work?

I think to find the number of operations we need to brute force. Once the smallest number in the array is 1 it is trivial as each number a[i] will be decremented a[i]-1 times.

But if the smallest number is bigger than 1 we need to try and count all other numbers.

Can u elaborate how minimum is cut by at least half?

Sorry, I understand now