We will hold AtCoder Regular Contest 105. From this contest, you don't need to choose the option "(with ACL)" to submit solutions with ACL. (The library is installed by default.)

- Contest URL: https://atcoder.jp/contests/arc105
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201011T2230&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: camypaper
- Rated range: ~ 2799

The point values will be 200-300-500-600-700-900.

We are looking forward to your participation!

Notice the

unusualstart time. Starts one and half later than the usual start time.Also thanks for integrating ACL library to avoid compilation errors. :)

Will there be any plan to retrofit old contests to add ACL option?

When solving some old problems, I had to use

`expander.py`

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

Why is this special starting time?

If it's an hour earlier as usual then I can participate....

I really want to participate in arc&agc but this time it's too late...

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.

But codeforces seldom have a good time for asians....

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.

how to solve c?????

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)

AGC (AtCoder Game Contest)

Can i know C & D conceptional difficulty according to codeforces ?

And how to solve C & D ??

Can you help me B

GCD of all the numbers

Yes,if input is (2,4,7) ans the 5 but the GCD =1??

please make sure you understand the problem before asking question.

yes sorry I misInterpeted O/P as Number of Steps it needs to make ALL cards equal

Can u plz expalin the intution behind it .I am not able that why it is working to just take gcd of all nos in problem B.

Thnx

Everytime we take onr pair of no and reduce it

It will be helpful if u elaborate a bit. Ur this reply cannot help . Thnx

Simple & easy code just using setDoesn't this TLE ? what's the time complexity ?

For the set {1,1e9} it runs 1e9 loops.

This code should not have passed

It just shows that the problem had weak tests

This will obviously get tle for simple case:

2

1 1000000000

You can improve this by adding another binary search to find the max limit upto which you can decrease current largest number.

SpoilerCool this one works.

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.How to solve D?

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

Thank you for the solution. Can you please explain "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". How should second player play in order to have "enough degree of freedom"? In editorial they do propose a strategy (seems some sort of heavy light trick) but I did't fully understand it. Can you please elaborate it perhaps?

In the editorial the strategy is to always take the maximum available bag and put it in the biggest dish and this way he'll guarantee to have more than half the coins in one bag and in that case you can't get a XOR of zero.

During the contest I didn't came up with that strategy but intuitively I thought that adding and XOR are very independent so if the numbers are random there should be no strategy to always get xor of 0. This doesn't prove anything but just encouraged me to try the solution I described.

Thank you for the reply, I understand your intuition now but can you tell me why does following this strategy "take the maximum available bag and put it in the biggest dish" guarantee to have more than half the coins in one bag? It feels right but not able to wrap my head around it (how to prove as in or any simple intuition/induction)?

Assume you're the one who's starting (i.e. strategy when n is even)

Each time you take the maximum available coins and put them in one bag. If your bags are sorted in decreasing order a1, a2, a3, ..., a2n; You'll get a1, a3, ..., a2n-1 in one dish and it is easy to see that the sum of all the other are less than it since a2 <= a1, a4 <= a3, ..., a2n <= a2n-1

Editorial is already posted here.

How to get rid of TLE in C. I keep getting TLE in C. my complexity is O((n-2)!*n*n*m) ~ 4*10^9. Here is my submission. How should I optimize my solution?

I fixed the first and the last camel by taking 2 highest weights and getting every permutation possible for the rest of n-2. For every permutation, I assign x coordinate to ith camels by traversing from ith to 1st camel and getting a hold on every m conditions. Can I optimize this approach?

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

Can you explain it in more detail?

For each subset of camels you only care about the maximum length of a bridge they can't go on.

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)

for B ,if input is (2,4,7) ans the 5 but the GCD =1??

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

Naive approach for B gave AC for me.

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

Yes, you are right. Can you please explain why exactly this type of small test cases are giving TLE?

Since the transition of a_1 and a_2 become like "1 and 10^9 -> 1 and 10^9-1 -> ... -> 1 and 1", it takes 10^9 loops to terminate.

F has a trivial $$$\Theta(n^2 2^n)$$$ solution under the view of "set power series".

Let's call $$$E(S) (S\subseteq V)$$$ be the edges of the induced subgraph of the given graph $$$G = (V, E)$$$.

Let $$$f_S$$$ be the number of the coloring of $$$S$$$ and a subset of $$$E' \subseteq E(S)$$$ satisfying $$$\forall (u,v)\in E', color(u) \neq color(v)$$$. We can see that

hence

and the answer is just

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?

Yes. There is no factorial. Because a partition is not ordered.

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

anyfunction 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?

Can someone please explain time complexity of https://atcoder.jp/contests/arc105/submissions/17342664? Shouldn't it be TLE with case $$$n = 2$$$, $$$a = [1, 1e9]$$$? Edit — Another user mentioned this above

In Task B, it is said that,

"Under the constraints in this problem, it can be proved that the procedure will eventually terminate."Can someone tell me how to find the number of operations?? Especially, for cases where the gcd of the input array is 1.

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.

There is a fast way to simulate problem B in O(N*logN*log(maxA))). It's gotta be somehow equivalent to finding the GCD, but that's beside the point. I wasn't going to implement it, but when I viewed the editorial saying it can't be simulated, I implemented it and it ACd. I was also super wasteful as you'll see.

Code:Explanation: let min be the minimum, which element will be the first to create a new minimum?

It's an element x s.t. x mod min is largest! that's because until all elements in the array are < 2*min, no element can create a new min. As long as there are elements with value >= 2*min, one of them will be chosen.

how do we reach the point that for all i, min <= a[i] < 2*min?

Stage 1: simply iterate over the array and set a[i] = a[i]%min + min; now, either all elements are the same, or the next operation will lower the minimum.

Stage 2: Sort the array from greater to smaller while maintaining the current minimum, and simulate the operation (reduce current minimum from each item).

Complexity:

why is it nlog^2(n)?(it's probably less tbh)I'll prove that after performing one iteration of the above algorithm (Stage 1 + 2), the minimum of the array is at least cut by half. At stage 2, max is a[0] and min is a[n-1]. We iterate from 0 to n-1, doing a[i]-=cur_min. If when we reach a[n-1], cur_min <= min/2, we are done. Otherwise, cur_min > min/2, and then a[n-1]-cur_min < min/2 definitely hold, because a[n-1] is min.

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

When the array is already sorted, and you perform the subtractions, there are two options that may happen when you reach the original minimum, which is at index n-1.

If when reaching it, new_min is already <= original_min/2, then the overall minimum is already cut in half, agree?

For example, if the sorted array is [11,9,9,8], then right before reaching 8 it becomes [3,6,6,8]. the new minimum is already 3, which is <= 4=8/2.

If when reaching it, new_min > original_min/2, then after performing original_min — new_min, it must be cut in half. Look at the equation "new_min > orig_min/2", subtract orig_min from both sides to get "new_min-orig_min > -orig_min/2" now multiply by -1 and get "orig_min-new_min < orig_min/2".

For example, if the sorted array is [14,13,13,8], then right before reaching 8 it becomes [6,5,5,8], and the new_min=5>4. now, after performing orig_min-new_min=8-5, the new_min will be 3 <= 4.

Got it.Thank you very much for taking out your time.

E — Keep Graph Disconnected Editorial Why the answer of 1 6 1 1 2 is “First” ? Thanks a lot.

Sorry, I understand now