We will hold Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）.
- Contest URL: https://atcoder.jp/contests/abc290
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230219T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: yuto1115, physics0523, PCTprobability, m_99
- Tester: m_99, leaf1415
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
Since this contest is used as a qualification round for a local contest, the problems are adjusted accordingly. For the style / difficulty of problems, please refer to Qual A.
How to solve D? :sob:
My solution:link
if gcd(n, d) = 1, how can you find the answer for any k?
look at the example n=6, d=3
try to look for cycles, notice that they all have the same length.
find the lenght of the cycles, then use that to calculate in which cycle (0, 1, 2...) c you are, given k. The answer is (c + k*d)%n
Means we will mark the number which are between GCD(n , d)?
I don't understand your question, are you asking for the answer of hint 1?
If so, try to come up with many examples of n,d such that gcd(n,d) = 1 and check k = 1, 2, ..., n. I'm sure you'll find something common to all of them that differs from a test case where gcd(n,d) != 1
It seems like that the d%=n part is not necessary.
yup, you're right, I edited it.
D was easy but I wasted a lot of time since python in my PC is more advanced than OJ.
I had to manually compile using python3.8, when I found out that math.lcm does not work in 3.8 version.
I still don't understand why do I have penalty even though I failed sample tests.
My submissions
Passed F 4 minutes later than the contest end...
But still have $$$\Delta=+47$$$.
How to F? (I would really appreciate if someone can start with hints, rather than direct answer, but direct answer also works)
You can try Google Translate on this: https://atcoder.jp/contests/abc290/editorial/5768
Firstly, note that the necessary and sufficient condition for a good tree is sum of X[i] must be 2N — 2.
Secondly, the max diameter is equal to the (number of nodes with degree >= 2) + 1 in the good tree. Then, look at this diagram (https://atcoder.jp/contests/abc290/editorial/5792) to see examples (basically arrange all nodes with degree >= 2 in a line then try to attach all the nodes with degree 1).
Lastly, use combinatorics to do counting. The implementation is straightforward once you get the formula right.
Given a degree sequence, how do you construct the best possible tree?
Take 2 nodes with degree 1, create a path with those two nodes as the ends of the diameter and nodes with degree $$$\geq 2$$$ in between. All the other nodes with degree 1 can be attached directly to a node on this diameter to create a valid tree. This is the best possible answer.
For a given $$$N$$$, how can we solve in $$$O(N)$$$?
Let the number of nodes with degree 1 be $$$K$$$. Then, for the other $$$N-K$$$ nodes, we need to assign them degrees such that $$$D_i \geq 2$$$ and $$$\sum D_i = 2*(N-1) - K$$$. We can do this with stars and bars, and we get the formula:
The first multiplier is the diameter of such a degree sequence, the next is where we choose the nodes with degree 1, and the last part is the stars and bars.
Can we simplify that sum into some pretty mathematical formula?
There is probably an easier way to do this, but here is how I thought of it:
I want to express this as the product of two polynomials $$$F(x)$$$ and $$$G(x)$$$:
Then our answer is $$$[x^{n-2}]F(x)G(x)$$$.
From the binomial theorem, we know $$$G(x) = (1+x)^{n-3}$$$. For $$$F(x)$$$, we consider $$$(1+x)^n$$$, multiply by $$$x$$$, and then differentiate, to get that same sum. Hence, $$$F(x) = (1+x)^n + nx(1+x)^{n-1}$$$. Now, multiplying the two, we get:
The coefficient of $$$x^{n-2}$$$ would be:
how to solve E?
Sorry my English is poor. Maybe we can think some easier problems.
If we have a sequence B1,B2,B3,...,Bn , how to calculation f(B)? We can calculation how many i that i<=n/2 and B[i]!=B[n-i+1]
If we want to find the sum of f(X), we can't find all contiguous subarrays of A So we can find two numbers (i,j) that A[i]!=A[j], we calculation how many contiguous subarrays of A have them. The answer is min(i,n-j+1). So now we can solve this problem by enumerating the two numbers.
We can use a vector to solve this problem. Now, When we enumeration the 'i',we can find how many 'j' can contribute i to the answer,and how many 'j' can contribute 'n-j+1' to the answer,you can use binary search.
and it is my code: https://atcoder.jp/contests/abc290/submissions/39026156
When will the English Editorial be available?
G is simpler than E and F (if don't think how to prove the correctness of solution).
How to solve C?
Solution for $$$F$$$ (based on the Japanese editorial):
An $$$x$$$ is valid if and only if $$$\sum_{i=1}^{N}{x_i}=2\cdot N-2$$$ (given that $$$x_i>0$$$). Since each edge contributes to the degree of $$$2$$$ nodes, i.e., $$$2\cdot (N-1)$$$.
Also we can always construct a tree with maximal diameter by having all nodes $$$i$$$ with $$$x_i>1$$$ connected with each other in a chain, connect a leaf to the first node in the chain, another leaf at the end of the chain, and greedily connect the other leaves to the middle nodes in the chain as long as their degrees allow more connections.
The previous construction will always work because if there are $$$y$$$ remaining leaves to be connected, exactly $$$y$$$ connections will be allowed by the middle nodes, since the degrees sum is $$$2\cdot N -2$$$ and each added edge reduces the available degrees sum by $$$2$$$.
So the answer for every $$$x$$$ is (the number of $$$x_i>1$$$) $$$+1$$$. The sum across all valid $$$x$$$ is equivalent to $$$(N+1)\cdot $$$(number of all valid $$$x$$$) $$$-N\cdot $$$ (number of valid $$$x$$$ where $$$x_i=1$$$). By stars and bars theorem, (number of all valid $$$x$$$) $$$=$$$ $$${2\cdot N-3}\choose {N-1}$$$, and (number of valid $$$x$$$ where $$$x_i=1$$$) $$$=$$$ $$${2\cdot N-4}\choose {N-2}$$$. So the final answer is $$$(N+1)\cdot $$$ $$${2\cdot N-3}\choose {N-1}$$$ $$$-$$$ $$$N\cdot $$$ $$${2\cdot N-4}\choose {N-2}$$$.
https://atcoder.jp/contests/abc290/editorial/5813
There is a typo in the fourth line of the formula: $$$|S|$$$ + (The number of $$$X \in S$$$ such that $$$X_i \ge 2$$$) $$$\times N$$$, $$$X_i$$$ should be $$$X_1$$$ .