tokitsukaze's blog

By tokitsukaze, 9 days 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
  • +123
  • Vote: I do not like it

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

Thanks for the fast editorial! <3

»
9 days 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)

  • »
    »
    9 days 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:

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Typical cyan attitude.

»
9 days 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}$$$ (((

»
9 days 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.

»
9 days 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.

  • »
    »
    9 days 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.

  • »
    »
    9 days 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

  • »
    »
    9 days 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?

    • »
      »
      »
      8 days 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.

  • »
    »
    9 days 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.

    • »
      »
      »
      8 days 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

  • »
    »
    8 days 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

»
9 days 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)$$$.

  • »
    »
    9 days 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 $$$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.

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

ayy fast editorial :)

»
9 days 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

  • »
    »
    8 days 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.

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

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

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

Thanks for nice debugging template.

»
9 days 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.

  • »
    »
    6 days 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. :)

    • »
      »
      »
      6 days 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.

»
9 days 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

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

there is another dp solution to b2 and b1 with 4 states like

i = current character of string

p0 = parity of last consecutive 0s

p1 = parity pf last consecutive 1s.

p = parity of s[i — 1] where s is given string s.

Solution[submission:156354472]

»
9 days 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

»
9 days 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.cc/contest/1678/submission/156353215

  • »
    »
    9 days 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

    • »
      »
      »
      9 days 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.

      • »
        »
        »
        »
        9 days 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.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Function overhead + Higher constant?

»
9 days 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).

  • »
    »
    6 days 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.

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

      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 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.

      • »
        »
        »
        »
        5 days 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!

»
9 days 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.

  • »
    »
    9 days 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.

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

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

»
9 days 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?

  • »
    »
    8 days 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

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        May I have a look about your solution?

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This 156351799 solution was getting TLE.

          • »
            »
            »
            »
            »
            »
            8 days 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

            • »
              »
              »
              »
              »
              »
              »
              8 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks for your reply. Got it!

          • »
            »
            »
            »
            »
            »
            8 days 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

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
»
9 days 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.

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

    I implemented exactly this (but with different two iterations)

    156328504

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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_{a<b<c<d}1_{p_{a}<p_{c}}1_{p_{d}<p_{b}} $$$

    which is equal to:

    $$$ \sum_{b}\sum_{c>b}\sum_{a=1}^{b-1}1_{p_{a}<p_{c}} \sum_{d=c+1}^{n}1_{p_{d}<p_{b}} $$$

    using s[i][j], we obtain:

    $$$ \sum_{b}\sum_{c>b}s[b-1][p_{c}-1]\left(s[n][p_{b}-1]-s[c][p_{b}-1]\right) $$$
»
9 days 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 :(

  • »
    »
    7 days 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.

»
9 days 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.

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

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

    • »
      »
      »
      9 days 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

»
9 days ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Today's Div2c is similar to click here

»
9 days 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?

  • »
    »
    6 days 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)$$$.

    • »
      »
      »
      33 hours 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$$$)

»
8 days 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.cc/contest/1678/submission/156367158

  • »
    »
    8 days 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).

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
8 days 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

»
8 days 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.

»
8 days ago, # |
  Vote: I like it -17 Vote: I do not like it

sjfsb

»
8 days 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.

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

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

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

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

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution is failing on the following test case :

    test case

    The answer should be "1 2" but your answer is "1 3"

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

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, 156393108

Also Here is the one which I submitted when the Contest was live....156311829

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

    Your Solution is failing on following test case :

    test case

    Answer 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.

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

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.....

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

Can someone help me understand the fenwick tree solution for Tokitsukaze and strange equality

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

suggest me some tips on how to solve c in contest .topics difficulty range or any other resources to follow

»
8 days 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?

»
8 days 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!

»
6 days 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)$$$

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

Could someone please help me understand Div 2 problem D editorial?

»
6 days 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?

»
5 days 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:(

»
4 days 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.

  • »
    »
    4 days 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

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

in question B1 can someone explain me this test case 110011000

  • »
    »
    3 days 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.

»
3 days 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

»
2 days 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

»
42 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Problem E div.2 be solved using some kind of DSU ?

»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.cc/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