peti1234's blog

By peti1234, 5 weeks ago, In English

Hope you enjoyed the problems.

Direction Change
Social Distance
Make it Increasing
Optimal Partition
Half Queen Cover
Edge Elimination
Centroid Probabilities
Yin Yang
 
 
 
 
  • Vote: I like it
  • +146
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

Great contest and lighting fast editorial l.thora to rukoo( wait a bit) , d was good almost did it in contest

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    what's there to downvote?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have come up with this solution for problem D.

    Here, I have found the max positive segment from each index using upper bound and then did dp as the max value either taking only the current index or taking the max segment of positive sum.

    I have found the edge case of my solution and I think checking all segments of positive sum from each index will give the correct ans but to find and store all such segments will take $$$O(n^2)$$$ complexity. I did top down dp here and did not understand the editorial solution after thinking a long time. I did not understand what segment tree or fenwick tree is doing here.

    Please anyone help how should I solve it.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very fast editorial.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for superfast editorial

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Fastest editorial ?

I'm happy that I actually had some approach for problem D instead of being totally clueless, which is a huge improvement

»
5 weeks ago, # |
Rev. 3   Vote: I like it +99 Vote: I do not like it

Please, add option “VERY bad problem” to C

»
5 weeks ago, # |
  Vote: I like it +59 Vote: I do not like it

How would one come up with the solution of div1C? I can't get even remotely close to it

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    You think "how can I save k queens from the trivial solutions of n queens?". Then you note that the issue in doing so is that you have kxk region that is not covered by horizontal and vertical lines (determined by not necessarily consecutive rows and columns). The path of least resistance is to hope for arrangements when that region is simply a kxk square. You need to cover it by diagonals and you play a lil bit on paper with construction. Moving in knight's move fashion is an often trick when you are covering consecutive diagonals.

»
5 weeks ago, # |
  Vote: I like it +75 Vote: I do not like it

FFT in E? I believe I solved it in much easier way (15 seconds after the contest end though...)

big[i] is the probability that subtree of vertex i has at least (n+1)/2 vertices, cent[i] is the probability that i-th vertex is the answer

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is Newt()? Quick_Power?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    For the big[] part, is it simply doing algebra or does it imply a prettier combinatorial explanation?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is a nice combinatorial explanation. Note that there is an easy bijection between all permutations of n numbers, where numbers 1..i are in order and 1 has to be the first number of whole permutation and ways of how do you connect guys i+1..n — you start from 1,2,...,i and you insert next numbers one by one into some place in this permutation, but not at the beginning. The number before new number is the one it connects to. (We don't care how guys 1..i are connected between themselves in order to determine whether subtree of i is big). Let's remove that 1 from our permutation. In this bijection, the subtree of i is big if and only if all numbers 2..i are in the first half of that permutation, so the formula from my code follows.

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

What is the meaning of "If we store the prefix sums, and assign a permutation according to the prefix sums,..."?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Greter prefix sum — greater value in the permutation.

    For example: array: $$$[1, 3, -5, 4, 2]$$$, prefix sums: $$$[1, 4, -1, 3, 5]$$$, permutation: $$$[2, 4, 1, 3, 5]$$$

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Ok...

      But still, "So there is an optimal solution when only winning segments might be longer than 1. It is easy to handle the 1 long segments. For each i (1≤i≤n) we have to find j, 0<=j<i, where v(j+1,i)>0, and dpj+v(j+1,i) is maximal (dp0=0)."

      Why $$$v(j+1,i)$$$ has to be positive? Is this somehow different from the initial, $$$n^2$$$ solution? And how/why does this prefix-sum ordered permutation help finding $$$j$$$ ?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +25 Vote: I do not like it

        Why v(j+1,i) has to be positive?

        The paragraphs at the beginning of the editorial explain why it's optimal to only consider indexes $$$j < i$$$ such that $$$v(j+1, i)$$$ is positive or the case when the last element is in a segment by itself (that is $$$j = i-1$$$).

        case 0:
        The case when the last element is in a segment by itself, is covered by $$$dp_i = dp_{i-1} + v(i,i)$$$.

        case 1:
        If $$$v(j+1,i)$$$ is negative, then we can split the segment $$$[j+1,i]$$$ into $$$i-j$$$ segments of length $$$1$$$, and the sum of values over these segments of size 1 can't be less than $$$v(j+1,i)$$$. However, the scenario when $$$[j+1,i]$$$ is split into segments of size 1 is already covered in case 0.

        case 2:
        If $$$v(j+1,i) = 0$$$, we can also split $$$[j+1,i]$$$ into two or three segments, the last of which (ending at $$$i$$$) either has positive value, or is of size 1, and moreover the sum of values over these (two or three) segments is not less than $$$v(j+1,i)$$$. (Look at the editorial to understand how).

        This means we don't have to worry about $$$j$$$ when $$$v(j+1,i)$$$ is not positive.

        And how/why does this prefix-sum ordered permutation help finding j ?

        By the previous observation, $$$dp_i$$$ is either equal to:
        $$$dp_i = dp_{i-1} + v(i,i)$$$ (last element is in a segment by itself), or
        $$$dp_i = max_{v(j+1,i) >0} (dp_j + v(j+1,i))$$$ -- the maximum over all $$$j$$$ such that $$$v(j+1, i)$$$ is positive. By definition, if $$$v(j+1,i)$$$ is positive, then $$$v(j+1,i) = i-j$$$. But $$$v(j+1,i)$$$ is positive if and only if $$$pref(j) < pref(i)$$$.
        So we can rewrite the second equality as:
        $$$dp_i = max_{pref(j) < pref(i)}(dp_j + i - j)$$$.

        How do we quickly find maximum of $$$dp_j-j$$$ over the interval $$$(-\infty, pref(i))$$$ ? We could use Segment Tree (or Fenwick Tree), but the values of $$$pref(i)$$$ can get very large. But we only need the relative order of $$$pref(i)$$$, so we can normalize the array $$$pref$$$ and replace it with values from $$$0$$$ to $$$N$$$.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How does one compute the permutation? I can think of O(nlogn) way but is there better?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the editorial of problem F of div1, Did the author know that no one will solve it because it's so hard, Or he has removed the editorial of it now?

»
5 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

Another optimal construction for C that's different from the editorial looks like alternating knights moves from the bottom left like this:

.........X
........X.
..........
.......X..
.....X....
..........
....X.....
..X.......
..........
.X........
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Yup. The motivation for me was to put one half-queen on an infinite board. Then try to repeatedly cover some of the closest uncovered squares, hence the knight move. All the while trying to keep the construction as square as possible, hence the alternating knight moves.

    text pictures of the solving process

    Additionally, this approach doesn't have special cases for $$$n = 1$$$ or $$$n = 2$$$.

»
5 weeks ago, # |
  Vote: I like it +247 Vote: I do not like it
$$$ \sum_{j=S-1}^{n-i} \frac{(n-j-2)!}{(n-i-j)!}=(i-2)!\sum_{j=S-1}^{n-i} \binom{n-j-2}{i-2}=(i-2)!\binom{n-S}{i-1} $$$
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    But intentionally, we can use NTT! So it will fit the Div. 1 E place!

    KAN, have you really reviewed these problems carefully?

»
5 weeks ago, # |
Rev. 2   Vote: I like it +52 Vote: I do not like it

My solution for Div2D/Div1B uses a map instead of segment/Fenwick trees: 154120734 (hope it passes system tests :D UPD it did!).

Let $$$dp_i$$$ be the answer for the array $$$a_1, a_2, \dots, a_i$$$. Then

$$$dp_i = \max_{j < i} dp_j + (i - j) * sign(a_{j + 1} + ... + a_{i})$$$.

Since, as proven in the editoral, losing and drawing segments can always be of length 1, we can account for them just by initializing $$$dp_i$$$ as $$$dp_{i - 1} + sign(a_i)$$$. Now in our maximum we only have to consider segments which have a positive sum, because only they can improve $$$dp_i$$$. If the segment from $$$j + 1$$$ to $$$i$$$ has a positive sum, then $$$p_i > p_j$$$, where $$$p$$$ are the prefix sums. We can rewrite

$$$dp_i = \max(dp_{i - 1} + sign(a_i), \max_{j < i, p_j < p_i} dp_j + (i - j))$$$.

We can store pairs $$$(p_j, dp_j - j)$$$ in a map and find our maximum using lower/upper_bound on that map. We have to keep it sorted by $$$dp_j - j$$$. This is a known trick where on every insert we remove all the pairs which have larger $$$p_j$$$ but smaller $$$dp_j - j$$$. In total there will be at most $$$O(n)$$$ removals.

The final complexity is $$$O(n \log n)$$$.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Looks like a cool trick. Thanks for sharing.

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

    Thank you! I wonder if your solution can be considered forward-style dp as opposed to the editorial's backward style dp.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I think by adapting the solution to more of a forward style, you get the one from the editorial. :)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      If you manually update all of the relevant states every time, the solution will be $$$O(n^2)$$$, which is impossible to fit under the constraints. However, you can think of Fenwick/segment tree as a way of updating all the states at once. This is where you arrive at the editorial solution.

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

Divison 2

Divison 1

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Overall great contest. But I have a problem. I implemented the solution to div 2. C (make it increasing) which is same as the official one. The complexity is O(n^2). The problem is it is in Python and it gets timed out on pretest 4. Is there any better solution to the problem or is the solution to just code in C++?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try pypy 3 64-bit.

    Otherwise you have to switch to big int I think which is too slow.

    I TLE'd too with pypy 2 once before resending with pypy 3 64-bit (the second submission AC'd).

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Oh. That hurts even more. I didn't change anything and submitted and it got accepte. Kinda sucks that i was correct but not really...

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thank you for this information, I had the same issue. Why does this make it faster, though?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        If the integers you work with get too large python switch to big int (something like an array of ints) which tends to be very slow. Using regular (32-bit) python or pypy, this happens when n>2^31 (somewhat more than 2*10^9). With 64-bit pypy you can go up to 2^63 (like a c++ long long).

        For example, if you multiply two numbers mod 10^9+7 in a loop you should use 64-bit pypy because otherwise it can be slow (you'll go above 32-bits with big ints). Modular addition and subtraction stay within 32-bit so they're not an issue.

        In problem C, the numbers could be as large as 5000*10^9 (or as low as -5000*10^9) so they wouldn't necessarily fit a 32-bit int and therefore you need to use 64-bit pypy.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          It didn't even occur to me that the sum might exceed a 32-bit int! Thanks for explaining.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    :( I did equivalent O(N^2) in C#. Stress tested it at ~950ms. Just in case decided to tune my code: removing silly stuff like getting value of an array too often, adding early terminations, moving from Int64 to Int32. Resulted in ~550ms on my stress test. Probably a good thing I did it.

»
5 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

Judge ver. of D1C is good (educational?) problem!

Step 1

Step 2

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +119 Vote: I do not like it

    First, if the output doesn't satisfy the minimum number of half-queen, return WA.

    Not exactly sure what you mean here, but this sounds as a bad checker design practice, so I want to comment on this. In general checkers should be as independed from the solution as possible; in this case it should first check that the queens indeed cover the board in both the model and the participant's solutions, and only after that compare the number of half-queens used, and return one of ok, wa, or fail verdicts.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

      But i don't consider your judging method an efficient and easy one...

»
5 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

peti1234 Thanks for the fast editorial. Problem 1668B - Social Distance is an interesting problem. Nonetheless, only the Note section shows that it is possible to permute the order of the $$$n$$$ people. It would have been better to clarify in the problem statement that it is required to find if there exists a permutation of the $$$n$$$ people that satisfies the given social distance constraints.

»
5 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

Here is my solution to C, with no casework, and very simple to implement.

For some arrangement of $$$k$$$ queens, if we only consider the row and column moves, there is a $$$(n - k) \times (n - k)$$$ subgrid that we must additionally cover. Notice that the cells in the bottom edge and left most edge of the subgrid must be covered by different diagonals. Therefore we get the condition $$$2(n - k) - 1 \le k$$$.

Let's now try constructing it. If we try to use the top right $$$(n-k) \times (n-k)$$$ grid, as our subgrid, we must place the queens on $$$(i, p[i])$$$ for $$$1 \le i \le k$$$, where $$$p$$$ is some permutation of $$${1\ldots k}$$$. Then we notice that we need all different values between $$$[-n+k+1, n-k-1]$$$ to be taken by $$$i - p[i]$$$ for some $$$i$$$.

If we reverse we get all even differences for an odd length array, and all odd differences for a even length array.

So we just reverse the first $$$\lceil n/2 \rceil$$$ elements of the identity permutation, then the next $$$\lceil n / 2 \rceil - 1$$$ of the new permutation. This gives us all odd and even differences needed.

Code
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for a nice contest!

Regarding Div1C/Div2E: How do you guys approach such problems? I went in a completely wrong direction:(. Can you perhaps recommend some problems(in a similar spirit) or resources?

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I want to share a formal and more "maths-ish" proof for observation in div2B

Lemma

To prove it we need lemma 1:

Lemma 1
Proof
Interesting
»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

So when we calculate $$$dp_i$$$, we should update with $$$dp_i−i$$$. This way, finding the optimal $$$j$$$ for each $$$i$$$ is just a prefix maximum. One can solve the problem with Fenwick tree or segment tree.

Can someone explain why should we update $$$dp_i - i$$$

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Because our dp transition is: $$$dp_i = max(dp_j + i - j)$$$, since $$$i$$$ is independent, we can rewrite it as follows: $$$dp_i = i + max(dp_j - j)$$$. As you can see, we always need $$$dp_j - j$$$ and what's why we update with this value.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you please attach this editorial to the contest attachments? Currently we just have the announcement attached.

»
5 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

MikeMirzayanov, I believe there are some violations of the rules in div2. kirya_molodec1, kirya_molodec2, kirya_molodec3, kirya_molodec4, kirya_molodec7 and kirya_molodec6's code are really confusing and similar, and they submitted each problem almost at the same time.

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

There is a spellling error in the solution of D, can you find it?

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

In solution of D optimal partition, in case of drawing segment. I don't understand how "For a drawing segment with length k if k is even than the answer is the same if we split it into two segments with length k/2". I have tried proving this, but I could not. Can someone share a proof for this please?

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

    Say your initial segment has size $$$2*k$$$ and is drawing (the sum is $$$0$$$), so it contributes $$$0$$$ to the answer. If you split it into two halves of size $$$k$$$, then either both halves are also drawing, or one half is winning and the other is losing. In either case, the combined contribution of the two halves is also $$$0$$$.

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

I Made Video Solutions for div2 A-D in Case someone is Interested.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody suggest me some online blogs or youtube channels or any sites from where I can learn about "parity". In the Problem A, the knowledge about parity is must needed, so from where I can learn that well for CP?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If the number is odd then the parity is 1, if even then 0. In on word, parity is the remainder of any number divided by 2.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve problem Div2 C using binary search?

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

consruction in the end of the solution of E

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C is a nice problem!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Div1E is a nice problem, btw, An O(n) solution without NTT exists.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution to Div2C which would have given wrong answer 154180260 passed system tests. (Here I checked for 0 position only till n-1th position.) So, in main tests, there is no testcase in which answer ends with 0.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Your solution is correct. There is no test, where the answer ends with 0. In that case you can set the n-1-th position to 0, and make 1 move on the last element. The answer will be the same.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The answer ending in 0 must be smaller than that ending in the penultimate 0, because the first penultimate 0 does not move, then all the previous ones must become negative. In other words, the second penultimate one will become negative at least once, but the first penultimate one will remain unchanged. Considering that the second penultimate one remains unchanged, it will be better if the first penultimate one becomes positive, because the second penultimate one becomes 0,0 > negative.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for question B can you please give me a testcase where my solution fail when i dont sort array and then it pass when i sort the array on same testcase...i am getting worng answer on testcase 3 (354th). i know it's hard to prove greedy sometimes. thanks in advance.

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Let me pen down a Div1F draft solution outline. I have been thinking of this problem for the day. Might be wrong.

Consider the colored points in the parameter and put them in a circular array. Remove consecutive duplicates in the circular array. If the length if the array is more than 2, there is no solution.

One side of the parameter will be white and another side will be black (The parameter might be all of the same color, we need to resolve that case as well). Build a black tree from a black point on the parameter.

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

problme B

sort it is easier

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem C have a faster solution ? I wrongly calculate 5000 * 5000 equals 2.5e8 , so at first I think the O(n^2) solution will TLE.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

NICE ROUND.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

I try to solve div1 E by using some math solutions. I get the expression of this:

we set $$$ k = \frac{n - 1}{2} $$$, then for a point id $$$ 1 < u \le k + 1 $$$, the answer is: $$$ (2k - u + 1)! (u - 1)! (C^{u-1}_k - \sum\limits_{x=0}^{k-1}\frac{1}{2k-x}C^{u-1}_x) $$$

($$$C^a_b$$$ means combination number $$$\frac{b!}{a!(b-a)!}$$$, and when $$$a > b$$$ we set $$$C^a_b = 0$$$)

I judged this expression is right. However, I don't know how to deal with the expression $$$\sum\limits_{x=0}^{k-1}\frac{1}{2k-x}C^{u-1}_x$$$, since that's an $$$O(n^2)$$$ implementation for all $$$1<u\le k+1$$$.

Can someone help me? Thanks a lot.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 7   Vote: I like it +18 Vote: I do not like it

    Thanks to newbin or playf, with her help, I solved div1 E with solve combinatorial math skills. Maybe it looks a bit long, but it's easy to think(Especially for anyone who are bad at DP like me) Here are my solutions:

    We set $$$k = \frac{n-1}{2}$$$. Consider a point $$$u (1 < u\le k + 1)$$$, let $$$c$$$ be the number of point $$$v$$$ such that $$$v > u$$$ and $$$u$$$ is not an ancestor of $$$v$$$. And $$$t$$$ be the number of $$$u$$$'s son. So $$$u$$$ has son $$$v_1,...,v_t$$$. The size of subtree rooted by $$$v_i$$$ is $$$n_i$$$($$$1\le i\le t$$$. So the answer of $$$u$$$ is:

    $$$(u-1)!\sum\limits_{c=0}^{k-u+1}C_{n-u}^c(u-1)u...(u-2+c)\sum\limits_{t=0}^{\infty}\frac{1}{t!}\sum\limits_{n_1+n_2+...+n_t=n-u-c,1\le n_i\le k}\frac{(n-u-c)!}{n_1!...n_t!}(n_1-1)!...(n_t-1)!$$$

    Let $$$f(x) = x+\frac{1}{2}x^2+...+\frac{1}{k}x^k$$$, the expressions equals to:

    $$$(n-u)!(u-1)!\sum\limits_{c=0}^{k-u+1}C_{u-2+c}^c\sum\limits_{t=0}^{\infty}\frac{1}{t!}\sum\limits_{n_1+n_2+...+n_t=n-u-c,1\le n_i\le k}\frac{1}{n_1...n_t}$$$

    $$$=(n-u)!(u-1)!\sum\limits_{c=0}^{k-u+1}C_{u-2+c}^c\sum\limits_{t=0}^{\infty}\frac{1}{t!}[x^{n-u-c}]f^t(x)$$$

    $$$=(n-u)!(u-1)!\sum\limits_{c=0}^{k-u+1}C_{u-2+c}^c[x^{n-u-c}]e^{f(x)}$$$

    Note that $$$f(x)=ln(\frac{1}{1-x})-\frac{1}{k+1}x^{k+1}-\frac{1}{k+2}x^{k+2}-...$$$, we have:

    $$$e^{f(x)}=\frac{1}{1-x}e^{-\frac{1}{k+1}x^{k+1}-\frac{1}{k+2}x^{k+2}...}=(1+x+...+x^{2k})(1-\frac{1}{k+1}x^{k+1}-\frac{1}{k+2}x^{k+2}-...-\frac{1}{k+k}x^{k+k})(mod\ x^n)$$$

    so $$$[x^{k+d}]e^{f(x)}=1-(\frac{1}{k+1}+...+\frac{1}{k+d})$$$ for $$$1\le d \le k$$$.

    Let $$$d = k - u + 1 - c$$$, the expression is:

    $$$(n-u)!(u-1)!\sum\limits_{d=0}^{k-u+1}C_{k-1-d}^{u-2}[x^{k+d}]e^{f(x)}=(n-u)!(u-1)!(\sum\limits_{d=0}^{k-u+1}C_{k-1-d}^{u-2} - \sum\limits_{d=1}^{k-u+1}\frac{1}{k+d}\sum\limits_{y=d}^{k-u+1}C_{k-1-y}^{u-2})$$$

    $$$=(n-u)!(u-1)!(C_{k}^{u-1} - \sum\limits_{d=1}^{k-u+1}\frac{1}{k+d}C_{k-d}^{u-1})=(n-u)!(u-1)!(C_{k}^{u-1} - \sum\limits_{x=0}^{k-1}\frac{1}{2k-x}C_{x}^{u-1})$$$

    $$$=(n-u)!(u-1)!(C_{k}^{u-1} - \frac{1}{(u-1)!}\sum\limits_{x=u-1}^{k-1}\frac{x!}{(x-u+1)!(2k-x)})$$$

    Consider $$$F(x)=\frac{(k-1)!}{k+1}+\frac{(k-2)!}{k+2}x+...+\frac{(k-k)!}{k+k}x^{k-1}$$$, $$$G(x)=\frac{1}{0!}+\frac{1}{1!}x+...+\frac{1}{(k-1)!}x^{k-1}$$$

    We can calculate $$$\sum\limits_{x=0}^{k-1}\frac{x!}{(x-u+1)!(2k-x)}$$$ for all $$$1<u\le k$$$ by calculate $$$F*G$$$ with $$$NTT$$$ in $$$O(nlogn)$$$. And this problem can be solved.

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

For div.1 E, we need to calculate $$$\sum\limits_{j=S-1}^{n-i}\dfrac{(n-j-2)!}{(n-i-j)!}$$$. But if we multiply it with $$$\dfrac{1}{(i-2)!}$$$, it turns to $$$\sum\limits_{j=S-1}^{n-i}\dfrac{(n-j-2)!}{(n-i-j)!(i-2)!}=\sum\limits_{j=S-1}^{n-i}\dbinom{n-j-2}{i-2}=\dbinom{n-S}{i-1}$$$, which can be calculated in $$$O(1)$$$ time without NTT. And total time complexity is $$$O(n)$$$.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the reason that ratings are temporarily rolled back? I have this a few times. I am curious about the reason.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To remove cheater and calculate rating again.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone clarify on (D)Optimal Partitions?: "There is an optimal solution if the length of the drawing and losing segments are 1. Proof: For a losing segment in the worst case we can get two losing segments with the same total length (the same value)." I get the first sentence, don't quite get the proof tho.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If the sum is negative in a segment then each element counts as -1. It can't lessen if you split it into shorter segments. Exapmle: [-3, 0, -1, -2] (the value is -4) -> [-3, 0], [-1, -2] (the value is -2+(-2)=-4)

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please explain why this solution is not working for Div2 — Problem C https://codeforces.com/contest/1667/submission/154462818

I am fixing the first element of array in some range as of now but can be fixed by binary search exactly and then trying to figure out minimum value for all possible values.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello, peti1234, in editorial of Div.1-C problem, can you please tell how you came up with the inequality (a+b-1 <= k), I spent a lot of time on it but did not get it. And can you elaborate on "Let's assume that there is a solution for k queens" line ?? (Does it mean the k queens for whole grid satisfying the given condition) and if it is true then how there will be left uncovered rows and columns and use of variables (a,b) ?? Sorry for tagging but couldn't understand after spending quite a time on it.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Each cell is covered if there is a half-queen in the same row, same column, or same diagonal. A cell in the intersection of a non-covered row and column must be covered diagonally.

      I showed that there are a+b-1 cells (on different diagonals) which must be covered diagonally. A half-queen can only cover 1, so we get the a+b-1 <= k inequality.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Failing testcase: Ticket 5576

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can somebody explain " Any order is good, when it always changes parity, and ends with an odd edge. " in Div1 D? I cannot fully understand.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For each vertex we care about the order of the removed edges. There are two good orders: odd-even-odd-even......-odd or even-odd-even-odd.... even-odd.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you elaborate a bit more on this part?

      Consider the directed graph with these conditions. One can see, that this graph is acyclic, so there is a topological order of that graph which will satisfy all the conditions.

      i.e. how does finding that there are no contradictions when labeling each edge as odd/even guarantee we can ultimately remove all the edges in some order (in particular, according to the way it's done in the editorial's implementation)

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Each edge has a parity, and each vertex has the same number of odd and even edges (or one more odd). For example, the edges are o_1, o_2, ... o_k, and e_1, e_2.. e_k, then a good removing order can be e_1, o_1, e_2, o_2..... e_k, o_k around this vertex.

        In the directed graph (where each vertex is an edge in the normal graph) we add the following directed edges: e_1->o_1->e_2->o_2....... e_k->o_k.

        And we do the same for each vertex. One can see that this directed graph will be acyclic, because it is a tree. So there is a topological order. This topological order will satisfy all the removing conditions described above.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. But what's the principle to assign the directions of an edge?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Assign parity to each edge.

        This is a pretty easy tree dp problem. For each vertex (x) calculate the parity of all edges in its subtree. Than it is easy to calculate the parity, between x and the parent of x. Because x will have the same number of odd and even edges (or one more odd).

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I thought there was a trick to problem C, but it was a brute force.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in question 2 it was given sum of n dont exceed 10^5 but i got correct only after using ll sum.i got wrong when i used int sum . am i correct or wrong

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sum of n will not exceed 10^5, because it is the size of the input. Sum of a[i] can be larger, than 2^31.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For div1B/div2D, I'm new to Fenwich tree I have some questions

  • All the top solutions use Fenwich tree, is there any advantage of it compare to segment tree, or it's just easier to implement ?

  • Is Fenwich tree used only in prefix sum or does it have other use ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Little bit faster, and easier to implement. There are other applications, but that's more complicated.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why are there no problems from D to F in the archive?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In div1E part where we calculate answer

$$$ans[i] = dp[i] - \sum_{j=i+1}^{n} \frac{ans[j]}{i} $$$

Why

$$$\frac{ans[j]}{i}$$$
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    $$$j$$$ is the centroid, and there is a decreasing path from $$$j$$$ to $$$1$$$. If this path crosses $$$i$$$, than $$$i$$$ is not the centroid, but we counted this case in $$$dp[i]$$$.

    On the path there is a unique vertex $$$k$$$, where $$$k>i$$$ and $$$p[k]<=i$$$ (the next vertex on the path). $$$p[k]$$$ can be anything, between $$$1$$$ and $$$i$$$ equiprobable, so there is a $$$1/i$$$ chance, that the path will go through $$$i$$$.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello can someone please help with my program for div1 B. It is giving WA on test 5 and I am not sure why. It is here: https://codeforces.com/contest/1667/submission/157232098