### tokitsukaze's blog

By tokitsukaze, 19 months ago,

1678A - Tokitsukaze and All Zero Sequence

Idea: tokitsukaze
Prepare: tokitsukaze

Tutorial
Solution
Feedback

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
• +115

| Write comment?
 » 19 months ago, # |   +9 Thanks for the fast editorial! <3
 » 19 months ago, # |   -13 -- Excuse me, what is the worst problem did you solved ever? -- Cf #789 B2. -- (surprising)
•  » » 19 months ago, # ^ |   +162 Although the problem was a bit difficult, but just because you missed some observation does not mean that problem was bad.Remember:
•  » » 19 months ago, # ^ |   +33 Typical cyan attitude.
•  » » » 19 months ago, # ^ |   +12 B2 was not a bad problem though...
 » 19 months ago, # |   -10 in div1D I thought that we choose k indices where we swap $p_i$ and $p_{i+1}$ (((
 » 19 months ago, # |   +14 Certainly not the most comfortable round for Div2, but I liked problem C. Thanks for a great editorial btw.
 » 19 months ago, # |   +64 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.
•  » » 19 months ago, # ^ |   +36 Yeah, that's straight up bad prep. Either they should have made a lower limit, or made these solutions fail.
•  » » 19 months ago, # ^ |   -9 Mine ordered set solution fails but others Fenwick tree solution passes that's a bit unfair
•  » » » 19 months ago, # ^ |   +22 ordered_set is much slower than Fenwick
•  » » » » 19 months ago, # ^ |   0 Then how to decide between Fenwick and ordered set
•  » » » » » 19 months ago, # ^ |   +76 Always choose fenwick over ordered_set if you can use both
•  » » » » 19 months ago, # ^ | ← Rev. 3 →   +1 My Custom Implemented Order Statistics Passed in ~561 ms : https://codeforces.com/contest/1678/submission/156411337Checkout my blog as well ;) -> Blog
•  » » » 19 months ago, # ^ |   0 ordered set does work, you might have been doing redundant operations https://codeforces.com/contest/1678/submission/156385249
•  » » 19 months ago, # ^ |   +16 Editorial mentions that n^2 logn solutions can pass too, so ig they didn't intend to cut them?
•  » » » 19 months ago, # ^ |   0 It is hard to cut them. Who use n^2 logn solutions also will lose time.
•  » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ | ← Rev. 3 →   0 Yeah, I also assumed that upper_bound should be fasterBut 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
•  » » » 2 months ago, # ^ |   0 mine too got TLE ...
•  » » 19 months ago, # ^ |   +13 "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
 » 19 months ago, # | ← Rev. 2 →   +126 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)$.
•  » » 19 months ago, # ^ |   +80 Here's an alternative phrasing of this concept, which inlines the differential operator a little bit.Fix a polynomial $A(x) = a_0 + a_1 x^1 + a_2 x^2 + \cdots + a_k x^k$. 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.
 » 19 months ago, # |   -9 ayy fast editorial :)
 » 19 months ago, # |   +12 We can solve 1677A - Tokitsukaze and Strange Inequality in more straightforward manner. 156343295
•  » » 19 months ago, # ^ |   +1 This is actually very good solution, i understood it better than the editorial itself.
•  » » 19 months ago, # ^ |   0 Sorry for being late, but can you please explain this solution?
•  » » » 16 months ago, # ^ | ← Rev. 2 →   +4 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.
•  » » 16 months ago, # ^ |   +1 This solution is extremally elegant, it's just so good and clever, haven't seen something like this for quite a while, wp.
 » 19 months ago, # | ← Rev. 2 →   0 Thanks for nice debugging template.
 » 19 months ago, # |   +79 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.
•  » » 19 months ago, # ^ |   +32 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. :)
•  » » » 19 months ago, # ^ |   0 Thank you for your comments. I agree with you. If possible, I will try to think of something more interesting.
 » 19 months ago, # |   +22 C was leaked on telegram. Link to the solution — https://ide.geeksforgeeks.org/cf163b70-3b16-4e83-a880-a9b2756fcf78. Please ban those who have cheated.
 » 19 months ago, # | ← Rev. 2 →   +3 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
•  » » 19 months ago, # ^ |   +3 Thank you for pointing out.
 » 19 months ago, # |   0 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.com/contest/1678/submission/156353215
•  » » 19 months ago, # ^ |   0 My solution is also O(n^2 logn) and it passes comfortably: I did it by brute-forcing b and c here
•  » » » 19 months ago, # ^ |   0 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.
•  » » » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ |   0 Function overhead + Higher constant?
 » 19 months ago, # |   +31 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).
•  » » 19 months ago, # ^ |   0 Hey! Getting the error "Constraints were violated." even with default values. Not sure what's wrong? Problem Div2D. Ticket 6965.
•  » » » 19 months ago, # ^ |   +1 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 6975P.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.
•  » » » » 19 months ago, # ^ |   0 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!
 » 19 months ago, # |   +12 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.
•  » » 19 months ago, # ^ | ← Rev. 3 →   +6 Unfortunately I missed this observation during the contest and failed to solve B2... and solved B1 using a more complicated solution.
 » 19 months ago, # |   +3 Thanks for the good round!!! Thanks for the editorial!!!
 » 19 months ago, # |   0 Why is it written in editorial that n*n*logn should pass in Div2C?
•  » » 19 months ago, # ^ |   0 a problem can be solved by many methods,we should not think one problem only to one solution
•  » » » 19 months ago, # ^ |   0 But I got TLE on n*n*logn :(
•  » » » » 19 months ago, # ^ |   0 May I have a look about your solution?
•  » » » » » 19 months ago, # ^ |   0 This 156351799 solution was getting TLE.
•  » » » » » » 19 months ago, # ^ |   0 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
•  » » » » » » » 19 months ago, # ^ |   0 Thanks for your reply. Got it!
•  » » » » » » 19 months ago, # ^ |   0 by the wall , you can use int instead of ll except the final answer
•  » » » » » » 19 months ago, # ^ |   0
•  » » » » » » » 19 months ago, # ^ |   0 this is my friend's code
 » 19 months ago, # |   +24 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.
•  » » 19 months ago, # ^ |   0 I implemented exactly this (but with different two iterations)156328504
 » 19 months ago, # |   +1 I read the first question wrong and wasted more than one hour in it. It feels frustrating :(
•  » » 19 months ago, # ^ |   0 Wait till you encounter a contest where you spend one hour to finish reading what Petya is up to.
 » 19 months ago, # |   0 Why does 156322948 this solution pass and 156357149 gives MLE. Both have O(n2) space complexity I think.
•  » » 19 months ago, # ^ |   0 Used int instead of long long and it passed ;_;
•  » » » 19 months ago, # ^ |   0 For me I was using array during contest it was showing MLE. But now with same size vector it passed
 » 19 months ago, # | ← Rev. 2 →   +6 Today's Div2c is similar to click here
 » 19 months ago, # |   +26 Can anyone explain more about the tutorial of div1 E? What's the difference algorithm and the a*R+b part?
•  » » 19 months ago, # ^ | ← Rev. 9 →   +26 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)$.
•  » » » 19 months ago, # ^ |   0 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$)
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   0 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
 » 19 months ago, # |   0 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.com/contest/1678/submission/156367158
•  » » 19 months ago, # ^ |   +3 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).
•  » » 19 months ago, # ^ |   0 you need O(n^2) to pass this problem.
 » 19 months ago, # |   0 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
 » 19 months ago, # |   0 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.
 » 19 months ago, # |   -17 sjfsb
 » 19 months ago, # |   +48 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.
 » 19 months ago, # |   +1 Div-2 C is kind of hard to understand from the tutorial. Anyone else having problem too?
 » 19 months ago, # |   +1 div-2, Problem B, this problem is an example of how valuable a good observation is!
 » 19 months ago, # |   +3 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)$
 » 19 months ago, # |   0 In div1. C, can someone give formal proof for why alternating between maximum and minimum, maximizes the beauty?
 » 19 months ago, # |   +3 Could't solve B2. It seems like a greedy problem but instead it's dp, and I didn't even think of dp:(
 » 19 months ago, # | ← Rev. 3 →   0 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.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +5 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
•  » » » 16 months ago, # ^ |   0 bro I did not get it.Can u pls tell me again?
 » 19 months ago, # |   0 in question B1 can someone explain me this test case 110011000
•  » » 19 months ago, # ^ |   0 your test case is wrong since n is guaranteed to be even and len(110011000)=9 which is odd ,read the problem again.
 » 19 months ago, # |   0 For div1 B I need help understanding the part of the tutorial about the rows
 » 19 months ago, # |   0 I tried doing div2 C with segment tree in n^2logn, but it tle's 157247666
 » 19 months ago, # | ← Rev. 4 →   +10 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.
 » 18 months ago, # |   0 For problem 1677A my submission has O(n^2) time complexity but it receives a TLE. Can anyone explain why?
•  » » 18 months ago, # ^ |   0 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) for (auto pair1 : lesst) for (auto pair2 : more) if (pair1.first < pair2.first && pair2.first < pair1.second && pair1.second < pair2.second) { //cout << pair1.first << ' ' << pair2.first << ' ' << pair1.second << ' ' << pair2.second << "\n"; sum++; } 
•  » » » 18 months ago, # ^ |   +3 Thanks!
 » 17 months ago, # |   +3 whoever wrote the editorial for div1c Tokitsukaze and Two Colorful Tapes is really a terrible writer
 » 14 months ago, # |   0 I didnt get the dp solution in b2 especially how did he got the cost calculating formula , can somebody help
 » 5 months ago, # |   0 Thanks for the Chinese version of the tutorial.