We will hold AtCoder Regular Contest 110（Sponsored by KAJIMA CORPORATION）.
- Contest URL: https://atcoder.jp/contests/arc110
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201205T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: gazelle
- Tester: satashun kobae964
- Rated range: — 2799
The point values will be 300-400-500-600-800-900.
We are looking forward to your participation!
I thought for a second that KOJIMA PRODUCTIONS is sponsoring this round. XD
So finally kazama from Shinchan became an Industrialist and sponsoring this . Nice to see his dream come true.
I am desperate to destroy this round ᕙ༼=ݓ益ݓ=༽ᕗ
Bump, how do you solve F?
Hint: Suppose that $$$P$$$ contains $$$1 \ 2 \ ... \ k$$$ as a continuous subsequence. Try to extend it to $$$1 \ 2 \ ... \ k+1$$$.
What about Um_nik's magical solution ?
https://atcoder.jp/contests/arc110/submissions/18575753
I don't remember how to prove it, I just copied it from my 5 years old submission to this problem and fixed a bit because of 0-indexation in this one.
Unexpected solution: assume doing random operations gets random permutations. There's 1/N probability of the permutation being one big cycle, so keep doing random operations until it's a big cycle then you can solve by using only 0.
Yes, I did something similar, tried to use 0, if not then do some random swap. I was surprised that it passed the tests, maybe reducing the limit on number of operations from $$$2e5$$$ would have helped to avoid such solutions.
Actually no, this solution uses way less operations than intended. N <= 1e3 would be possible with this, not sure about much higher.
Can you elaborate on this? What does it mean to "solve by using only 0"?
I also wasn't sure what you mean by the permutation being one big cycle, since 0 always points to itself.
operation 0 swaps positions 0 and a[0], so if every position is in the same cycle then we can solve it by repeating N-1 0's.
Oh got it, you’re using a[0] and not the a[i] = 0.
I took a look at your submission on Atcoder and it seemed like something completely different, so I’m guessing you came up with this idea afterward.
Credits to https://codeforces.com/blog/entry/85275?#comment-730112
We were discussing it in discord after the contest, I told him he should share it here but it took a bit too long so I ended up commenting it first.
There are $$$(n - 1)!$$$ permutations which consist of exactly one cycle (or, in terms of Stirling numbers of the first kind, $$$s(n, 1) = (n-1)!$$$). Next, there are $$$n!$$$ permutations in total, so for a random permutation there is a $$$1/n$$$ probability of being a one big cycle.
I was surprised too, because I always knew that there are $$$(n-1)!$$$ ways to pick a cycle, but never heard of this in terms of $$$1/n$$$ probability
Yep and in fact, in a random permutation the expected number of cycles of length k is $$$\frac1k$$$ for all k. This also immediately shows that the expected number of cycles in total is about $$$\ln n$$$.
How to do C ?
First, priority is to get '1' on the first position. So suppose if '1' is at fourth position, we will have to bring '1' to 1st pos by swapping it 3 times. Now also keep an array to remember if you have swaped a certain position Pn and P(n-1) [you can't swap twice]. Now keep doing tis for every index [if indexis 'i' bring the number 'i+1' to that pos by swapping] and store the order of swaps in some array.
Now, if you came to an indice where the swap has already been done and the value on index isn't equal to (index)+1 , you print "-1" and return bcoz you can't fix that index by swapping.
Atlast, iterate thru the "visited" array you used, to keep check of what index has been swaped and confirm that each of the indices have been swaped.[We need to swap it EXACTLY one time]. If some index hasnt been swapped, return. Otherwise just print the order array
can you share your code ?
Any idea how to solve D?
$$$\displaystyle\binom{m+n}{\sum{a_i}+n}$$$
I mean how to find this formula, except using generating function?
How can it be found using generating functions?
Why this works: the problem is equivalent to placing $$$\sum{a_i} + n$$$ bars between $$$m - \sum{a_i}$$$ stars, after this we consider the bars number $$$a_1 + 1$$$, $$$a_1 + a_2 + 2$$$, etc $$$a_1 + \ldots + a_n + n$$$ as the real bars, and the other "bars" between them being the chosen objects (there are $$$a_1$$$ of them before the first real bar, $$$a_2$$$ between the first and the second and so on). All stars before the last bar are the unchosen objects from $$$b_i$$$.
Brilliant, thanks a lot Sir.
I tried to show if $$$\sum b_i-\sum a_i=d, N+\sum a_i=X$$$, then the product of $$$\binom{b_i}{a_i}$$$ over all such $$$b_i$$$ is $$$\binom{X+d-1}{d}$$$
If I prove $$$\sum\limits_{b_1+b_2=S} \binom{b_1}{a_1} \binom{b_2}{a_2}=\binom{S+1}{a_1+a_2+1}$$$, I can easily win by induction.
Consider binary strings of length $$$S+1$$$ with $$$a_1+a_2+1$$$ 1's. There are $$$\binom{S+1}{a_1+a_2+1}$$$ of them. Summing over the $$$a_1+1$$$ th 1 gives the other sum.
Therefore, we are done by the Hockey Stick Identity.
E as the hardest problem again? I admit the solution is similar idea-wise to some AGC E, except without some ugly special casing that made that problem much harder.
We can see that each character in the resulting string is formed from a substring. When does a substring $$$I$$$ form 'A'? The key is that in each operation, the number of occurrences of each character switches parity. At the end, we have 'A' once and 'B', 'C' zero times, so in the starting string, the number of occurrences of 'A' must also have a different parity than for 'B', 'C'.
Is this sufficient? We can always perform operations till we end up with a constant string. This can't be all 'B' or all 'C' because they don't satisfy this necessary condition, but it could be an odd number of 'A'. The last operation, however, gave us 'A...A' from w.l.o.g. 'A...ABCA...A'; we can simplify 'CAA' or 'AAC' to 'C' and 'BAA' or 'AAB' to 'B', which gives us at most one 'A' on each side; we know that we're getting an odd number of 'A', so it couldn't be 'ABC' or 'BCA'. Now 'BC' is ok and 'ABCA' can be transformed into 'CCA' and that into 'A'. The condition is sufficient.
If you were reading carefully, you noticed a special case: a constant substring can't be changed. If the initial string is constant, the answer is $$$1$$$. Otherwise, let's look at the string we want as the result. If it's non-constant, even if we perform some operations and end up with some extra 'AA', 'BB' and 'CC', we can always remove substrings 'AA', 'BB' and 'CC'. If it's constant, we look at the last operation and apply the same reasoning as above to see that if we can get 'A...AAA', we can also get 'A...A'.
For each resulting string, we can now associate its characters greedily with consecutive substrings of $$$S$$$. If the shortest prefix from which the first $$$p$$$ characters can be obtained is $$$S_1, \ldots, S_l$$$, then we find the smallest $$$r$$$ such that $$$S_{l+1}, \ldots, S_r$$$ gives the $$$p+1$$$-th character. We wouldn't gain anything by choosing a larger prefix than $$$S_1, \ldots, S_r$$$; this is obvious if we rewrite the condition for "we can create character from substring" to "are these prefix sums different?".
If we reverse that, we get a DP solution: for each prefix of $$$S$$$, find the number of prefixes of the resulting substring that are associated with it. State transitions are "add character" and can be processed in $$$O(1)$$$ with the above mentioned prefix sums. At the end, we can only use strings associated with some prefix if the remaining suffix has the same parities of the number of occurrences of each character, but that's easy to check. $$$O(N)$$$.
can we calculate coefficient of $$$x ^ M$$$ in the below equation ,just curious, if yes then how ?? i thought it for long time but couldn't think anything after reducing to this for D .
$$$(\prod_{i=1}^{N} ( \sum_{j=a_i}^{\infty}\binom{j}{a_i}x^j)) * (\frac{1}{1-x})$$$
The polynomial for ai is actually x^ai / (1 — x)^(ai+1) so you want to calculate the coefficient of x^m in x^(sum of ai) / (1 — x)^(sum of ai + n + 1)
Can you explain how did you get $$$\frac{x^{a_i}}{(1-x)^{a_i+1}}$$$?
sum (N+i choose N) * x^i = 1 / (1 — x)^(N+1) so multiply that by x^ai to get the exponent shift.
Got it. Thanks!
B Can someone help me with this code? I am getting 2 test cases wrong!! Thanks in advance.
try this
Thanks! My code failed in this test case.
Also try this
Check this test case
2 01
Your code is giving 0. Correct ans- 9999999999
How to solve B ?
for B what i did was convert it into classic question of given a string $$$S$$$ and $$$T$$$ we can append $$$S$$$ total $$$x$$$ times and find the occurences of $$$T$$$ using some linear function as we know the delta or difference we get of $$$ K * S $$$ and $$$ ( K + 1) * S$$$ is constant, where $$$ \vert S \vert \geq \vert T \vert $$$, so to satisfy this condition i appended $$$110$$$ total $$$10^6$$$ times, like $$$110110....$$$ let it be $$$S^\prime$$$
then i used prefix function on $$$S^\prime$$$ and $$$T$$$, where $$$T$$$ is the pattern we have to find number of occurrences of,let that val be $$$V_1$$$ and then again do same thing for $$$ S^\prime + S^\prime $$$ and $$$T$$$ ,let that val be $$$ V_2$$$,
So my answer will be $$$V_1 + (V_2 - V_1) * 9999 $$$
multiplied by $$$9999$$$ because we already chose $$$10^6$$$ so remaining factor will be $$$10^4$$$ as $$$10^4 * 10^6 = 10^{10}$$$
My submission link
This ARC is missing the "Discuss" link that points here. (So was ARC 109, but it's there now.)
Hi, I have alternative (bad) solution for F
(1) Do random operation (2) Announce 0 until 0 comes into P_0 (3) if sorted, done. else, go back to (1)
I think this works with around 1/N probability each iteration and this in contest passed with time around 700ms with python.
In Question A : for N = 30 -> ans =2329089562801, (2*10^13 ) is Giving AC, And the limit for Ans is N-10^13
Have you tried comparing 2329089562801 and 2*10^13 e.g. in Python?
anyone can help me for task D solution? https://atcoder.jp/contests/arc110/tasks/arc110_d
just read Golovanov399 's solution above
so……no ediorial in English?