Endagorion's blog

Technocup 2019 — Elimination Round 4 + Codeforces Round 528: editorial
By Endagorion, history, 2 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +26
  • Vote: I do not like it

Comments Comments (17)
»
2 years ago, # |
  Vote: I like it +120 Vote: I do not like it

Thanks for fast editorial

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to ask questions about the solution F:the 2n polynomials,is it should be n2 polynomials?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2n since the inclusion-exclusion formula is used in the proof. But it is only the proof that the main function is a polynomial, we don't need to actually compute all these 2n summands.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Out of curiosity, may I ask problemsetters about their views to criticism on Div1C? There seems to be quite negative feedback to this problem. Do you think it is reasonable to appear in CF rounds? Do you think people's criticism make sense? Thanks.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I am not a setter of this problem, but I considered it to be OK when it was proposed. Perhaps it would be better if we didn't ask for a certificate.

    But I still don't quite understand why it received such an amount of hate. There are problems which at first seem like handling a lot of corner cases without applying any specific idea, but if contestant thinks carefully before starting to write code, then he can reduce the length of this solution and the number of cases he needs to handle. I understand how this problem can be seen as a bad one if someone picks the first solution idea that comes to his mind and starts implementing it right away, but is it a good strategy on contests?

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't understand that in problem link 1085-B

how can we get this result : x= p*(n−p)/k ? Please Help.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain the following lines from "Minimum Diameter Tree" for dummies: "Note that the contribution to the sum on the right side of the inequality of the weight of each edge will be at least l−1, because any edge lies on ≥l−1 paths between the leaves of the tree. So, ∑1≤i<j≤ldistaiaj≥(l−1)⋅∑e∈Eweighte=(l−1)⋅s"

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

    same here , didn't got it either. Hope someone explains.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I know this thread is quite old, but I'll write this for any future visitors

      Consider any edge $$$ \displaystyle e \in E $$$ and let $$$ \displaystyle x , y $$$ be the number of leaves on either side of the subtrees of this particular edge. Then the number of paths between leaf vertices, such that $$$ \displaystyle e $$$ belongs to this path is given by $$$ \displaystyle x*y. $$$ If $$$ \displaystyle l $$$ be the total number of leaves, then we have $$$ \displaystyle x + y = l. $$$ Therefore, the minimum number of paths (leaf to leaf) in which the edge $$$ \displaystyle e $$$ is a part of is, when there is one leaf on one side and $$$ \displaystyle l - 1 $$$ leaves on the other side. Hence each edge will be part of atleast $$$ \displaystyle 1*(l-1) = l- 1 $$$ paths.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is mistake in B editorial. There is should be x = (nk + p^2) / p, not x = p * (n — p) / k.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone provide easier explanation for the problem div-2 D, or how they were able to get this approach

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

could not understand problem 1085-B

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

    As $$$(x\ mod\ k)*(x\ div\ k)=n$$$, both $$$x\ mod\ k$$$ and $$$x\ div\ k$$$ should be the divisors of $$$n$$$.

    As $$$k \leq 10^3$$$, which is very little, that means $$$x\ mod\ k$$$ is also less than $$$10^3$$$.

    Therefore, we can try all possibilities of $$$x\ mod\ k$$$ by assigning all values from $$$0$$$ to $$$k-1$$$ that are divisors of $$$n$$$ to it.

    Let $$$p$$$ be the assigned value of $$$x\ mod\ k$$$. How can we recover $$$x$$$?

    As we know right away that $$$x\ div\ k = \frac{n}{p}$$$, $$$x$$$ is almost going to be $$$k\cdot \frac{n}{p}$$$. However, if it ends that way, $$$x\ mod\ k$$$ would be $$$0$$$ which might be contradiction as we assigned $$$x\ mod\ k$$$ to be $$$p$$$.

    BUT $$$0 \leq p < k$$$. So if we add $$$p$$$ to that $$$x$$$, the $$$x\ div\ k$$$ wouldn't change and $$$x\ mod\ k$$$ is now $$$p$$$, the problem is solved.

    In conclusion, $$$x$$$ must be $$$k\cdot \frac{n}{p}+p$$$ if $$$x\ mod\ k=p$$$

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am really confused of the definition of $$$dp2[i][k]$$$ in Div1 E.

"Calculate the following $$$dp$$$: $$$dp2[n][k]$$$ — the number of permutations of length $$$n$$$ of elements $$$1,2,…,n,n+1,n+2,…,2n−k$$$ such that $$$p_i \neq i$$$"

According to the definition, how can $$$dp2[n][0]$$$ is just only $$$n!$$$ ?

Because the number of ways just from using elements from $$${n+1,n+2,...,2n}$$$ only is already $$$n!$$$ If we take $$$1,2,3,...,n$$$ into account, it is even more.

Did you mean "the number of permutations of length $$$n$$$ of elements $$$2n,2n-1,2n-2,...,n+1,n,...,n+1-k$$$ such that $$$p_i \neq i$$$" ?

Even so, I still can't really understand the usage of it when we are trying to build the suffix of the current row ;_;

→ Reply