platelet's blog

By platelet, 16 months ago, In English

1842A - Tenzing and Tsondu

Tutorial
Code

1842B - Tenzing and Books

Tutorial
Alternative Solution
Code
Alternative Code

1842C - Tenzing and Balls

Tutorial
Code

1842D - Tenzing and His Animal Friends

Tutorial
Code

1842E - Tenzing and Triangle

Tutorial
Alternative Solution
Code
Alternative Code O(n alpha n)
Alternative Code O(n)

1842F - Tenzing and Tree

Tutorial
Code

1842G - Tenzing and Random Operations

Tutorial
Code

1842H - Tenzing and Random Real Numbers

Hint 1
Hint 2
Tutorial
Code

1842I - Tenzing and Necklace

Hint 1
Hint 2
Tutorial
Code
  • Vote: I like it
  • +573
  • Vote: I do not like it

| Write comment?
»
16 months ago, # |
  Vote: I like it +77 Vote: I do not like it

Problem D :|

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's wrong with it?

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it -74 Vote: I do not like it

      Because the idea — do some greedy. I am pretty sure, that 90% who solved it write like 100-200 lines greedy, without(ANY) proof why it works.

»
16 months ago, # |
Rev. 3   Vote: I like it -24 Vote: I do not like it

Editorial of D makes it seem easy but could not get it during contest

»
16 months ago, # |
  Vote: I like it +87 Vote: I do not like it

Can anyone explain problem E in detail?

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

    I didn't understand the tutorial either.

  • »
    »
    16 months ago, # ^ |
    Rev. 4   Vote: I like it +13 Vote: I do not like it

    it's a standard segtree + dp problem. my approach was moving in x-axis from k to 0, let dp[i] be optimum cost for points from i to k, to optimize dp[i] we can either draw a triangle from i to k-y where 0<=y<k-i (obviously), or we can just do dp[i] = dp[i+1] + c[i], c[i] is total cost of points having x coordinate as i. let j (j>i) be the x coordinate till which we draw the triangle, so dp[i] = (j-i)*A + dp[j] + c[i<=x<j,0<=y<k-j], last term is the cost of points strictly below the triangle and strictly to the left of j. we can write dp[i] = (-i*A) + (dp[j]+j*A + c[i<=x<j,0<=y<k-j]), so as we move to left we must precompute the second term for all the coordiates after i so that we can do a min query at i, the term dp[j] + j*A can be added just after computing dp[j] but cost of points in c[i<=x<j,0<=y<k-j] added using lazy propagation whenever we encounter a new point

    My submission: 211064886

    you can find similar problems at, problem1 problem2 they don't involve lazy tree so comparatively easier

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

      eklavya_k sorry but can you explain how to do the desired stuff with segment tree? whenever we encounter a point (x, y) we will add it's cost to the interval [i, j] but how will we maintain the constraint of y that is 0 <= y < k — j. It might be possible that some points in range [i, j] violates this.

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

        if a point is at (i,y) you should update the cost in range [i+1,k-y-1], i.e. till j = k-y-1, so k-j = y+1 > y, other positions which are left of j will certainly have their y-axis range greater than y+1, no range is violated. Draw graph to understand better rather than equations

»
16 months ago, # |
Rev. 3   Vote: I like it +227 Vote: I do not like it

Several fun facts:

  • KAN thought the problem A was a little difficult before the contest.
  • The problem B was walking on a graph at first. KAN also thought it was difficult and changed to three stacks.
  • Sadly a lot of FST appeared in the problem D. The problem D was E before and we did not add multiple tests. Sorry for the FSTs.
  • MagicalFlower discussed problem F,G with me today and tried to find polylog solution. He found n log^2 n solution for solving a single k in problem F, orz orz orz.
  • The module of problem G was 1e9+7 at first, our coordinator changed it to 998244353. Some testers' NTT solution passed, so we changed back to 1e9+7.
  • »
    »
    16 months ago, # ^ |
    Rev. 2   Vote: I like it +74 Vote: I do not like it

    Thanks for the round; the problems were good even if there were some issues with the tests (fwiw I've heard rumors that systests are weak for C and H, but I haven't had the chance to look at the submissions myself). Rough way to lose LGM, though ;-;

    To add some context re: D, I believe my solution should FST anytime (a) vertices $$$1$$$ and $$$n$$$ are connected (i.e., the answer is not infinity) and (b) there exists a vertex connected to $$$n$$$ with weight $$$0$$$. This seems like the sort of thing that could easily be covered by multitesting, rather than a niche edge case that isn't likely to come up in pretests (in fact, even without multitesting I'm somewhat surprised it doesn't happen sooner).

    My suggestion (for CF policy in general, not specific to this round) is that there should be a valid documented justification anytime multitesting is not used. The most common justification I can imagine is that pretests and systests are identical (and ideally, it would be nice if this could be enforced within Polygon if this is the reason multitesting is not being used, to prevent extra tests from accidentally being added to systests later). I could imagine allowing non-multitesting if e.g. multitesting makes the complexity analysis more confusing (though in such cases it seems like the problem would usually already be difficult enough to allow pretests = systest).

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

    I think problem A is difficult too.

»
16 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

In Problem 'A' solution , sum(ai) < sum(bi) , then anser is Tenzing...typing mistake in tutorial(sorry for bad English).platelet

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve ghi

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Here is how I solve G:

    First, somehow I defined

    $$$ S = \prod_{i = 1}^n (a_i + v X_i + v Y_i + \ldots) $$$

    where $$$X_i, Y_i, Z_i, \ldots \sim \textsf{Ber}(i / n)$$$. Note that $$$X_i, Y_j$$$ are independent, but $$$X_i, X_j$$$ are dependent.

    It is clear that once we expand everything (and have $$$(m + 1)^n$$$ terms), we can use linearity of expectation to find the answer. Then I attempted to expand that on small $$$n$$$ and $$$m$$$, hoping to see the pattern.

    I observed that for $$$i < j$$$, $$$\textsf{E}[X_j | X_i] = X_i$$$. That is, once we have some earlier term $$$X_i$$$, we don't have to worry about $$$X_j$$$ at all.

    Then I came up with a dynamic programming solution, trying to calculate the answer for each suffix. By the symmetry of $$$X, Y, Z, \ldots$$$, I can define a state to be the length of the suffix and the number of variables ($$$X, Y, Z$$$) that were previously in our expression before. (a.k.a. "free") at that point. There are $$$\mathcal{O}(n^2)$$$ states, and all transitions can be done in $$$\mathcal{O}(1)$$$, as there are three cases to handle, the case where the contribution comes from $$$a_i$$$, "free" $$$X_i$$$, and "new" $$$Y_i$$$.

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

    Nvm

  • »
    »
    16 months ago, # ^ |
    Rev. 3   Vote: I like it +43 Vote: I do not like it

    For G: I am aware of two ways. Someone in the AC discord mentioned this blog: https://codeforces.net/blog/entry/98624 for a good approach that does not use that much machinery.

    My way used generating functions. I 1-index $$$a$$$ in the math below. Let $$$dp_{i}(m)$$$ (the naive dp, which can be easily done in something like $$$nm^2$$$) be sum of the values of the product of the first $$$i$$$ elements given that $$$m$$$ operations land there. We have that

    $$$ dp_i(m) = \sum_{c \leq m} (a_i + vm)\binom{m}{c}dp_{i-1}(m-c). $$$

    It is easy enough to write this as a convolution: let $$$y_i = \sum_k dp_i(k)x^k/k!$$$

    so that

    $$$ y_i = (a_i+vx)e^xy_{i-1} + vxe^xy_{i-1}'. $$$

    (I am skipping some steps, this is just a rough sketch--the idea that I didn't see in contest was to send $$$vm$$$ to $$$v(m-c)+vc$$$, haha)

    Now substitute: $$$z_i = e^{-ix}y_i$$$, and we have

    $$$ z_i = (a_i + vix)z_{i-1} + vxz_{i-1}'. $$$

    Conveniently $$$z_0=1$$$. It is enough to compute the polynomials $$$z_i$$$ for $$$i\in [n]$$$ and just take

    $$$ m!n^{-m}[x^m]e^{nx}z_n = \sum_{c \leq n} \frac{m!}{(m-c)!n^c}[x^c]z_n $$$

    where the falling factorial on the right is easily maintained.

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Beautiful solution! I have learned a lot from this. However, it should be $$$z_i=(a_i+ivx)z_{i-1}+vxz'_{i-1}$$$ (:

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

Try hacking this submission

Upd: Uphacked, yay!

»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For problem D, I brute forced the problem. I first noticed that if node 1 and node n weren't in the same component, than the game would last for an infinite amount of time. So from now on, we can assume that node 1 and n are in the same component. I started by looking at the set of all the nodes in the component except node n. If you look at the weighted edges between the set of current nodes and node n, then you can see that we can set the minimum of those edges to be the amount of time spent playing with the set of current nodes. Then we have to update those edges by decrementing all of them by that value. This will force some new edges to have a value of 0. The new nodes connecting to those edges will have to be removed from the set of current nodes. In this way, you can keep simulating the process by looking at the edges between the set of current nodes and the set of removed nodes. Once node 1 is removed, you can end the process and print the answer. I'm not quite confident on how to prove that this will give the best answer but I guess it worked. 210933986

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you tell me reason why if node 1 and node n are not in same component then game will last for infinite amount of time?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      we can use all nodes that are in the same component with node 1 and that can last inf time.

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

I nearly got D — used int instead of long long :P

»
16 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For A:

If \sum a_i > \sum b_i, Tsondu wins. Else if \sum a_i < \sum b_i, Tsondu wins.

I think the first "Tsondu" should be "Tenzing". Is it a typo?

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

There is another solution for E. Let dp[i] be the answer for all points with x < i. Also, let f(i, j) be a sum of costs of points with j <= x < i and y < k - i. As triangles do not intersect, dp[i] = min(dp[i - 1] + f(i, i - 1), min(dp[j] + (i - j)A + f(i, j))) for all j < i. First part of the formula means simply adding points with x = i - 1 to dp[i - 1]. Second part means there is a triangle with a vertex (j, k - i). f(i, j) can be simply calculated with Persistent Segment Tree for O(nlogn) precalculation and O(logn) for a query. min(dp[j] + (i - j)A + f(i, j)) can be calculated with Li Chao Tree. So total time complicity is O(nlog^2n). Code: 210975752

»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Sadly,i misread E and do not know that k is given. Can the problem be solved in polylog time then?

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As in choose some k then solve it? If so, then the min possible k is most likely optimal.

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean you can choose any K in one operation

      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        then you chose k=x+y at each step and remove point at 0 cost

        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it +25 Vote: I do not like it

          Yes. I am stupid.

          • »
            »
            »
            »
            »
            »
            16 months ago, # ^ |
            Rev. 2   Vote: I like it +18 Vote: I do not like it

            A version where you're limited to some amount of triangles or that each triangle has a base cost added to the edge cost is interesting. It's easy to solve it in polynomial time using max flow I think, but it's quite a big polynomial. I wonder if there's some way to solve this one fast.

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

:(

I actually really liked problem D. I don't know how to explain it, it's just fun to implement problems like this one (At least in the messy way I did it).

Buuut the statement is just toooo unclear. It also seems like many people had their solutions broken by system tests.

:(

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Yes, I still can not understand problem D at all!

  • »
    »
    16 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    which part of the statement was unclear to you (im kinda curious). I thought the statement was perfect and defined everything well.

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

      For me, the ambiguous part is restriction No 3. I can read the sentence more than a dozen times without really getting it. I imagine if the problem is described more mathematically, it will be easier for readers to get the precise meanings in shorter time.

      • »
        »
        »
        »
        16 months ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        really? is sum of time among all sets such that u \in S and v \notin S + time of all sets such that u \notin S and v \in S easier to understand than time of exactly one of u, v?

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

          I read it as exactly one of --> "The total time that u plays" OR "The total time that v plays" must not exceed yi. Ofc this is incorrect, even the test cases throw that under the bus, but if one has to experiment with testcases to decipher the meaning of a problem, it clearly isn't clear. Thank you for your explanation of the statement, ironically it really was simpler and better and hence my upvote for putting this information.

          Note that I am relatively inexperienced, and English is my 1.5-ish language.

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

          That saved me lot of time, but I really thing that it was better, if it was defined mathematically in problems, like you did. Otherwise, I lost many times think in the wrong way.

»
16 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I just forgot visited array in D and still passed.
Why am I the one to always get stuck on the weak pretests.
Anyways next round rated lol

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

Like these problems and +118 rating points:)

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I did D 1842D - Tenzing and His Animal Friends using simulation. 210925507

Approach:

  1. Model as a graph problem and maintain two disjoint sets, yes and no
  2. Initially yes={1, 2, 3, ... , n-1} and no={n}
  3. Loop, each iteration:
    i. Query mn: minimum edge connecting vertices inside different sets
    ii. If no such edge exists then output inf and exit
    iii. Else if mn == 0 then we need to move corresponding vertices from yes to no
    iv. Else we 'play' a game with length=mn with all people inside yes and subtract mn from all edges
    v. Break if 1 gets removed from yes

This means each iteration we remove k>=1 friends from yes, which means at most n games are needed, and at most max(n)*max(yi) == 1e11 total play time.

Implementation wise, I used adjacency matrix for the graph and a binary string to indicate the yes set. resuling in O(n**3)

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

I managed to get full point on problem A by literally implementing the game. I took the monsters from both Tenzing and Tsondu, quicksort them, take the maximum of each array. If one monster dies, decrease the number of monsters. Rinse and repeat.

For the second question, I am extremely unfamiliar with bitmasks, so I wasn't be able to solve it :(

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

    Oh wow. I just read the A tutorial. I also simply implemented the game. :)

    As for problem B, well, here's a reason for you to study/practice bitmasks more!

»
16 months ago, # |
  Vote: I like it +96 Vote: I do not like it

Dear MikeMirzayanov, platelet, errorgorn, Alexdat2000

I have pinged you to report some suspicious submissions from 3 Indian guys from the same college (IIT Roorkee) in this contest. Their submissions are very similar in style and it looks like they've just changed variable names. Linking the submissions for reference:

Numinous210931590

fyre210935593

nano_nish210924576

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    all of them got similar ranks. Even their code for Problem C is same.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in C I did a not optmized DP and it work for 998ms I hope you fix the test cases my soultion is trying first 100 element and last 100 element of the number this is my code : https://codeforces.net/contest/1842/submission/210953786

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

Video Solutions for A-E

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

Hi ladies/bros I am facing difficulty understanding the editorial and the DP approach of $$$G$$$. Maybe because I am dumb... But would you please help me? I posted a blog on the MSE site.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, I love E's code, it is elegant and precise! I will learn this style for fast coding and debug-free. Thank you authors ^^

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem E, I defined dp[i] as the cost of removing all elements from the triangle of ht 'i' (ending at (k,0)).

The transitions will look like dp[i] = min((i-j-1)*A + dp[j] + sum [ X = {k-i,k-j-1} : Y = {0 : j} ] (assuming that from(i) -> (j+1) is a hypotenuse of a type 1 triangle). We can store this information in a segment tree and query it, later we can update the i'th index with (dp[i]-i*A) and for the sum [ X = {k-i,k-j-1} : Y = {0 : j} ], we can update it when we go fromi -> i+1 and get some new points to take care of using lazy propagation.

Video Solution — https://www.youtube.com/watch?v=l1j3dwvopZs

Submission — https://codeforces.net/contest/1842/submission/211025258

»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone explain task B in more detail. Where and why x|y!=x. Thank you.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    If x|y != x , then y has a bit that x doesn’t have

»
16 months ago, # |
  Vote: I like it +33 Vote: I do not like it

I still can't understand solution to $$$E$$$. The editorial for it is bad. Can someone explain it in understandable way? ("It is possible to do it with segment tree" is not understandable way)

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

    Alright, I solved it and will try to explain.

    Firstly, let's mirror picture via line $$$y = k / 2$$$, so point $$$(x, y)$$$ will become $$$(x, k - y)$$$. It will be easier to work with. Triangles can't intersect — it is better to merge them, as if some point belongs to one of the original two, it will also belong to the merged one.

    We also will do one more preparation step. In original problem each point either belongs to one of triangles, or its cost has to be added to the answer. Change problem: for every point if it belongs to one of triangles, we will subtruct its cost from answer, otherwise — not. Then we will simply add to this answer sum of costs of all points.

    Let $$$dp[i]$$$ be the cost for all points, which $$$y <= i$$$ (don't forget, we flipped $$$y$$$ coordinate) (all these dp values will be non-positive, as we can just not make any triangles). Now we are choosing some $$$j \le i$$$, to which $$$y$$$ coordinate we will draw triangle (if $$$j = i$$$ the triangle is "empty", there will be no problems with it later). So the triangle is bounded by lines $$$x = j$$$ and $$$y = i$$$. We can't make any additional triangle between $$$i$$$ and $$$j$$$. So we can add to result only $$$dp[j]$$$. And finally, there are some points, which are covered by this new triangle. Let $$$C[i][j]$$$ be the $$$-$$$ (negative) sum of all costs of all points $$$(x, y)$$$, such that $$$x \ge j$$$ and $$$y \le i$$$. We are ready to write initial transition formula: $$$dp[i] = min_{j \le i}(dp[j] + (i - j) \cdot A + C[i][j])$$$. Rewrite: $$$dp[i] = i \cdot A + min_{j \le i}(dp[j] - j \cdot A + C[i][j])$$$.

    How to find that $$$min_{j \le i}(dp[j] - j \cdot A + C[i][j])$$$. Let's store these values in segment tree. Then for $$$i$$$ we do following. Firstly, we add all points with $$$y = i$$$ to the structure. Assume, we add point $$$(x, i)$$$. Then by definition of $$$C$$$ its cost has to be added to (subtracted from) $$$C[i][j]$$$ for all $$$j \le x$$$ (We will not store $$$i$$$ dimension of $$$C[i][j]$$$). Now we ask for minimum on segment $$$[0, i]$$$. Let it be $$$X$$$. We update global answer by $$$X + i \cdot A$$$. And finally, we set on position $$$i$$$ the value to $$$X + i \cdot A - i \cdot A = X$$$.

    Hope, this is understandable. I'm quite confused by number of submissions to this problem, it looks for me difficult.

    Upd. Ough, they updated editorial. Now it is understandable.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I did 1842D — Tenzing and His Animal Friends using Dijkstra which feels very intuitive. 211041880

1-Initialy you only have 1 and you propagate the edges you have and push them into priority queue

2- once you find a new friend at time T you push the old string and the time that string is going to played is just T — last, after that you make this friend '1' on your string because you can no longer play wihtout him and not violate the rules

3- terminate when you find the nth friend or the pq is empty

4- if you didn't visit nth friend print inf else print the sum of time and strings played

I think that this approach is more intuitive since you are essentialy simulating the process and playing with the lowest amount of friends until you can't any more

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

For problem D: can anybody explain why this greedy solution works?

  1. If 1 and n are not connected then answer is inf as Tenzing could always play with 1 for eternity

  2. Using two vectors bad and good. Bad stores all the friends that cannot play any further and good stores the friends that can play now (Thus, at the start bad will contain only the last element n and good will have other elements)

  3. calculate the minimum value of dis[x][y] for all x in bads, all y in good (i.e. the next friend that will become bad). let this value be mn. Now all the elements in good will play for time mn
  4. Now update the bad and good arrays as well as the distance matrix
  5. Do steps 3, 4 until element 1 becomes bad

Link to AC code

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

    I believe we can prove it with induction. Let me know if I'm missing something, I found the problem quite hard for the number of solves.

    Let the move $$$(S, t)$$$ represent the move "Select the subset $$$S$$$ with time $$$t$$$". We model the problem as in the editorial (with a weighted graph $$$G = (\{1,\dots, n\}, E)$$$)

    Set $$$S_0 := \{1,\dots, n-1\}$$$. All the edges of the form $$$e = (\cdot, n)$$$ will only be affected with moves of the form $$$(S_0, \cdot)$$$. Thus we can't make optimal moves without doing the operation $$$(S_0, \cdot)$$$ as most as we can. So in other words in the optimal moves there will be the move(s) $$$(S_0, \cdot)$$$ somewhere (notice that the order in a valid moveset does not matter). So let's do the operations first as much as we can (in the simulation/algorithm).

    Now since we exhausted all the edges $$$e = (\cdot, n)$$$ (if one of them gets affected, all of them get affected) we can't make any more moves $$$(S_0, \cdot)$$$. This means that in the new moves $$$S'$$$, if $$$(u, n)\in E$$$ then $$$u\not\in S'$$$ (we can't pick such $$$u$$$ anymore).

    The current state of the graph is equivalent to the graph state where all the edges connecting $$$v$$$ and $$$u$$$ instead connected $$$v$$$ and $$$n$$$ (with the same weight). This is because any valid move would still be valid and any non-valid move would, again, still be non-valid. So we can delete vertices $$$u$$$ such that $$$(u, n)\in E$$$ (since they cannot get picked) and for every edge $$$(v, u)$$$ ($$$v\neq n$$$) add $$$(v, n)$$$ (with the same weight). We can then move the induction step to the new graph (which will have fewer vertices).

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't seem to understand problem G at all. Which are the factors of each term? Won't some of the terms products consist of different ai or different x? Please can someone explain the solution in more detail?

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'd stuck in F for long... I feel a little confused now.

For a case that the $$$root$$$ is not actually centroid, the subset of $$$\{1, 2, \cdots, n\}$$$ we choose as black nodes itself is valid, but we used a wrong way to calculate the value of the tree.

Because, for every subset we choose, the result from a wrong calculation is absolutely less than the result from a proper calculation, so the wrong result doesn't affect the final answer.

Above is the part I can understand. And here is my problem:

We've proved wrong result is no need to be worried about, but how to prove we can reach the optimal result at last?

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Because if we pick the correct centroid the answer is correct

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

sry。where is "Statements and editorials will be available in Chinese (Simplified) after the contest.",please,thank you. QAQ

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

What is the meaning of dp(i)=min(dp(i−1)+1,min{dp(j)|a[j+1]=a[i],j+1<i}) in C tutorial

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    If we keep the $$$i-th$$$ ball , then the value is $$$dp(i−1)+1$$$.

    If we erase $$$(j+1,j+2,j+3,...,i)-th$$$ bals , then the value is $$$\min\{dp(j)|a[j+1]=a[i],j+1<i\}$$$.

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To determine j + 1 index we have to traverse from 0 to i — 2 or through every duplicate in the prefix but this is O(N2) right?

      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        We can save the min $$$dp_j$$$ such that $$$a_{j+1}=x$$$ for all x.

        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Didn't get it like how tho?

          • »
            »
            »
            »
            »
            »
            16 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            refer to the standard solution for better understanding

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why do we add plus one to dp[i-1], isn't dp[i] storing max number of balls that can be possibly removed at index i?

      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no dp[i] stores the min number of balls that can be kept.

»
16 months ago, # |
  Vote: I like it +21 Vote: I do not like it

It appears that the time limit of 2 seconds for problem 1842F is too tight for other languages except C++. I have tried all the optimizations I can think of in a Java implementation, but still see TLEs (and bunch of tests more than 1900 ms). Another evidence is, as of now, there are 10 pages of Accepted submissions, all in C++.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Try to hack me.
https://codeforces.net/contest/1842/submission/210940413
»
16 months ago, # |
Rev. 2   Vote: I like it +84 Vote: I do not like it

In fact, there is an $$$O(n)$$$ solution for problem E(submission). I have explained it in in the "Alternative Solution" section.

»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Who can translate problem D in a clear way for me? I can not understand it at all.

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

    The solution is that we can construct the sets $$$s_1,s_2,s_3,...,s_k$$$, such that $$$s_i\subset s_{i+1}$$$.

    So we only care about when each element is added to the set.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D is too difficult to understand:

Can any one explain for me the #3 restriction ? 1842D - Tenzing and His Animal Friends

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the third condition "total time that exactly one of $$$u_i$$$ and $$$v_i$$$ is playing with Tenzing" refers to the sum (time that $$$u_i$$$ is playing and $$$v_i$$$ is not playing) + (time that $$$v_i$$$ is playing and $$$u_i$$$ is not playing).

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem C:

Maybe we can directly calculate the balls that are selected.

We can do DP in the following way:

$$$f[i]=max(f[i-1],max(f[j-1]+i-j+1)|a[i]=a[j]))$$$

The problem then turns into calculating the second part in the first max function.

By observing the part we can see that only $$$f[j-1]-j+1$$$ is needed.

So we can use $$$g[i]$$$ to store the position $$$j$$$ of number $$$i$$$ that make $$$f[j]-j+1$$$ the maximum

Actually it's similar to the tutorial, but just happy to share a maybe different solution!

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

The Disjoint Set Union used in the alternative solution of E is special (at least I do think so). I didn't understand how to use it at first sight. I use set instead.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Disjoint Set Union is used in this way, making the representative element of each position equal to the first non-zero position after this position. You can check out the Alternative Code $$$O(n\alpha (n))$$$.

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

I solved C, by maximizing balls selected.

dp[i] = max balls we can select till ith index.

We keep track of the last index with value a[i], unordered_map<int, int> last.

We iterate the balls. dp[i] = dp[i-1]

if last.count(a[i]) > 0 then

let's j is the last index of a[i] value.

We have to 2 options for choosing balls:

  1. Take all balls from j to i + dp[j-1]

  2. Take all balls from j+1 to i + dp[j]

Example:

a[] = {1, 4, 1, 2, 1}

index = 1, 2, 3, 4, 5

at index 5:

  1. We can take balls at index 4, 5 + dp[3].

  2. We can take balls at index 3, 4, 5 + dp[2]

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, I know I am replying to a 6 month old comment, but I was solving this problem now. I thought of exactly the same approach, but I don't get why you considered j to i and j+1 to i, I only considered j to i, and hence was failing. Here is my code for your reference. Glad, if you could explain why you took the latter case. Thanks in advance!

»
16 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Bad round! Problem B is harder then 1100, like 1300. I think C easier than B! Geometry in E? Are you kidding me? Random in G and H? They are impossible! Codeton4 was better:(

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In editorial for H:

It can be found that $$$\le 1$$$ condition limits variables later in position in $$$p$$$ to be less than $$$0.5$$$, and $$$\ge 1$$$ condition limits variables later in position in $$$p$$$ to be greater than $$$0.5$$$.

I think here the limitation should be on the previous variables.

»
16 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Elaborating on problem F:

Firstly, observe that all the black nodes will form a single connected component, otherwise the tree value is suboptimal.

Let $$$\mathrm{sub}_v$$$ denote the number of black nodes in the subtree of $$$v$$$. The value of the tree is defined as $$$\sum |(k - \mathrm{sub}_v) - \mathrm{sub}_v|$$$.

Life would be easier if it were just $$$\sum (k - \mathrm{sub}_v) - \mathrm{sub}_v$$$ (without absolute value). But there isn't always such a case, is there? It turns out that $$$(k - \mathrm{sub}_v) \ge \mathrm{sub}_v$$$ is always true if your root is the centroid of the component of black nodes (since by definition, for every subtree of a centroid — $$$\mathrm{size}_i \le \frac{n}{2}$$$).

So now assuming the root of the tree is this centroid, the value is given by $$$\sum k - 2 \cdot \mathrm{sub}_v$$$, which is $$$(n - 1) \cdot k - 2 \cdot \sum \mathrm{sub}_v$$$.

Given this, lets try every node as said root and lets fill black nodes around it one at a time and update the answer for each $$$k$$$. Each black node $$$v$$$ contributes $$$-2 \cdot \mathrm{depth}_v$$$ to the answer. To maximize this, we choose the next black node to be the one with minimum depth at each stage.

In doing so, for every $$$k$$$ we would have found the answer for when the root also happens to be the centroid and this value will be better (greater) than the value in all cases when it is not. So we don't have to worry about them.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't the decimal value of 0x3f = 63, how is that used to initialize the dis matrix in problem D? Is it related to LLMAX in any way?

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

    memset works not by setting all integers equal to the given value, but instead it sets all bytes to the given value. A long long variable is 64-bit and thus, it contains 8 bytes. Each of these bytes are set to 0x3f = 0b00111111. This means that each long long in the array will be set to 0b0011111100111111001111110011111100111111001111110011111100111111 = 0x3f3f3f3f3f3f3f3f or $$$4\,557\,430\,888\,798\,830\,399$$$ in decimal. This is not related to LLMAX but it's large enough to be considered "infinity".

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the solution to D is too vague, and doesn't explain the specific meaning of the dist array!

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody tell me why does my code give TLE on 2nd test in C?: 216987462. Shouldn't time complexity of the code be O(3*N + N*sqrt(N)) (input — N, calc — N, reset — N, solve — N*sqrt(n))?

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

Please help me understand problem D. I think I have misunderstood the question.

5 3
10100 2
10010 2
11000 1

Why is this a wrong solution to the sample case ? The total times of all animals are -

S[1] = 5, S[2] = 1, S[3] = 2, S[4] = 2

For constraints -

1 : 1 3 2 => S[3] <= 2
2 : 1 4 2 => S[4] <= 2
3 : 2 3 1 => S[2] <= 1
4 : 2 5 1 => S[2] <= 1

Exactly one of the two satisfy. What am I understanding wrongly?

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

Even though it's simple, in problem F, the proof for the black nodes being a connected component in an optimal coloring should have been mentioned in the editorial.

  1. For $$$k = 1$$$: It's trivially true.
  2. For $$$k \geq 2$$$:
    Let's assume we have two black nodes $$$u$$$ and $$$v$$$ in an optimal coloring such that the path between them has only white nodes.

    Observation 1: Uncoloring either of $$$u$$$ or $$$v$$$ and coloring some other white node on the path from $$$u$$$ to $$$v$$$ in place of them only affects the value of edges lying on the path from $$$u$$$ to $$$v$$$.
    proof

    Now, let's consider the edge $$$(u, w)$$$ such that $$$w$$$ is the first node on the path from $$$u$$$ to $$$v$$$. Let $$$x$$$ be the number of black nodes in the component on the side of $$$u$$$ and $$$y$$$ be the number of black nodes in the component on the side of $$$v$$$.
    • Case 1 $$$(x \geq y)$$$: In this case, uncoloring node $$$v$$$ and coloring node $$$w$$$ increases the value of all edges on the path from $$$u$$$ to $$$v$$$ except the edge $$$(u, w)$$$. Values of edges which don't lie on the path are not affected by observation 1. Thus, the total value of the tree increases.
    • Case 2 $$$(x < y)$$$: In this case, uncoloring node $$$u$$$ and coloring node $$$w$$$ increases the value of edge $$$(u, w)$$$ and does not affect values of other edges on the path. Values of edges which don't lie on the path are also not affected by observation 1. Thus, the total value of the tree increases.

    So, in both cases (which are mutually exclusive and exhaustive), we have shown that the coloring was not optimal, hence our assumption was false, and there cannot exist any two black nodes in an optimal coloring which have only white nodes on the path between them.

    It follows that all black nodes must form a connected component in an optimal coloring.
  3. Note: Even though this is simpler, another proof (which I used when solving this) is to root the tree and consider the lowest node in the optimal coloring at which the number of black nodes in its subtree becomes $$$\geq k/2$$$. This proof immediately leads to the rest of the solution.

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

Is there a problem in checker's code for problem D?

Even the output and answer values are matching but it's showing the wrong answer.

Here is my submission:- https://codeforces.net/contest/1842/submission/238336885

Could anyone please help why it is coming wrong answer even with correct output of total time?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The checker is correct. It says that the total time does not match, so if you sum up the second number on each row, it won't be equal to the total time you printed at the start.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D greed: keep PQ of the constraints where one friend from the constraint is out of the set. Then you can always find the next constraint that will be met and update $$$s$$$, $$$t$$$, and the PQ accordingly. 239816163

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

problem D : it's statement is literally too much ambiguous

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

Can anyone explain the m' of problem I in detail?

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

    i can't understand the last sentence of the official editorial