### tokitsukaze's blog

By tokitsukaze, 13 days 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

• +123

 » 13 days ago, # |   +9 Thanks for the fast editorial! <3
 » 13 days ago, # |   -13 -- Excuse me, what is the worst problem did you solved ever? -- Cf #789 B2. -- (surprising)
•  » » 13 days ago, # ^ |   +162 Although the problem was a bit difficult, but just because you missed some observation does not mean that problem was bad.Remember:
•  » » 13 days ago, # ^ |   +33 Typical cyan attitude.
•  » » » 13 days ago, # ^ |   +12 B2 was not a bad problem though...
 » 13 days ago, # |   -10 in div1D I thought that we choose k indices where we swap $p_i$ and $p_{i+1}$ (((
 » 13 days ago, # |   +14 Certainly not the most comfortable round for Div2, but I liked problem C. Thanks for a great editorial btw.
 » 13 days 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.
•  » » 13 days ago, # ^ |   +36 Yeah, that's straight up bad prep. Either they should have made a lower limit, or made these solutions fail.
•  » » 13 days ago, # ^ |   -9 Mine ordered set solution fails but others Fenwick tree solution passes that's a bit unfair
•  » » » 13 days ago, # ^ |   +22 ordered_set is much slower than Fenwick
•  » » » » 13 days ago, # ^ |   0 Then how to decide between Fenwick and ordered set
•  » » » » » 13 days ago, # ^ |   +76 Always choose fenwick over ordered_set if you can use both
•  » » » » 13 days 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
•  » » » 12 days ago, # ^ |   0 ordered set does work, you might have been doing redundant operations https://codeforces.com/contest/1678/submission/156385249
•  » » 13 days ago, # ^ |   +16 Editorial mentions that n^2 logn solutions can pass too, so ig they didn't intend to cut them?
•  » » » 13 days ago, # ^ |   0 It is hard to cut them. Who use n^2 logn solutions also will lose time.
•  » » 13 days 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.
•  » » » 13 days 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
•  » » 13 days 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
 » 13 days 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)$.
•  » » 13 days 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.
 » 13 days ago, # |   -9 ayy fast editorial :)
 » 13 days ago, # |   +12 We can solve 1677A - Tokitsukaze and Strange Inequality in more straightforward manner. 156343295
•  » » 13 days ago, # ^ |   +1 This is actually very good solution, i understood it better than the editorial itself.
•  » » 7 days ago, # ^ |   0 Sorry for being late, but can you please explain this solution?
 » 13 days ago, # | ← Rev. 2 →   0 Thanks for nice debugging template.
 » 13 days 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.
•  » » 11 days 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. :)
•  » » » 11 days ago, # ^ |   0 Thank you for your comments. I agree with you. If possible, I will try to think of something more interesting.
 » 13 days 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.
 » 13 days ago, # |   0 there is another dp solution to b2 and b1 with 4 states likei = current character of stringp0 = parity of last consecutive 0sp1 = parity pf last consecutive 1s.p = parity of s[i — 1] where s is given string s.Solution[submission:156354472]
 » 13 days 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
•  » » 13 days ago, # ^ |   +3 Thank you for pointing out.
 » 13 days 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
•  » » 13 days ago, # ^ |   0 My solution is also O(n^2 logn) and it passes comfortably: I did it by brute-forcing b and c here
•  » » » 13 days 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.
•  » » » » 13 days 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.
•  » » 13 days ago, # ^ |   0 Function overhead + Higher constant?
 » 13 days 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).
•  » » 10 days ago, # ^ |   0 Hey! Getting the error "Constraints were violated." even with default values. Not sure what's wrong? Problem Div2D. Ticket 6965.
•  » » » 10 days ago, # ^ |   +1 Hi dofecorces 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.
•  » » » » 10 days 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!
 » 13 days 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.
•  » » 13 days 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.
 » 13 days ago, # |   +3 Thanks for the good round!!! Thanks for the editorial!!!
 » 13 days ago, # |   0 Why is it written in editorial that n*n*logn should pass in Div2C?
•  » » 13 days ago, # ^ |   0 a problem can be solved by many methods,we should not think one problem only to one solution
•  » » » 13 days ago, # ^ |   0 But I got TLE on n*n*logn :(
•  » » » » 13 days ago, # ^ |   0 May I have a look about your solution?
•  » » » » » 13 days ago, # ^ |   0 This 156351799 solution was getting TLE.
•  » » » » » » 13 days 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
•  » » » » » » » 13 days ago, # ^ |   0 Thanks for your reply. Got it!
•  » » » » » » 13 days ago, # ^ |   0 by the wall , you can use int instead of ll except the final answer
•  » » » » » » 13 days ago, # ^ |   0
•  » » » » » » » 13 days ago, # ^ |   0 this is my friend's code
 » 13 days 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.
•  » » 13 days ago, # ^ |   0 I implemented exactly this (but with different two iterations)156328504
•  » » 12 days ago, # ^ |   0 Why not just write the maths? Let's note: $s[i][j]=\sum_{k=1}^{i}1_{p_{k}\leq j}$We want to compute: $\sum_{ab}\sum_{a=1}^{b-1}1_{p_{a}b}s[b-1][p_{c}-1]\left(s[n][p_{b}-1]-s[c][p_{b}-1]\right)$
 » 13 days ago, # |   +1 I read the first question wrong and wasted more than one hour in it. It feels frustrating :(
•  » » 12 days ago, # ^ |   0 Wait till you encounter a contest where you spend one hour to finish reading what Petya is up to.
 » 13 days ago, # |   0 Why does 156322948 this solution pass and 156357149 gives MLE. Both have O(n2) space complexity I think.
•  » » 13 days ago, # ^ |   0 Used int instead of long long and it passed ;_;
•  » » » 13 days ago, # ^ |   0 For me I was using array during contest it was showing MLE. But now with same size vector it passed
 » 13 days ago, # | ← Rev. 2 →   +6 Today's Div2c is similar to click here
 » 13 days ago, # |   +26 Can anyone explain more about the tutorial of div1 E? What's the difference algorithm and the a*R+b part?
•  » » 11 days 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)$.
•  » » » 6 days 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$)
 » 13 days 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
•  » » 13 days 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).
•  » » 13 days ago, # ^ |   0 you need O(n^2) to pass this problem.
 » 13 days 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
 » 13 days 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.
 » 13 days ago, # |   -17 sjfsb
 » 13 days 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.
 » 13 days ago, # |   0 I had a doubt with this submission for Problem C : 156336500 I used PBDS of C++ to find the number of Pa < Pc and Pb > Pd where I'm iterating over b and c and finding the number of Pa and Pd and since we can select any of those a or d we multiply and add for all cases. Help
 » 13 days ago, # |   0 Why did my solution failed for B2 , any test cases where my solution is not correct ? 1678B2 - Tokitsukaze and Good 01-String (hard version) 156326219
•  » » 13 days ago, # ^ |   0 Your solution is failing on the following test case : test case1 8 11110010The answer should be "1 2" but your answer is "1 3"
•  » » » 13 days ago, # ^ | ← Rev. 2 →   0 Got it , Thanks a lot :)
 » 13 days ago, # |   0 Can anyone please help me for Problem A with Round #789 Division 2 my logic seems to be alright as compared to the one given in the editorial I don't know why I am getting Wrong Answer....Here is my code, 156393108Also Here is the one which I submitted when the Contest was live....156311829
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 Your Solution is failing on following test case : test case1 2 1Answer should be 3 but it is giving 4. This is because in your solution you are checking if adjacent number are eqaul or not , but actually you should check if any 2 number are eqaul. For example in this case "1 2 1" have two numbers equal (first and last) so it should return n , but in your solution because it is not adjacent it will return n+1 , which is wrong.
•  » » » 13 days ago, # ^ |   0 thanks for pointing that out
•  » » 2 days ago, # ^ |   0
 » 13 days ago, # |   0 It hurts a lot when your solution got wrong because of just two line mistake. :( But it also helps you motivate not to do it again :) Thanks for solutions.....
 » 13 days ago, # |   0 Can someone help me understand the fenwick tree solution for Tokitsukaze and strange equality
 » 13 days ago, # |   0 suggest me some tips on how to solve c in contest .topics difficulty range or any other resources to follow
 » 13 days ago, # |   +1 Div-2 C is kind of hard to understand from the tutorial. Anyone else having problem too?
 » 12 days ago, # |   +1 div-2, Problem B, this problem is an example of how valuable a good observation is!
 » 10 days 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)$
 » 10 days ago, # |   0 Could someone please help me understand Div 2 problem D editorial?
 » 10 days ago, # |   0 In div1. C, can someone give formal proof for why alternating between maximum and minimum, maximizes the beauty?
 » 10 days 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:(
 » 9 days 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.
•  » » 9 days 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
 » 8 days ago, # |   0 in question B1 can someone explain me this test case 110011000
•  » » 7 days 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.
•  » » » 7 days ago, # ^ |   0 thanks beethoven97
 » 7 days ago, # |   0 For div1 B I need help understanding the part of the tutorial about the rows
 » 7 days ago, # |   0 I tried doing div2 C with segment tree in n^2logn, but it tle's 157247666
 » 7 days ago, # |   0 Can Problem E div.2 be solved using some kind of DSU ?
 » 5 days ago, # |   0 https://codeforces.com/contest/1678/submission/157409437 Here is my solution which got accepted for problem C I create a 2d vector of size n*n to solve this problem, should't it cause any problem since I was not able to create an array of the same size
 » 4 days ago, # | ← Rev. 4 →   0 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.
 » 9 hours ago, # |   0 can't understand the row operation for "Tokitsukaze and Meeting" (https://codeforces.com/problemset/problem/1677/B). Can anyone please explain?