tokitsukaze's blog

Codeforces Round #789 Editorial
By tokitsukaze, 3 years ago, In English

1678A - Tokitsukaze and All Zero Sequence

Idea: tokitsukaze
Prepare: tokitsukaze

Tutorial
Solution
Feedback

1678B1 - Tokitsukaze and Good 01-String (easy version) and 1678B2 - Tokitsukaze and Good 01-String (hard version)

Idea: qsmcgogo-B1, 74TrAkToR-B2
Prepare: tokitsukaze

Tutorial(greedy)
Tutorial(DP)
Solution(greedy)
Solution(DP)
Feedback-B1
Feedback-B2

1677A - Tokitsukaze and Strange Inequality

Idea: tokitsukaze
Prepare: tokitsukaze

Tutorial
Solution
Feedback

1677B - Tokitsukaze and Meeting

Idea: funer
Prepare: tokitsukaze, funer

Tutorial
Solution
Feedback

1677C - Tokitsukaze and Two Colorful Tapes

Idea: qsmcgogo, winterzz1
Prepare: winterzz1

Tutorial
Solution
Feedback

1677D - Tokitsukaze and Permutations

Idea: dark_light, FreshP_0325
Prepare: dark_light

Tutorial
Solution
Feedback

1677E - Tokitsukaze and Beautiful Subsegments

Idea: Frank_DD
Prepare: Frank_DD

Tutorial
Solution
Feedback

1677F - Tokitsukaze and Gems

Idea: dark_light
Prepare: dark_light

Tutorial
Solution
Feedback
  • Vote: I like it
  • +115
  • Vote: I do not like it

Comments Comments (98)
| Write comment?
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks for the fast editorial! <3

→ Reply
»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

-- Excuse me, what is the worst problem did you solved ever? -- Cf #789 B2. -- (surprising)

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

    Although the problem was a bit difficult, but just because you missed some observation does not mean that problem was bad.

    Remember:

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

    Typical cyan attitude.

    → Reply
»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

in div1D I thought that we choose k indices where we swap $$$p_i$$$ and $$$p_{i+1}$$$ (((

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Certainly not the most comfortable round for Div2, but I liked problem C. Thanks for a great editorial btw.

→ Reply
»
3 years ago, # |
  Vote: I like it +64 Vote: I do not like it

Obligatory to say this, since many people are talking about it:

Div1A in $$$\mathcal O(n^2 \log n)$$$ (with a BIT/Fenwick Tree) fits within the time limit, even though I think $$$n \leq 5000$$$ was chosen to specifically cut out these solutions.

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

    Yeah, that's straight up bad prep. Either they should have made a lower limit, or made these solutions fail.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Mine ordered set solution fails but others Fenwick tree solution passes that's a bit unfair

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

    Editorial mentions that n^2 logn solutions can pass too, so ig they didn't intend to cut them?

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

      It is hard to cut them. Who use n^2 logn solutions also will lose time.

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

    I'm a bit surprised since my n^2logn solution using only upper_bounds(which are probably faster than/ not much slower than BIT) got TLE.

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

      Yeah, I also assumed that upper_bound should be faster

      But now that I think about it rationally, BIT has much fewer operations, particularly by half fewer conditional jumps which are damn expensive. So it is only natural that bit is much faster

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

    "was chosen to specifically cut out these solutions."

    Well, what is the point of cutting logn solutions? It doesn't even make the general idea much different

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

Actually problem F can be solved when $$$k \leq 10^6$$$, my solution has complexity $$$O(k\log k + n\log^2 n)$$$.

Our goal is to compute the coefficient of some polynomial $$$S(n)$$$ satisfying

$$$ p^nS(n)-S(0) = \sum_{i=0}^{n-1} p^i i^k, $$$

We have

$$$ p^{n+1} S(n+1) - p^n S(n) = p^n n^k. $$$

Therefore we have

$$$ pS(n+1) - S(n) = n^k, $$$

we write $$$S(x+1) = \mathrm{e}^{\mathrm D} S(x)$$$ formally, here $$$\mathrm D$$$ is the differential operator, then we have

$$$ (p \mathrm{e}^{\mathrm D} - 1) S(x) = x^k, $$$

thus

$$$ S(x) = \frac{1}{p \mathrm{e}^D - 1} x^k, $$$

we only need to compute the multiplicative inverse of $$$p\mathrm{e}^x - 1$$$, which can be done in $$$O(k\log k)$$$.

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

    Here's an alternative phrasing of this concept, which inlines the differential operator a little bit.

    Fix a polynomial

    Unable to parse markup [type=CF_MATHJAX]

    . Now, let $$$t$$$ be a formal variable, and note that for any $$$n$$$, $$$e^{nt} = \sum_{i \ge 0} \frac{1}{i!} n^i t^i$$$. In particular, this contains all powers of $$$n$$$, so we multiply this by a polynomial to get linear combinations of powers of $$$n$$$ (i.e. polynomials). In particular,
    $$$ A(n) = [t^k] \left((k! a_k t^0 + (k-1)! a_{k-1} t^1 + \cdots + 0! a_0 t^k) e^{nt} \right)$$$

    Where $$$[t^k]$$$ denotes taking the coefficient of $$$t^k$$$. Let $$$\hat{A}(t) = k! a_k t^0 + (k-1)! a_{k-1} t^1 + \cdots + 0! a_0 t^k$$$, so that $$$A(n) = [t^k] \hat{A}(t) e^{nt}$$$.

    Now, consider the sum $$$\sum_{i=0}^{n-1} p^i A(i)$$$. We can use the above form to get

    $$$ \sum_{i=0}^{n-1} p^i A(i) = \sum_{i=0}^{n-1} p^i [t^k] \hat{A}(t) e^{it} = [t^k] \hat{A}(t) \sum_{i=0}^{n-1} p^i e^{it}$$$

    (This is valid because $$$[t^k]$$$ is a linear operator.) Note that $$$\sum_{i=0}^{n-1} p^i e^{it}$$$ is a geometric sum! Thus, we get

    $$$ \sum_{i=0}^{n-1} p^i A(i) = [t^k] \hat{A}(t) \sum_{i=0}^{n-1} p^i e^{it} = [t^k] \hat{A}(t) \frac{p^n e^{nt} - 1}{p e^{t} - 1}$$$

    We can split this term into

    $$$ \sum_{i=0}^{n-1} p^i A(i) = p^n \left([t^k] \frac{\hat{A}(t)}{p e^t - 1} e^{nt} \right) - \left([t^k] \frac{\hat{A}(t)}{p e^t - 1}\right)$$$

    Note that this only depends on the first $$$k+1$$$ coefficients of $$$\hat{A}(t) / (pe^{t} - 1)$$$, and the left hand term can be viewed as a different polynomial evaluated at $$$n$$$. The rest of the solution is the same.

    One final note: if $$$p = 1$$$, then $$$e^t - 1$$$ does not have a generating function inverse, as it has constant term $$$0$$$. In this case, we can instead use

    $$$[t^k] \hat{A}(t) \frac{e^{nt} - 1}{e^t - 1} = [t^{k+1}] \hat{A}(t) \frac{e^{nt} - 1}{(e^t - 1)/t}$$$

    since $(e^t-1)/t$ has nonzero constant term. The generating function $$$((e^t-1)/t)^{-1}$$$ is thus the key thing to compute to find sums of powers; this is in fact the EGF of the Bernoulli numbers.

    → Reply
»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

ayy fast editorial :)

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

We can solve 1677A - Tokitsukaze and Strange Inequality in more straightforward manner. 156343295

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

    This is actually very good solution, i understood it better than the editorial itself.

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

    Sorry for being late, but can you please explain this solution?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      It's quite late already, but let me try:

      He's going through all possible A-C pairs by the 2 for loops and is storing B-D pairs count in DP.

      ii = C; jj = A; dp[jj] = pairs of B-D for the current A(=jj);

      if the number standing on index jj is less than on the number on ii, it means this pair is a valid A-C pair and he's adding all valid B-D pairs(=Cnt) for the current jj(=A). He has stored sum of all B-D pairs from ii down to jj(=from C down to A). Index A(=jj) isn't included, since he adds it after the summation.

      'Cnt+=dp[jj]' adds all valid B-D pairs into the current sum(=Cnt) for this A-C. And then he increases dp[jj] IF the value aa[jj] is greater than aa[ii], which basically is 'if(a[b]>a[d])'. This line ensures we have correct amount of valid B-D pairs in the dp.

      I hope this makes sense, although it's been quite a while since you asked.

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

    This solution is extremally elegant, it's just so good and clever, haven't seen something like this for quite a while, wp.

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

Thanks for nice debugging template.

→ Reply
»
3 years ago, # |
  Vote: I like it +79 Vote: I do not like it

I'm very sorry for question 1F in div1. This question is not only the same as the question（ https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial） (I haven't seen it before), but it's really a garbage question. I'm very sorry for affecting the experience of div1 participants. I won't have such a problem next time.

My English is a little poor and may not be smooth.

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

    There is no need to say "something is garbage" because it has appeared before.

    Personally, I didn't solve the libchecker task, and I do learn something new from the task (especially from the comment from Elegia). So I really appreciate the task.

    On the other hand, I just don't quite like the "wrapping" part of task. Next time you can try to come up with something more interesting. :)

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

      Thank you for your comments. I agree with you. If possible, I will try to think of something more interesting.

      → Reply
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

C was leaked on telegram. Link to the solution — https://ide.geeksforgeeks.org/cf163b70-3b16-4e83-a880-a9b2756fcf78. Please ban those who have cheated.

tokitsukaze MikeMirzayanov

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

dp states for problem B is wrong, please correct to

$$$dp[i][0]=min(dp[i-2][0]+\left \{c_0,0\right \},dp[i-2][1]+\left \{c_0,1\right \})$$$
$$$dp[i][1]=min(dp[i-2][0]+\left \{c_1,1\right \},dp[i-2][1]+\left \{c_1,0\right \})$$$

Solution link

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

I did Problem C in O(n^2 logn) using binary search, got TLE. But the editorial says it will pass. How is this possible? My solution link : https://codeforces.net/contest/1678/submission/156353215

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

    My solution is also O(n^2 logn) and it passes comfortably: I did it by brute-forcing b and c here

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

      Well theoretically it should not pass as the # of operations: O(5000*5000*13) = 3.25 * 10^8. And we can process 10^8 operations in 1 sec.

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

        You assumed it takes exactly 1e8 operations in a second. I've seen somewhere I can't remember that its something like 4e8 or so(not sure but i'm sure 1e8 is just used as a rough estimate)... Also, stuff like compiler optimizations etc might happen.

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

    Function overhead + Higher constant?

    → Reply
»
3 years ago, # |
  Vote: I like it +31 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).

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

    Hey! Getting the error "Constraints were violated." even with default values. Not sure what's wrong? Problem Div2D. Ticket 6965.

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

      Hi codefforces I inspected the logs and your submission throws a compilation error when using C++17. (NOTE: C++20 support is officially not added yet).

      (You can confirm this by clicking on "View Logs" in the ticket status page, there you won't find any line denoting "Found failing test", indicating an early failure.

      I'll improve the error message shortly (and add C++20 support soon).

      I temporarily enabled C++20 support, and ran your submission again. Here's the failing testcase: Ticket 6975

      P.S: I know, I know. I also promised you another feature a couple of days back that I'm yet to work on. How come you're always the unlucky one to encounter these bugs? xD.

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

        Got it, thanks. Hahaha I'm a chaos monkey by coincidence. Btw it's satisfaction seeing cfstress grow day by day. Like a tree. Cheers!

        → Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I think the most important observation for B1 & B2 is that we can just look at each digit-pair's index to determine whether we need to change it: specifically, if we have an "01" or "10" at an even position, we must change it, because finally every segment will be of even length so each such "01" or "10" must reside in a single segment instead of at the boundary of two segments.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    Unfortunately I missed this observation during the contest and failed to solve B2... and solved B1 using a more complicated solution.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the good round!!! Thanks for the editorial!!!

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

Why is it written in editorial that n*n*logn should pass in Div2C?

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

    a problem can be solved by many methods,we should not think one problem only to one solution

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

      But I got TLE on n*n*logn :(

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

        May I have a look about your solution?

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

          This 156351799 solution was getting TLE.

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

            I read through your code and noticed that there are a lot of copy-like or sort-like parts in your code, which will greatly increase the running time of your code by a constant multiple (roughly counted as 6 times). $$$O(n^2logn)$$$ is not an optimal solution in the first place, and will probably fail in the case of large constants. But your idea is roughly correct, you can try to maintain the steps of the array sorting section to maintain the previous and next values through the value field by O(n^2), thus avoiding the log

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

              Thanks for your reply. Got it!

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

            by the wall , you can use int instead of ll except the final answer

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

            https://paste.ubuntu.com/p/Z4mNJ6r2Rc/

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

              this is my friend's code

              → Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

For Div. 2 C, this solution can also pass. Let suffix_count[i][v] be the number of elements in p[i..n] that is smaller than v. Similarly we have prefix_count[i][v]. Those two arrays can be calculated in O(n^2): first enumerate v then enumerate i and maintain the suffix/prefix total. Then you just enumerate all 1 < b < c < n, and for each pair of b and c just add suffix_count[c + 1][p[b]] * prefix_count[b - 1][p[c]] to the answer.

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

I read the first question wrong and wasted more than one hour in it. It feels frustrating :(

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

    Wait till you encounter a contest where you spend one hour to finish reading what Petya is up to.

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

Why does 156322948 this solution pass and 156357149 gives MLE. Both have O(n2) space complexity I think.

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

    Used int instead of long long and it passed ;_;

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

      For me I was using array during contest it was showing MLE. But now with same size vector it passed

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

Today's Div2c is similar to click here

→ Reply
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Can anyone explain more about the tutorial of div1 E? What's the difference algorithm and the a*R+b part?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 9   Vote: I like it +26 Vote: I do not like it

    Yeah I couldn't figure that out either, but here's an alternate solution.

    First, for each $$$x \in [1, n]$$$, precalculate:

    • the position $$$i$$$ where $$$p_i = x$$$, this can be done in $$$O(n)$$$,
    • the "active range", the maximal range $$$[l, r]$$$ in which $$$\max \{p_l, p_{l+1}, \ldots, p_r \} = x$$$, this can be done in $$$O(n \log n)$$$ with ordered sets, or $$$O(n)$$$ with monotonic stack

    There are $$$O(n \log n)$$$ triples $$$(a, b, c)$$$ where $$$1 \le a < b \le c \le n$$$ and $$$a \cdot b = c$$$. For each such triple we can find their positions in $$$p$$$; if they are all in $$$c$$$'s active range, then there is some $$$l_1, l_2, r_1, r_2$$$ where all segments $$$[l, r]$$$ where $$$l \in [l_1, l_2]$$$ and $$$r \in [r_1, r_2]$$$ are beautiful. You can imagine a $$$n \times n$$$ grid of cells where the $$$x$$$ and $$$y$$$ axes represent $$$l$$$ and $$$r$$$ respectively; this would translate to marking a rectangular region of the cells. Then the answer for each query $$$[l, r]$$$ is the number of marked cells in the region $$$x \in [l, r]$$$ and $$$y \le r$$$. (It turns out for later analysis that it's easier to count unmarked cells and subtract it from the area of the region)

    To speed this up, one might think of a 2D lazy segment tree with "region add" and "count zeros in region" (via minimum and frequency of minimum). But this is complicated, requiring an implicit storage strategy to cut down on space, and more importantly, may be too slow with total time complexity $$$O(n \log^3 n + q \log^2 n)$$$.

    Instead, we use only a 1D lazy segment tree and do a sweep line over the $$$y$$$ axis. Region add becomes two range adds, one positive and one negative. To implement "count zeros in region", we solve the queries offline, at time $$$y = r_i$$$. But we also need to implement a "tick" operation when advancing $$$y$$$, whose basic description is "if range minimum is $$$0$$$, add its frequency to a historic sum $$$zeros$$$"

    For a lazy segment tree to work, all possible range update operations, and compositions thereof, must be unified into a single small data structure that is cheap (preferably $$$O(1)$$$) to copy, compose, and apply, so we somehow need to summarize an arbitrary sequence of range adds and ticks into such a data structure.

    Multiple range adds are easy, just add their deltas. Multiple ticks are also pretty easy, just store the number of ticks elapsed, then perform them all at once using multiplication. However, range adds and ticks do not commute with each other, so it's not sufficient to merely store these counts separately.

    Turns out though, we only care about the ticks that happen when the range minimum is zero, and this can only happen when the delta (prefix sum of range adds) is at the minimum value. So any sequence of update operations can be summarized by a triple of values:

    • minimum delta (always non-positive),
    • number of ticks that happened during minimum delta,
    • current delta (sum of range adds)

    Final time complexity is $$$O(n \log^2 n + q \log n)$$$.

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

      I have a similar solution 157331395 with the following differences:

      When generating rectangles for $$$c$$$, we can do a small tweak so no two rectangles intersect with each other, this will make the count easier. We use $$$(x1, y1, x2, y2), x1 \le x2, y1 \le y2$$$ to represent a rectangle.

      We do a sweep line over the $$$x$$$ axis, move $$$X$$$ from $$$1$$$ to $$$n$$$, we use two 1D segment trees:

      $$$F$$$: Count the cover of rectangles that are fully inside the current region, i.e. the rectangle's $$$x2 \le X$$$. Let $$$F_y = $$$ the number of covered cells $$$(x, y), 1 \le x \le X$$$. We just use the traditional "range add, query sum" segment tree.

      $$$G$$$: Count the cover of rectangles that are partially inside the current region, i.e. $$$x1 \le X \lt x2$$$. Each leaf node $$$G_y$$$ maintains:

        1. $$$x$$$: $$$x1$$$ of the rectangle covering column $$$y$$$, or 0 if it is not covered.

        2. $$$cnt$$$: 1 if column $$$y$$$ is covered, or 0 if it is not covered.

      Non-leaf nodes maintain the sum of $$$x$$$ and sum of $$$cnt$$$. It is a modification of "range set, query sum" segment tree. We need to add an extra field to indicate if the column is covered.

      For every rectangle whose $$$x1 = X$$$, add it to $$$G$$$. For every rectangle whose $$$x2 = X$$$, remove it from $$$G$$$ and add it to $$$F$$$.

      To calculate the number of covered cells inside rectangle region (1, 1, X, Y): Let $$$g$$$ = $$$G$$$.query(1, $$$Y$$$). The count = $$$g$$$.$$$cnt * (X+1) - g$$$.$$$x + F$$$.query(1. $$$Y$$$)

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        There is an easier way to do so:

        Let's say we want to find the "rectangles" for $$$p_i$$$. The active region of $$$p_i$$$ (maximal neighbourhood of $$$p_i$$$ having no number greater than itself) can be visualized as something like:

        (Each pair of cells at positions $$$x$$$ and $$$y$$$ with same colors has $$$p_x.p_y = p_i$$$)

        Let the active region of $$$p_i$$$ be $$$[L, R]$$$. Now notice that any valid (beautiful) range $$$[l, r] $$$which has its maximum as $$$p_i$$$ must have atleast one of these same color pairs completely within it. Now it's easy to see that any such maximal set of valid ranges having maximum as $$$p_i$$$ can also be generated if we completely ignore those pairs of colored cells which have another pair lying completely within them (for example in given image, yellow and blue can be removed).

        So we can ignore such "colors", and finally we are left with a set of pairs (two cells with same color constitute a pair) in which for any two pairs $$$(l_i, r_i)$$$ and $$$(l_j, r_j)$$$ if $$$l_i < l_j$$$ then $$$r_i < r_j$$$.

        The example shown above becomes:

        Now we can divide such a region into a $$$O(colors)$$$-sized set $$$S$$$ of quartets $$$(l_1, r_1, l_2, r_2)$$$ such that for any beautiful range $$$[l, r]$$$ having maximum as $$$P_i$$$, there exists one and only one element in $$$S$$$ $$$(a, b, c, d)$$$ such that $$$a \leq l \leq b$$$ and $$$c \leq r \leq d$$$.

        How to do so? Just sort the set of colored pairs by their first element. The quartet corresponding to the $$$i$$$'th colored pair is $$$(L, l_i, r_i, (r_{i + 1} - 1))$$$ (for last pair, $$$(r_{i + 1} - 1) = R$$$).

        Our example becomes:

        (for each color, a valid range is that which has left border in left group of some colored cells, and right border in right group of cells with same color)

        Implementation: link

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

Hi can someone tell me why this code times out on Div2.C. I am new to segment trees but I knew there was a way to use it to find the number of elements less than x within a given range, so I took the code online and tried it but it times out. Any help is appreciated. Thank you https://codeforces.net/contest/1678/submission/156367158

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

    I might be wrong but I think it is just because of constants. Segment tree already has very big constants and your implementation uses vectors which adds more constants and is not necessary. Try to use a Fenwick tree instead which is strictly O(logN).

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

    you need O(n^2) to pass this problem.

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

Participating in div2 contest was pretty hard for me because of B2 being so strange. Anyway, I upsolved this contest and I have 1 question: How D2F (D1D) is supposed to be D2F? It seems pretty like D2D for me, and I spent much more time on D2D/D2E, than on D2F

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

Can someone please help me understand what the variable y means in the greedy solution for problem B2? I've been trying to wrap my head around the greedy solution, but I'm just not getting it.

→ Reply
»
3 years ago, # |
  Vote: I like it -17 Vote: I do not like it

sjfsb

→ Reply
»
3 years ago, # |
  Vote: I like it +48 Vote: I do not like it

I cannot understand why I have to check if it is impossible to make original permutations in div1 D. In statement, you said that the unclear value sequence was originated from some value sequence that Tokitsukaze made. So I think the unclear value sequence of the problem must have at least one correct original permutation.

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

Div-2 C is kind of hard to understand from the tutorial. Anyone else having problem too?

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

div-2, Problem B, this problem is an example of how valuable a good observation is!

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem E $$$2c * (N - c)$$$ is obtained from the following: We choose the largest $$$c$$$ numbers from 1 ~ N with positive contribution and smallest $$$c$$$ numbers from 1 ~ N with negative contribution. The answer is twice the sum.

$$$2 * [-(1 + 2 + ... + c) + (N - c + 1) + (N - c + 2) + ... + N]$$$

$$$= 2 * [-(c + 1) * c / 2 + (2 * N - c + 1) * c / 2]$$$

$$$= c * (2 * N - 2 * c)$$$

$$$= 2c * (N - c)$$$

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

In div1. C, can someone give formal proof for why alternating between maximum and minimum, maximizes the beauty?

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Could't solve B2. It seems like a greedy problem but instead it's dp, and I didn't even think of dp:(

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

Can anyone explain how was the below formula in the problem Tokitsukaze and Two Colorful Tapes Div 1 C derived:

c=∑⌊CircleSize / 2⌋, N represents the size of the permutation, score=2c⋅(N−c).

I understood the part of valleys and peaks. But I can not seem to connect that with this formula which is said to be derived from the summation formula of the arithmetic sequence.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    So I finally found out how we can get the score value from the summation formula of the arithmetic sequence. Here if we consider all the cycles then it will be a series of positive peak values and a series of negative valley values. So we need to take the highest peak with the lowest valley. So it would be like this:
    (2*h_maxpeak — 2* h_minvalley),(2*h(maxpeak-1) — 2*h_(minvalley+1)),...._
    This is how the series will go. If we have odd cycles then the last terms will get reduced. So if we consider n=10. This is how the series will go:

    (Sorry for picture . I am not that adept yet to write equations in spoiler. Any help or resource on how to write equations in codeforces will be appreciated)

    Please feel free to correct me if I have made any mistakes

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

      bro I did not get it.Can u pls tell me again?

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

in question B1 can someone explain me this test case 110011000

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

    your test case is wrong since n is guaranteed to be even and len(110011000)=9 which is odd ,read the problem again.

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

For div1 B I need help understanding the part of the tutorial about the rows

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

I tried doing div2 C with segment tree in n^2logn, but it tle's 157247666

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

Ladies and gentlemen, we got him!

I'm talking about div1F: the coefficients don't need to be interpolated, we have a direct (but not closed-form) formula.

Consider the Mellin operator $$$\mathsf{O} = x \frac{\mathrm{d}}{\mathrm{d}x}$$$. We want to find $$$h_{k,n} = \mathsf{O}^k \frac{Px-(Px)^{n+1}}{1-Px}$$$ for $$$x=1$$$ (yes, starting the sum from $$$1$$$ even for $$$k=0$$$). This operator follows the general Leibniz rule:

$$$h_{k,n} = \sum_j \left. {k \choose j} \mathsf{O}^{k-j} (1-(Px)^n) \mathsf{O}^j Px (1-Px)^{-1} \right|_{x=1} = \sum_j {k \choose j} (0^{k-j} - P^n n^{k-j}) \left. \mathsf{O}^j Px (1-Px)^{-1} \right|_{x=1}$$$

with proof by induction: it follows the Leibniz rule trivially for $k=0$ and

$$$\mathsf{O}^{k+1} (fg) = x \frac{\mathrm{d}}{\mathrm{d}x} \sum_j {k \choose j} \mathsf{O}^j f \cdot \mathsf{O}^{k-j} g = \sum_j {k \choose j} x (\frac{\mathrm{d}}{\mathrm{d}x}\mathsf{O}^j f \cdot \mathsf{O}^{k-j} g + \mathsf{O}^j f \cdot \frac{\mathrm{d}}{\mathrm{d}x}\mathsf{O}^{k-j} g) =$$$
$$$= \sum_j {k \choose j} (\mathsf{O}^{j+1} f \cdot \mathsf{O}^{k-j} g + \mathsf{O}^j f \cdot \mathsf{O}^{k-j+1} g) = \sum_j \left({k \choose j} + {k \choose j-1}\right) \mathsf{O}^j f \cdot \mathsf{O}^{k+1-j} g \,.$$$

We need to express $D_k = \left. \mathsf{O}^k Px (1-Px)^{-1} \right|_{x=1}$. Ansatz $$$D_k = f_k(x) (1-Px)^{-k-1}$$$ gives a recurrence

$$$f_{k+1}(x) = (1-Px) \mathsf{O} f_k(x) + P (k+1) x f_k(x)$$$

which together with $f_0(x)=Px$ says $$$f_k$$$ is a polynomial with degree $$$k+1$$$ (proof by induction); denoting its coefficients by $$$f_{k,j} P^j$$$, we have

$$$f_{k+1,j} = j f_{k,j} + (k+2-j) f_{k,j-1}$$$

which is the formula for Eulerian numbers (shifted so indices start at $1$ and $$$f_{k,0}=0$$$). In short, $$$D_k = P A_k(P) (1-P)^{-k-1}$$$ where $$$A_k(x)$$$ is the $$$k$$$-th Eulerian polynomial. Btw, this is in Wikipedia too (with a mistake, unsurprisingly for Wikipedia).

$$$h_{k,n} = \sum_j {k \choose j} (0^{k-j} - P^n n^{k-j}) P A_j(P) (1-P)^{-1-j} = \frac{P A_k(P)}{(1-P)^{1+k}} - \frac{P^{n+1} n^k k!}{1-P} \sum_{j=0}^k \frac{1}{(k-j)!} \frac{A_j(P)}{j! n^j (1-P)^j}$$$

How do we calculate $A_k(P)$ for $$$k \le K$$$? Eulerian polynomials have been studied extensively. We can use the formula $$$A_k(P) - \sum_{j\lt k} {k \choose j} A_j(P) (P-1)^{k-1-j} = 0$$$ for $$$k \gt 0$$$, which can be rewritten to

$$$\left(1-\frac{1}{1-P}\right)\frac{A_k(P)y^k}{k!(1-P)^{k+1}} + \sum_{j=0}^k \frac{A_j(P)y^j}{j!(1-P)^{j+1}} \frac{(-1)^{k-j}y^{k-j}}{(k-j)!(1-P)} = 0$$$

and this gives us a way to express the generating function $G(y) = \sum_k \frac{A_k(P)y^k}{k!(1-P)^{k+1}}$ as

$$$G(y) = A_0(P) / \left(e^{-y}-P\right) = \left(e^{-y}-P\right)^{-1}$$$

so all we need to do is invert a polynomial.

Next, we can define a generating function of $h_{k,n}/k!$ for fixed $$$n$$$:

$$$H(z) = \sum_k h_{k,n} \frac{z^k}{k!} = P \sum_k \frac{A_k(P)z^k}{k!(1-P)^{k+1}} - P^{n+1} \sum_{j=0}^k \frac{n^{k-j}z^{k-j}}{(k-j)!} \frac{A_j(P)z^j}{j! (1-P)^{j+1}} = P G(z) - P^{n+1} e^{nz} G(z)$$$

so what we're looking for is the $K$-th coefficient (multiplied by $$$K!$$$) of $$$\frac{1}{e^{-z}-P}\sum C_i (P-P^{n_i+1}e^{n_iz})$$$ where $$$C_i$$$ are the coefficients mentioned at the start of the editorial and computed in $$$O(N)$$$. I don't think this can be computed easily, multipoint evaluation seems better — but at least we got rid of interpolation.

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

For problem 1677A my submission has O(n^2) time complexity but it receives a TLE. Can anyone explain why?

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

    you code complexity is O(n^4) not O(n^2) as you run nested loop on the two vectors which they contain O(n^2) elements so total complexity is O(n^4) ,try another approach.

    O(n^4) not O(n^2)
    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain me the answer for rows in the problem 1677B — Tokitsukaze and Meeting

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

whoever wrote the editorial for div1c Tokitsukaze and Two Colorful Tapes is really a terrible writer

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

I didnt get the dp solution in b2 especially how did he got the cost calculating formula , can somebody help

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
I solved 
1677A - Tokitsukaze and Strange Inequality...using 2D prefix sum..O(n^2)..

``mySubmission

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

Thanks for the Chinese version of the tutorial.

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

I thought of a weird solution for C but it uses 3 ordered sets... The names a,b,c,d refers to indices in sync with the context of the question. I maintain an ordered set that initially contains all the elements but as we keep on erasing all the elements till the index c (as c moves forward) this set then represents the potential candidates for d since we can just use order of key for element(b) and get to know the number of possible options for this current b...

Now, at the same time we have an 'a' as well that is behind b (think of 2 for loops one decides b and the other decides c). Also, the elements in (b,c] are to be kept in another ordered set and [0,b) are to be kept in another ordered set and similarly use find by order for current ele(c) on the ordered set that contains ele in range [0,b). Deciding b and c using for loops is O(n^2) while find by order and similar operations take o(logn). Would this TLE???

→ Reply