platelet's blog

By platelet, 10 months ago,

Tutorial
Code

1842B - Tenzing and Books

Tutorial
Alternative Solution
Code
Alternative Code

Tutorial
Code

Tutorial
Code

1842E - Tenzing and Triangle

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

Tutorial
Code

Tutorial
Code

Hint 1
Hint 2
Tutorial
Code

1842I - Tenzing and Necklace

Hint 1
Hint 2
Tutorial
Code
• +573

 » 10 months ago, # |   +77 Problem D :|
•  » » 10 months ago, # ^ |   0 What's wrong with it?
•  » » » 10 months ago, # ^ |   -74 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.
•  » » » » 10 months ago, # ^ |   +16 Isn't that the case with 90% of the greedy problems?
 » 10 months ago, # | ← Rev. 3 →   -24 Editorial of D makes it seem easy but could not get it during contest
•  » » 10 months ago, # ^ |   +1 gawd bro
 » 10 months ago, # |   +87 Can anyone explain problem E in detail?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +5 I didn't understand the tutorial either.
•  » » 10 months ago, # ^ | ← Rev. 4 →   +13 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<=yi) be the x coordinate till which we draw the triangle, so dp[i] = (j-i)*A + dp[j] + c[i<=x
•  » » » 10 months ago, # ^ |   +6 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.
•  » » » » 10 months ago, # ^ |   +3 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
 » 10 months ago, # | ← Rev. 3 →   +227 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.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +74 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).
•  » » 10 months ago, # ^ |   +3 I think problem A is difficult too.
•  » » » 10 months ago, # ^ |   0 me too
 » 10 months ago, # | ← Rev. 2 →   +22 In Problem 'A' solution , sum(ai) < sum(bi) , then anser is Tenzing...typing mistake in tutorial(sorry for bad English).platelet
•  » » 10 months ago, # ^ |   +56 Thank you, it has been fixed.
 » 10 months ago, # |   0 Can someone suggest few resources or simple problems for system of difference constraints?
 » 10 months ago, # |   0 How to solve ghi
•  » » 10 months ago, # ^ |   +30 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$.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Nvm
•  » » 10 months ago, # ^ | ← Rev. 3 →   +43 For G: I am aware of two ways. Someone in the AC discord mentioned this blog: https://codeforces.com/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.
•  » » » 10 months ago, # ^ |   +19 Beautiful solution! I have learned a lot from this. However, it should be $z_i=(a_i+ivx)z_{i-1}+vxz'_{i-1}$ (:
•  » » » » 10 months ago, # ^ |   0 Oops! Fixed.
 » 10 months ago, # | ← Rev. 2 →   +3 Try hacking this submissionUpd: Uphacked, yay!
 » 10 months ago, # |   +3 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
•  » » 8 months ago, # ^ |   0 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?
•  » » » 8 months ago, # ^ |   0 we can use all nodes that are in the same component with node 1 and that can last inf time.
 » 10 months ago, # |   +5 I nearly got D — used int instead of long long :P
•  » » 10 months ago, # ^ |   +5 What a pity!
 » 10 months ago, # |   +1 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?
•  » » 10 months ago, # ^ |   +55 Thank you, it has been fixed.
 » 10 months ago, # |   +5 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
 » 10 months ago, # |   +8 Sadly,i misread E and do not know that k is given. Can the problem be solved in polylog time then?
•  » » 10 months ago, # ^ |   0 As in choose some k then solve it? If so, then the min possible k is most likely optimal.
•  » » » 10 months ago, # ^ |   0 I mean you can choose any K in one operation
•  » » » » 10 months ago, # ^ |   +14 then you chose k=x+y at each step and remove point at 0 cost
•  » » » » » 10 months ago, # ^ |   +25 Yes. I am stupid.
•  » » » » » » 10 months ago, # ^ | ← Rev. 2 →   +18 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.
 » 10 months ago, # | ← Rev. 2 →   +16 Video solutions A. Tenzing and TsonduB. Tenzing and books c. Tenzing and balls
 » 10 months ago, # |   +16 :(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.:(
•  » » 10 months ago, # ^ |   +14 Yes, I still can not understand problem D at all!
•  » » 10 months ago, # ^ |   -14 which part of the statement was unclear to you (im kinda curious). I thought the statement was perfect and defined everything well.
•  » » » 10 months ago, # ^ |   +3 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.
•  » » » » 10 months ago, # ^ | ← Rev. 3 →   +3 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?
•  » » » » » 10 months ago, # ^ |   +6 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.
 » 10 months ago, # |   +11 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
 » 10 months ago, # |   +9 Like these problems and +118 rating points:)
 » 10 months ago, # |   0 I did D 1842D - Tenzing and His Animal Friends using simulation. 210925507Approach: Model as a graph problem and maintain two disjoint sets, yes and no Initially yes={1, 2, 3, ... , n-1} and no={n} Loop, each iteration:i. Query mn: minimum edge connecting vertices inside different setsii. If no such edge exists then output inf and exitiii. Else if mn == 0 then we need to move corresponding vertices from yes to noiv. Else we 'play' a game with length=mn with all people inside yes and subtract mn from all edgesv. 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)
•  » » 10 months ago, # ^ | ← Rev. 2 →   +3 Shouldn't it be O(n^2) as done here 211001107
 » 10 months ago, # | ← Rev. 2 →   +13 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 :(
•  » » 10 months ago, # ^ |   +6 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!
 » 10 months ago, # |   +96 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:
•  » » 10 months ago, # ^ |   +8 all of them got similar ranks. Even their code for Problem C is same.
 » 10 months ago, # |   0 My code didn't accept when my idea is identical with the tutorial in problem A :(
•  » » 10 months ago, # ^ | ← Rev. 3 →   0 Hlo new-in-coding sum1 and sum2 are getting integer overflow change them to long long
 » 10 months ago, # |   0 Hey hi! I have implemented code for problem B.. But I'm not knowing which edge case I have missed. It's giving wrong answer in test 2, 19th token... 210999740
 » 10 months ago, # |   0 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.com/contest/1842/submission/210953786
 » 10 months ago, # |   0 Can anyone explain me recursive dp approach for Problem C?
 » 10 months ago, # |   +5 Video Solutions for A-E
 » 10 months ago, # |   +9 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.
 » 10 months ago, # |   0 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 ^^
 » 10 months ago, # |   0 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
 » 10 months ago, # |   +8 Can someone explain task B in more detail. Where and why x|y!=x. Thank you.
•  » » 10 months ago, # ^ |   +16 If x|y != x , then y has a bit that x doesn’t have
 » 10 months ago, # |   +33 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)
•  » » 10 months ago, # ^ | ← Rev. 2 →   +4 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.
 » 10 months ago, # |   0 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 queue2- 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 rules3- terminate when you find the nth friend or the pq is empty4- if you didn't visit nth friend print inf else print the sum of time and strings playedI 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
 » 10 months ago, # | ← Rev. 2 →   0 For problem D: can anybody explain why this greedy solution works? If 1 and n are not connected then answer is inf as Tenzing could always play with 1 for eternity 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) 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 Now update the bad and good arrays as well as the distance matrix Do steps 3, 4 until element 1 becomes bad Link to AC code
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 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).
 » 10 months ago, # |   0 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?
 » 10 months ago, # |   0 can anyone modify my code of Problem C: Tenzing and balls.....It shows TLE...my submission
 » 10 months ago, # |   0 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?
•  » » 10 months ago, # ^ |   +18 Because if we pick the correct centroid the answer is correct
 » 10 months ago, # |   0 sry。where is "Statements and editorials will be available in Chinese (Simplified) after the contest.",please,thank you. QAQ
•  » » 10 months ago, # ^ |   0 On the announcement
•  » » » 10 months ago, # ^ |   0 thank you！
 » 10 months ago, # | ← Rev. 3 →   0 What is the meaning of dp(i)=min(dp(i−1)+1,min{dp(j)|a[j+1]=a[i],j+1
•  » » 10 months ago, # ^ |   +8 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 •  » » » 10 months ago, # ^ | 0 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? •  » » » » 10 months ago, # ^ | +8 We can save the min$dp_j$such that$a_{j+1}=x$for all x. •  » » » » » 10 months ago, # ^ | 0 Didn't get it like how tho? •  » » » » » » 10 months ago, # ^ | 0 refer to the standard solution for better understanding •  » » » 10 months ago, # ^ | 0 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? •  » » » » 10 months ago, # ^ | 0 no dp[i] stores the min number of balls that can be kept.  » 10 months ago, # | +21 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++. •  » » 10 months ago, # ^ | +10 I managed to get Accepted once with https://codeforces.com/contest/1842/submission/211112289. There are at least 5 tests completed with 1996 ms, under the limit only by 4 ms! The problem will be more friendly to have a time limit of 3 seconds or so instead.  » 10 months ago, # | 0 Try to hack me. https://codeforces.com/contest/1842/submission/210940413  •  » » 10 months ago, # ^ | 0 Upd: Hacked.  » 10 months ago, # | ← Rev. 2 → +84 In fact, there is an$O(n)$solution for problem E(submission). I have explained it in in the "Alternative Solution" section.  » 10 months ago, # | +4 Who can translate problem D in a clear way for me? I can not understand it at all. •  » » 10 months ago, # ^ | +33 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.  » 10 months ago, # | 0 problem D is too difficult to understand:Can any one explain for me the #3 restriction ? 1842D - Tenzing and His Animal Friends •  » » 10 months ago, # ^ | 0 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). •  » » » 10 months ago, # ^ | 0 Thank you for your explanation, I am not too good in English so this sentence is too difficult to understand for me.  » 10 months ago, # | 0 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 maximumActually it's similar to the tutorial, but just happy to share a maybe different solution! •  » » 9 months ago, # ^ | 0 Noice, I was looking for the same. •  » » 8 months ago, # ^ | 0 In editorial where are we using the condition ai=aj can u pls explain?  » 10 months ago, # | ← Rev. 2 → 0 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. •  » » 10 months ago, # ^ | 0 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))$.  » 10 months ago, # | ← Rev. 4 → 0 Nice tutorials thank you!  » 10 months ago, # | ← Rev. 2 → 0 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 last.We iterate the balls. dp[i] = dp[i-1]if last.count(a[i]) > 0 thenlet's j is the last index of a[i] value.We have to 2 options for choosing balls: Take all balls from j to i + dp[j-1] Take all balls from j+1 to i + dp[j] Example:a[] = {1, 4, 1, 2, 1}index = 1, 2, 3, 4, 5at index 5: We can take balls at index 4, 5 + dp[3]. We can take balls at index 3, 4, 5 + dp[2] •  » » 4 months ago, # ^ | 0 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!  » 10 months ago, # | -38 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:(  » 10 months ago, # | 0 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. •  » » 10 months ago, # ^ | +10 ok, fixed.  » 10 months ago, # | 0 Please help! problem c sub: 211718555why this solution for test case 1 on my pc gives correct answer of4 3but on cf servers test 1 gives me wrong answer of2 3  » 10 months ago, # | +13 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. •  » » 10 months ago, # ^ | ← Rev. 2 → 0 nvm  » 10 months ago, # | 0 https://codeforces.com/contest/1842/submission/211358322 can someone explain why this is giving TLE ? Thank You  » 10 months ago, # | 0 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? •  » » 10 months ago, # ^ | ← Rev. 2 → 0 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". •  » » » 4 months ago, # ^ | 0 Thanks for putting it out so clearly  » 9 months ago, # | 0 I think the solution to D is too vague, and doesn't explain the specific meaning of the dist array!  » 9 months ago, # | 0 in problem c, can someone explain me what is happening in these lines of codedp[i] = min(dp[i — 1] + 1, buc[a[i]]); buc[a[i]] = min(buc[a[i]], dp[i — 1]);  » 9 months ago, # | ← Rev. 2 → 0 Can someone explain C's tutorial to me? I ended up doing a knapsack-ish solution where I either decide to use the current ball in an array or not. Specifically, I got lost here: what does$dp_j |$mean?We can write a DP.$dp_i$denotes the minimum number of points we do not delete when considering the subarray$a[1 \ldots i]$. We have$dp_i = \min (dp_{i-1}+1, \min { dp_j | a_{j+1}=a_i, j+1
 » 9 months ago, # |   0 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))?
•  » » 9 months ago, # ^ |   0 UPD: I just shouldn't have used sqrt decomposition
•  » » 3 months ago, # ^ |   0 Can u help why this gives TLE https://codeforces.com/contest/1842/submission/243680975
 » 7 months ago, # |   0 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] = 2For 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?
 » 6 months ago, # | ← Rev. 2 →   0 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. For $k = 1$: It's trivially true. 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$. proofAn informal proof for this observation is that one can imagine all other nodes of the tree to be parts of trees hanging from the nodes on path from $u$ to $v$. All other edges will be part of these trees, and their value depends only on the number of black nodes in the subtree of their lower node, which is not affected by uncoloring/recoloring nodes on the path from $u$ to $v$. 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. 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.
 » 4 months ago, # | ← Rev. 2 →   0 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.com/contest/1842/submission/238336885Could anyone please help why it is coming wrong answer even with correct output of total time?
•  » » 4 months ago, # ^ |   0 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.
 » 4 months ago, # |   0 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