chokudai's blog

By chokudai, history, 12 months ago, In English

We will hold Toyota Programming Contest 2023 Spring Qual B(AtCoder Beginner Contest 290).

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.

  • Vote: I like it
  • +62
  • Vote: I do not like it

| Write comment?
»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D? :sob:

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My solution:link

  • »
    »
    12 months ago, # ^ |
    Rev. 3   Vote: I like it +2 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 2.1
    Solution
    Code
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Means we will mark the number which are between GCD(n , d)?

      • »
        »
        »
        »
        12 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems like that the d%=n part is not necessary.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like 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

»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Passed F 4 minutes later than the contest end...

But still have $$$\Delta=+47$$$.

»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to F? (I would really appreciate if someone can start with hints, rather than direct answer, but direct answer also works)

  • »
    »
    12 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve E?

  • »
    »
    12 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Sorry my English is poor. Maybe we can think some easier problems.

    1. 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]

    2. 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.

    3. 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

»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the English Editorial be available?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

G is simpler than E and F (if don't think how to prove the correctness of solution).

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    solution
»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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}$$$.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$ .