### ikar's blog

By ikar, 8 years ago, translation,

Excuse me for my english, but I tried very hard to.=)

#### A: 379A - New Year Candles

Let cura amount of new candles, curb — amount of burnt out. Initially cura = a, curb = 0, after burning all cura new candles, amount of hours incremented by cura and curb +  = cura, lets make all burnt out candles into new cura = curb / b , repeat this algorithm until we can make at least one new candle. #### B: 379B - New Year Present If wallet contains more then one coin, then between orders to "put a coin" we can orders to move to adjacent wallet then back. Since for each orders to "put a coin" we spend at most 2 other orders, number of total orders for maximum test equals 300 * 300 * 3 = 270000 it less then 106.

#### C: 379C - New Year Ratings Change

We can to sort ratings in nondecrease order, then iterate by them we can keep minimal rating not used before. If ai > cur, i's user recieve ai of rating and cur = ai + 1, else ai ≤ cur then i's user recieve cur of rating and cur increased by one.

#### D: 379D - New Year Letter

We can't fairly calculate sk because of length of this string which can be very large. But note that whole string not need, we just need number of AC substrings, first and last letter. That help us to easy calculate number AC substrings for any sk for some s1, s2. Let's iterate through s1, s2 using alphabet of A, C, and any other letter. We need just first and last letter and number of AC. Using some s1, s2 we can calculate sk.

#### E: 379E - New Year Tree Decorations

Let's keep union of first i pieces, S(i) denote the area of union for the first i pieces. Then to know visible part of i's piece we need to calculate S(i) - S(i - 1), (

Unable to parse markup [type=CF_TEX]

and with end at x = 1. Union looks like a downward convex polyline, lets represent it sequence of points, adjacent are connected. So calculate i's union, if new union will be contains new segment, this segment must intersects two segments of union, this intersection we can calculate for the amount of points in union. All points lower than new segment must be erased from union. Because each segment can add at most one point in union calculating of one range is O(n2).

Coming soon.

#### G: 379G - New Year Cactus

This problem can be solved for tree by using of dynamic programming d[v][c][a], where v — vertex, c — type of vertex(whose toys are hanged or nothing are hanged there), a — number of toys hanged by Jack for this subtree, d[v][c][a] denote of maximum number of toys which can be hanged by Jill. Value d[v][c][a] can be calculated iterated through sons of v vertext and type of these vertices. Let's compress our cactus into tree by compressing each cycle into vertex. Vertex of tree will be looks like sequence of vertex from cactus which have edges not from this cycle and intermediates that belongs only to this cycle. Now we can calculate all d[v][c][a] for this tree but we must be carefully processing a vertices.

Tutorial of Good Bye 2013

• +38

 » 8 years ago, # |   -6 problem A act optimally how to prove the algorithm acting optimmally ?
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 not really related to your question but actually a "brute-force" implementation can also AC 5571273 :)edit : it's clearly optimal since make new candle when ever we can, it have the same idea with the tutorial but this may be easier to understand :p
•  » » » 8 years ago, # ^ |   -11 maybe it's not a good question seems trivial I think maybe the candle which is run out and then make a new one have different choice of run out candle and run out ones may have different levels and maybe not using them all in the same time or in different order maybe different. your answer is implement not brute force or exhaustion.I may have consider all the situation .Id like an elegant simple approach to the proof.
•  » » » 7 years ago, # ^ |   0 thank s for the brute forces explanation :p
 » 8 years ago, # |   +10 This Tutorial is too simple that I can't understand how to solve D after I read it : (
•  » » 8 years ago, # ^ |   +8 Look for example you need to calc s5 for strings s1 = CACACC and s2 = CACAA, represent s1 like 2 AC substring and first and last letter — CC,s2 = (1, CA)s3 = (3, CA) (AC + CC has no AC at the junction and we just take first and last letter)s4 = (4 + 1, CA) (+1 because of at the junction substring AC appears)s5 = (8 + 1, CA) (again).
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 I got it now.
•  » » » » 8 years ago, # ^ |   0 yes, enough to sort out first and last letter and count of AC for s1, s2.
•  » » » 8 years ago, # ^ |   0 How can I obtain s1 and s2?
•  » » » » 8 years ago, # ^ |   0 You could generate all strings using alphabet of 3 letters, important things in this strings would be first and last letter and amount of 'AC' substrings.
•  » » » 8 years ago, # ^ |   0 Great!
 » 8 years ago, # |   +16 This tutorial' english gave me cancer XD
 » 8 years ago, # |   +4 Any better explanation for problem E ?
•  » » 8 years ago, # ^ |   +3 You can separate the problem into K parts, because each part is independent of the others. To solve for just one part, you can keep the segments (points) that builds it, at first there is only one segment, from (xk,0) to (xk+1,0) and the area is currently 0. For each new segment (each new decoration) we must build the parts again. To add a new segment Bk, you need to check for every segment Ak that builds the part with the new segment Bk: Segment A and B intersect: add the segments (A.x1, max(A.y1, B.y1)) to (intersect_x, intersect_y) and from (intersect_x, intersect_y) to (A.x2, max(A.y2, B.y2)) Segment A and B don't intersect: add the segment (A.x1, max(A.y1, B.y1)) to (A.x2, max(A.y2, B.y2)) (The y coordinate for the B segment means the y for the current x). After building the parts again you have the old ones and the new ones. The amount of area that they add to the answer of this decoration is the new area minus the old area. The overall idea is not hard, it is just can be tricky to implement, specially for those who don't have much geometry skills :) (like me). You can check my code here: 5594115
•  » » » 8 years ago, # ^ |   0 I have implemented an idea similar to yours ,can you have a look and tell me why it fails case 15? http://codeforces.com/contest/379/submission/5597257
•  » » » » 8 years ago, # ^ |   +3 I have made some modifications to your code, but at the end what made it pass was adding an eps to the line intersection test: 5600093. I thought a while about it and made some test cases but couldn't come with an explanation why it is failing without that :/, does anyone know why would it fail?
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 Thanks,brunoja . I also managed to get a Happy New Year!'ed submission by adding epsilon comparison to the intersection test.
 » 8 years ago, # |   0 i thought that struct is faster than pair,but it seems not, i changed it to pair and got ac the C problem
•  » » 8 years ago, # ^ |   0 What slowed you down wasn't struct, but the comparison function. See 5602813. I modified your comparison function and got AC, passing the arguments by reference and adding a "return false" at the end. Not sure why the latter is required but without it I got a WA in test #10.
•  » » » 8 years ago, # ^ |   0 hi! thank you soo much for your explanation! its very clear and now i know where my code is wrong! it seems that it cant handle the sort when the 2 values is same, and adding "return false" seems to fix it all! thank you very much once again!
•  » » » » 8 years ago, # ^ |   0 You're welcome :)
•  » » 8 years ago, # ^ |   0 pair is basically the same as struct {int first, int second}; with some predefined comparison operators and constructors.
 » 8 years ago, # | ← Rev. 2 →   0 Problem G how to write O(N^2) dynamic solution for tree. O(N^3) is simple, but O(N^2) is not so obvious. Answer in Russian is also acceptable.
•  » » 8 years ago, # ^ |   +28 Hah, you will be surprised. O(n^2) is essentially exactly the same, but in vertex v you should not iterate a from 0 to n, but from 0 to size of subtree of v (it's obvious that a > size[v] makes no sense) which results in O(n^2) algorithm. Prove it by yourself, because it's very nice and remember that trick! This trick was used by Touma_Kazusa in his DP solution to http://codeforces.com/contest/375/problem/E which was problem from last Tuesday :).
•  » » » 8 years ago, # ^ |   0 Nice thanks .I didn't know about it before.
•  » » » 8 years ago, # ^ |   +8 Man, that's amazing! U made my day, really!
•  » » » 8 years ago, # ^ |   +3 Can you share links to other problems, which demand using this trick to solve them? Thanks in advance.
•  » » » » 8 years ago, # ^ |   +29 http://main.edu.pl/en/archive/pa/2007/barProblem J from NCPC 2012 (it's not the only solution, but one of the possible) http://ncpc.idi.ntnu.no/ncpc2012/ncpc2012problems.pdfProblem Pizzerias from Marathon24 qualifications (which I have prepared :P) http://www.marathon24.com/static/attachment/marathon24_piz_pl.pdf
•  » » » » » 8 years ago, # ^ |   0 Nice! Thanks again
•  » » » » 8 years ago, # ^ |   +21 This problem is a good example: 178F3 - Репрезентативная выборка
•  » » » » » 8 years ago, # ^ |   0 Thank you!
•  » » » » 8 years ago, # ^ |   0 Oh, I remember another one problem! In my opinion it's really brilliant, so here it goes: https://www.facebook.com/hackercup/problems.php?pid=413074315443326&round=499927843385312
 » 8 years ago, # | ← Rev. 2 →   0 Can somebody, please, post at least a sketch of the actual solution on F? Thanks, Happy new year!
•  » » 8 years ago, # ^ |   0 As someone already pointed out, this is the (almost) same problem: http://discuss.codechef.com/questions/24750/rrtree-editorial ;)
 » 8 years ago, # |   0 How to solve F?
•  » » 8 years ago, # ^ |   0
 » 8 years ago, # |   +8 How can I solve the problem F? Who can give me some idea? Thanks!
•  » » 8 years ago, # ^ |   0 This is a problem about LCA?
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +23 Indeed, this is a problem about LCA. Let end_first and end_second be the endpoints of the diameter of the tree. When inserting an new node u we first have to compute the 2^j-th ancestor of u, for all j in range 0..log2(N). After that, notice that a possibly new diameter may start from j and end at end_first, or start at j and end end_second. So, you just compare the distances to get the new diameter, and you update properly end_first and end_second. I also have some code I wrote after the contest: http://codeforces.com/contest/379/submission/5603366. I hope this helps :)
•  » » » » 8 years ago, # ^ |   0 Thanks.My English is bad,but I still hope you can get gratitude from me！HaHa.
•  » » » » 8 years ago, # ^ |   0 But I have another quetion now.When all nodes have two subtrees(except leaves),the height of a subtree is 1,another is [1,Q+1].In other words,the height of the new year tree is Q+2.Are you sure this solution will not be TLE？
•  » » » » » 8 years ago, # ^ |   0 Yes, because the complexity of the procedure add is O(lgN), and the complexity of the procedure lca is also O(lgN). Both procedures are called 2*Q` times, so this gives us a total complexity of O(Q * lgN), which i think can easily pass all the system's tests. I hope I helped :)
•  » » » » » » 8 years ago, # ^ |   0 got the key.Thanks!
•  » » » » » 8 years ago, # ^ |   +3 you can read more about LCA here https://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor I'am sure it'll help :D
•  » » » » » » 8 years ago, # ^ |   0 got the key.Thanks!
•  » » » » 6 years ago, # ^ |   0 i might not have fully understood,for a long-tailed tree the number of ancestors will be close to N i.e total vertices.I understand the expected time is log2N for that j in range 0...log2N task you did.But what about this worst-case? TIA.
 » 5 years ago, # |   +1 coming soon after X years?
•  » » 13 months ago, # ^ |   0 still coming soon, maybe next yr
 » 4 years ago, # |   0 How to solve the problem F with Centroid Decomposition
 » 4 years ago, # |   0 Still " coming soon "
 » 3 years ago, # |   0 How to solve question B?
 » 3 years ago, # |   0 How to solve question F?
 » 2 years ago, # | ← Rev. 2 →   0 here the solution problem A my doubt is, i am using pigeonhole principle here but not getting it how its actually working.
 » 4 months ago, # |   0 For problem A, what about the case where a=b?