By cookiedoth, history, 2 years ago, translation,

Hi!

I'm glad to invite you to Codeforces Round #526, which will be held on 10.12.2018 19:35 (Московское время). The round will be rated for both divisions.

Problems were prepared by me, TheWayISteppedOutTheCar, CTPAX, Egor.Lifar.

Thanks to ismagilov.code, Kuyan, 300iq, alexey_kuldoshin, Jatana for testing, arsijo and vintage_Vlad_Makeev for helping us and MikeMirzayanov for the great Codeforces and Polygon platforms.

You will be given 6 problems in each division and 2 hours to solve them.

UPD:

The scoring distribution in Div. 1: 500-1000-1500-2000-2000-2500

The scoring distribution in Div. 2: 500-1000-1500-1750-2250-2750

UPD: Congratulations to winners!

Div. 1:

Div. 2:

UPD: Editorial

• +170

 » 2 years ago, # |   +28 I think the date is wrong
•  » » 2 years ago, # ^ |   0 Fixed
 » 2 years ago, # | ← Rev. 3 →   +164 I am confused.
•  » » 2 years ago, # ^ | ← Rev. 4 →   +85
•  » » 2 years ago, # ^ |   +38
•  » » 2 years ago, # ^ |   +8 so I decided that I do the contest and I did.
•  » » » 2 years ago, # ^ |   +18 batman taught you a good lesson :P
 » 2 years ago, # |   +45 Aww, new codeforces round, new chance to fall!
•  » » 2 years ago, # ^ |   +10 Reverse psychology — Activated!
 » 2 years ago, # |   +12 I am very interested in knowing what vintage_Vlad_Makeev is planning to do??XDD
•  » » 2 years ago, # ^ |   0 You missed this I guess :)
•  » » » 2 years ago, # ^ |   -6 Heisenberg dude what I meant was that I was curious to know what vintage_Vlad_Makeev was planning to do with his rating! See his graph he is trying something out! Maybe he wants to visit all colors or maybe something else!!XD
•  » » » » 2 years ago, # ^ |   -14 He helped in creating the problems so can't participate.
•  » » » » 2 years ago, # ^ |   +43 He is trying to look like Bitcoin :)
•  » » 2 years ago, # ^ |   0 He's singing : Oh take me back to the start!
•  » » 2 years ago, # ^ |   +3 I asked him. He didn't reply :/
 » 2 years ago, # |   -9 Time is always a severe problem for us Chinese fanatic.
•  » » 2 years ago, # ^ |   -9 yes!Next regular time is 9:45pm, I think this is ok,but too far.
•  » » » 2 years ago, # ^ |   -9 Sounds like u have long awaited for that aha
•  » » » » 2 years ago, # ^ |   0 oh!There will be no class tomorrow morning，I am ready gang tonight,after i'm ready the first question,the registration channel is closed.
•  » » » » 2 years ago, # ^ |   0 I'm not sure i will join this contest,so I haven't register advance!!! no, the The prophecy is coming true.（唉！真的要等到23号才能打）
 » 2 years ago, # |   0 “Is this rated?” hURr DuRR
•  » » 2 years ago, # ^ |   +4 Yes，it is
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -18 Nah mate, you’re wrong
•  » » » 2 years ago, # ^ | ← Rev. 3 →   -18 f
 » 2 years ago, # |   -38 will this rate my rating
 » 2 years ago, # |   +2 i hope that problems will be graduated in terms of difficulty ^^
 » 2 years ago, # |   -34 yey i cant wait for all of you to lose rating! :D
 » 2 years ago, # |   +21 2300
•  » » 2 years ago, # ^ |   +9 :((
 » 2 years ago, # | ← Rev. 4 →   -14 ...
 » 2 years ago, # |   +2 Again a new chance to restart coding...
 » 2 years ago, # | ← Rev. 2 →   +14 does cf stops producing 5 problem Div2.s ?
•  » » 2 years ago, # ^ |   -11 problem no happen not will .j
 » 2 years ago, # |   0 Wish for 2400.
 » 2 years ago, # |   +1 how many problems are shared between the divisions ?
•  » » 2 years ago, # ^ |   +19 3 problems
•  » » » 2 years ago, # ^ |   0 thkns!
 » 2 years ago, # |   0 Yes I wont lose rating
 » 2 years ago, # |   +32 Div2A was such broken english that I couldn't comprehend the problem statement. After reading the statement multiple times I reached an understanding which was in conflict with pretest 1 answer. I submitted a question and nobody answered it. So I guess I'm just gonna skip this round then.Please don't google-translate russian problems into english. If you can't write english problem statements, ask help from someone who speaks english. If you can't explain a simple problem (such as div2A level) in an understandable way, please don't write problem statements at all.
•  » » 2 years ago, # ^ |   +9 I was confused by Div1A not mentioning that you can choose u,v freely and talking about 'the city u/v' and 'the path' (not a city/path).So I asked 'what are u,v, they are not in the input' — answer: 'Yes'
•  » » 2 years ago, # ^ |   +3 Problem statement in russian was very unclear too — I doubt we should blame google-translate here.
 » 2 years ago, # |   +3 How can i register now?
 » 2 years ago, # |   -29 The comment removed because of Codeforces rules violation
•  » » 2 years ago, # ^ |   +5 yeah, difficult to understand
 » 2 years ago, # |   +18 RIP problem statements
 » 2 years ago, # |   +14 Lol. C was harder than D and E. How to solve C?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +35 Use a segment tree to quickly calculate, for any segment [l, r], if there is a path that contains all values in [l, r].Each node should store a pair representing a path, but combining pairs requires a lot of casework and isn't fun :(
•  » » » 2 years ago, # ^ |   +16 Nice.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +16 Actually restrictions were rather kind, so something like checking for all pairs of endpoints of two paths that all other endpoints lie on a path between them still passes. So you could do it without any casework.
•  » » » 2 years ago, # ^ |   0 What does this comment has to do with problem C?...
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   +8 The l and r are the interval of node i in the DFS traversal of the tree. So we can store the l[p - 1[i]] in a max segment tree, and the r[p - 1[i]] in a min segment tree, then all values 0, 1, ..., K lie on an ascending path iff ltree.query(0, K) < rtree.query(0, K).EDIT: I was working on this at the end of the contest but there was too much casework glueing together two paths and my code was a mess so now I only got problem B, RIP :(
 » 2 years ago, # |   +8 How to solve DIV1B?
•  » » 2 years ago, # ^ |   +6 for each prefix, calculate the maximum string you can make, then add it to the answer.
•  » » 2 years ago, # ^ |   +11 The characters being 'a', 'b' allows for a pretty easy solution that is barely programming. You can consider s and t as binary strings and iterate through their prefixes. While the prefix difference is less than k, you add it to the sum and when it grows larger you add k instead.→ Reply
 » 2 years ago, # |   +34 Was the intended solution to E convex hull trick? If so why is it after C and D in the list? :Dd
 » 2 years ago, # |   +8 can someone explain div 2 C problem and its solution?
•  » » 2 years ago, # ^ |   +2 We have to find the no. of index sequences where in which all the string elements at those indexes are equal to 'a' and between every two adjacent indices there must be atleast one 'b'.So, we divide the string into pieces, where each piece contains those "a's" which are preceded by same no. of "b's". e.g. : "aabaabbaaabab: is divided into "aab" "aabb" "aaab" "ab". Now, from each piece, we have the choice of taking either 0, 1, 2... till count of "a's" in that piece. So, total "count of a's in that piece + 1" choices. Now, to find the total required sequences, we multiply the no. of choices from each piece. But, since we want to choose a non-empty sequence, we subtract 1.
•  » » » 2 years ago, # ^ |   0 Sorry I'm facing problem yet to understand the problem. Help me please:For the example you given, "aabaabbaaabab, [0], [1], [0][1] are also valid sequence. Right? But, how do they satisfy the condition that there must have at least one b between two adjacent indices?
•  » » » » 2 years ago, # ^ |   0 [0, 1] is not a valid sequence as the first two a's don't have any 'b' in between.
•  » » » » » 2 years ago, # ^ |   0 Why [0], [1] are valid?
•  » » » » » » 2 years ago, # ^ |   0 Yes, 0 and 1 as two different sequences are valid as they contain only one 'a'.
•  » » » » » » » 2 years ago, # ^ |   0 I failed to relate this with given conditions of the problem please help me to do so.
•  » » » » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 Okay, The problem statement says to find the no. of strictly increasing sequences p1, p2, ..., pk such that: This means value of string at all these indices of sequence must be 'a'. For every i, except the last one in sequence, there must be a 'j' such that and . This means, for any two consecutive elements of sequence, there must be a 'b' in between those two indices of the string. Please let me know if you get it now.
•  » » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 :( not yet.if the given string be aaa, then second condition can never be met by any sequence. Then?
•  » » » » » » » » » 2 years ago, # ^ |   0 Yes, but then all the sequences will be of the same size, to meet both the conditions. So, required sequences are: [0], [1], [2].
•  » » » » » » » » » 2 years ago, # ^ |   0 But this is not mentioned in no where in the problem :(.
•  » » » » » » » » » 2 years ago, # ^ |   0 It's called vacuous truth. https://en.m.wikipedia.org/wiki/Vacuous_truthIf the sequence is of length 1, then there's nothing to check regarding the second condition. So you can consider that it meets the requirement.
•  » » » » » » » » » 2 years ago, # ^ |   0 Thanks djm03178
•  » » » » » » » 2 years ago, # ^ |   0 The two given conditions should be met at a time or else?
•  » » » » » » » » 2 years ago, # ^ |   0 Yes, both the condition should be met at the same time.
•  » » 2 years ago, # ^ |   0 Problem — Count number of subsequences of the string which consists of only a's and every two a's should have at least one 'b' between them in the original string.Solution — Pretty standard approach. Iterate over the string. Maintain a counter. When you get an 'a' increment the counter. When you get a 'b' multiply the counter to answer and set counter to 0. Do not forget to multiply the counter again for trailing a's.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 Please help me. I'm yet to understand the problem statement. 1. which consists of only a's 2. two a's should have at least one 'b' between them in the original string. how to relate this two points with the given condition in problem statement.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Credit to matcoderIt doesn't depend at all if there exists any letter other than a or b in the given string. You can for sure ignore those letters, so the editorial says to erase them. Now, what you have is a string consisting only of a and b's. Also two consecutive b's can be merged as one. So your final string will look something like (a...a)b(a...a)b(a...)...You can now consider this problem as sum of all possible product of subsets of a given set, where each element in the set is the number of a's delimited by b.For example: In the string "aaabaabaaab", set formed will be {3,2,3,0} (0 can be ignored). Now if you have a set {a1,a2,...,aN}, then sum of all possible products of this set is equal to (1+a1)*(1+a2)*...*(1+aN)-1.Proof:Write the required answer as follows:S = Sum of products of subset with (size=1)+(size=2)+...(size=N)S = (a1+a2+...aN)+(a1.a2+a1.a3......+aN-1.aN)+...+(a1.a2.....aN)After factorization,S = (1+a1)(1+a2)...(1+aN)-1For more help check this.
•  » » » » » 2 years ago, # ^ |   0 I read this one before. But, what if the given sequence is "aaa"? No 'b' is present here.
•  » » » » » » 2 years ago, # ^ |   0 For this part append one extra b at the end, and count the total number of a's, the answer is (no of a's +1 ) simply, which is 4 for this test case(aaa).
•  » » » » » » » 2 years ago, # ^ |   0 Why did you append this 'b'? There goes no change in the string length.
•  » » » » » » » » 2 years ago, # ^ |   0 Check this
•  » » » » » » » » » 2 years ago, # ^ |   0 Thanks.
•  » » » » » 2 years ago, # ^ |   0 How did you get — which consists of only a's — this point from the problem's description? this is the thing where I felt short to make up.
•  » » 2 years ago, # ^ |   0 It's a classic dynamic programming problem. The first thing is that you should save the position of 'a' beforehand. Okay, so f[i] is the way to choose the array with the positions of all elements are not greater than the position of ith 'a'.f[i] = f[i-1]; f[i] += 1 (Should take care of the case that the array contains only one 'a'). Now if we choose ith 'a', we should find the previous proper 'a' that has the largest index, which means that between that 'a' and the ith 'a' contains a least on 'b'. This can be done by binary search. The overall complexity of this sol is O(nlogn)
 » 2 years ago, # |   +16 That feeling when you spent nearly 1h to think about 1A but finally realized that the condition that one should have enough gas to pass through a road is useless.
•  » » 2 years ago, # ^ |   +1 Well, you also may consider it and honestly push maximum possible sums in two dfs, one for pushing them to the root and another one for pushing them from the root.
•  » » » 2 years ago, # ^ |   0 Lol. I solved it in this way, though couldn't debug it within time.AC submission
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 But how to ensure that both the paths do not come from the same child?
•  » » » » 2 years ago, # ^ |   0 You should keep maximum and second maximum pathes.
•  » » 2 years ago, # ^ |   +3 What? How?
•  » » 2 years ago, # ^ |   +9 can you please elaborate why that condition is useless?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Because that condition will always get satisfied,when you take two maximum sums among its child.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +11 Because if for any path, at some edge the condition isn't satisfied, then by erasing the path from the starting vertex to that will yield a path with a better result. Thus we only need to find the maximum answer without considering the condition, that is, the optimal answer we find in this way must satisfy the condition.
•  » » » 2 years ago, # ^ |   0 Here's a little more elaborate proof that I wrote.
 » 2 years ago, # |   0 how to solve C without seg tree??
•  » » 2 years ago, # ^ |   +4
•  » » » 2 years ago, # ^ |   0 @Nightshade thanks.
 » 2 years ago, # |   +11 Div2D test 7 anyone please?
•  » » 2 years ago, # ^ |   +3 Check this case: 6 100 100 5 5 5 5 1 3 0 2 3 0 3 4 0 4 5 0 4 6 0 The right answer here is 205.
•  » » » 2 years ago, # ^ |   0 My program got 205, still failing pretest 7?
•  » » » » 2 years ago, # ^ |   0 Me too
 » 2 years ago, # |   +12 early system testing nice ^^
 » 2 years ago, # |   0 For div1E, is it enough to use long double?
•  » » 2 years ago, # ^ |   +5 why you used double dude? i am sure there is no fraction needed
•  » » » 2 years ago, # ^ |   +6 I used convex hull. To determine if a point is to be deleted, I needed a check which could go like till 10^27.Well, I used an int128 library for this check.
 » 2 years ago, # |   +43 C and F were very good problems! (Too bad I didn't solve any of them :(.)
 » 2 years ago, # |   +26 Why are constraints so tight in E? My solution worked 1840ms/2000ms on pretests (I don't know if it will pass, although I'm 100% sure idea is fully correct) and it had 64-bit integer overflow issues. So why did you do so? Am I obliged to prepare very fast CHT beforehand to pass on this problem?
•  » » 2 years ago, # ^ |   +13 Maybe they wanted to block O(nlogn) CHT. But it is poor because there is a sort involved already.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 It seems neither possible nor reasonable in such constraints...
•  » » » » 2 years ago, # ^ |   -33 This is so sad that someone didn't prove it but got acc and you didn't prove it too but you didn't get acc :(((
•  » » » » » 2 years ago, # ^ |   +10 Wtf are you talking about?.. I got AC. My complaint is that solution works in 1918ms which is very close to TL and constraints are very tight without any proper reason.
•  » » » » » » 2 years ago, # ^ |   0 Sorry wrong reply, i wanted to replay another comment.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Maybe they were overly paranoid of n2 dp?You wrote the blog about li chao tree, so I'm surprised you don't have a fast CHT implementation :O
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +8 I used implementation from my article, it didn't turn out to be very fast, haha. Although I used offline version because thought that Li Chao would use memory. Спойлерit wouldn't
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 why overflow? isn't the answer always within long long?Update: sorry my implementation is probably different from yours.
 » 2 years ago, # |   +6 can someone please share their approach to Div2 D ?
•  » » 2 years ago, # ^ |   +3 DFS, where each node returns the best path in its subtree that ends at this node. Do this while maximizing the answer among the sum of best 2 children of each node with each other, i.e sum the paths returned from the best 2 children and check if they're better than your answer, they resemble the best path passing through this node, also try taking the best path alone, or just the gas of the current node.
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 dp on tree.first, make the tree rooted. dp[u] = maximum gasoline that can be starting from u and ending to node that have u as its ancestorfor each node, you can find the maximum of the path passing that node by finding the best two children of that node.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +3 what about the constraint on the minimum amount of gas to cross a path?
•  » » » » 2 years ago, # ^ |   0 nah. doesn't need it. they ask you to maximize the minimum gasoline that can be achieved. not the minimum gasoline spent
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Centroid decomposition — force the centroid to have a depth of 0, and find depths of subtree accordingly (add weights, subtract lengths of edges).Then add in the w[centroid] when considering the answer.Unfortunately, I put for (auto e : arr) ARR.insert(e); in the wrong layer of looping causing it to do nothing at all! :(
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 First notice that an edge and a vertex only comes into the picture along with some other vertex when w(vertex)-w(edge) is positive. In this case it will only increase the gasoline upon reaching some vertex. You need to maximize this.The way to do it is calculate (in) value for the vertex which denotes answer if you start with this vertex and travel down...Also calculate (out) for each vertex which denotes max answer you can get starting from the node and not traversing the children of it.As wewark says keep 2 best children for it to do it in linear time.It is the in-out dp trick. Sad it is for I wasn't able to complete its implementation on time.Below is the link to its video tutorial. https://www.youtube.com/watch?v=Xng1Od_v6Ug
 » 2 years ago, # |   +31 Last week I was mocking .ckodser. for using "ll" no matter what , even as a loop variable. And today I got two wrong answers in the whole contest , both due to the above issue :|. Guess that's the universe slapping in my face ... :O
•  » » 2 years ago, # ^ |   +60 Please give proper respect to the power of #define int long long xD
•  » » » 2 years ago, # ^ |   +5 Amen to that. It takes away a layer of worry.
 » 2 years ago, # |   +78 I don't want to make int128 library only for codeforces(why codeforces working on 32bit????)
 » 2 years ago, # |   0 Can we solve DIV2 D using in-out dp ? for every node , taking max value in inside subtree and max from outside subtree , and now curnodeval+max(inside_value,outside_value) ! we will check this for every node and taking out max of all ! P.S : value in a subtree is sum of values of nodes — sum of values of edges !
 » 2 years ago, # |   +5 Fast judging, pretty good.
 » 2 years ago, # |   +7 And btw, apart from C and F being good problems which I mentioned before, there were a few annoying things. I see that TLE in C was pretty tight (I currently see 1 AC and 2 TLEs on 100/112 tests among my friends) and it seems TL in E pretty strict as well and in E we needed to check whether ab>=cd where these products could be as large as 1027. Why weren't the constraints lower so that it could fit in LL? It took me something like 5-10 minutes to solve this problem and code it apart from doing this check which took me 26 minutes xDDD. CF doesn't have int128 (ノಠ益ಠ)ノ彡┻━┻, long doubles are shaky and all other ways are troublesome and require a lot of care.
•  » » 2 years ago, # ^ |   +8 Wait where did E require that check? I didn't have it and got AC
•  » » » 2 years ago, # ^ |   +8 Depends on implementation, I guess. Check is needed if you reduce CHT to convex hull of points.
•  » » » » 2 years ago, # ^ |   0 I didn't write this code myself but 46872251 uses the CHT and doesn't seem to produce overflows. Source: kactl
•  » » » 2 years ago, # ^ |   0 I just copied not mine code for convex hull (which is great btw) and it had such check. Many people here talk about it (yosupo and comfi) and Radewoosh had this problem as well, so this problem definitely exists and I'm not the only one. Maybe you used some other idea.In my code 46871036 that is line "return (x->b — y->b) * (z->m — y->m) >= (y->b — z->b) * (y->m — x->m);" which is commented and replaced with ugly functions Wrap and Gr
•  » » » » 2 years ago, # ^ |   0 I got AC using long double to do that 10^27 multiplication part (in practice submission). Maybe weak testcases?
•  » » » » » 2 years ago, # ^ |   +8 I am not surprised by fact that it gets AC, but it may be risky. It may be hard to create testcases against this. You can't be sure.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +44 You can use __float128 instead of __int128, as it has enough bits of mantissa precision to store integer numbers of order  ≈ 1033 exactly and exists on the Codeforces.
•  » » 2 years ago, # ^ |   +6 Also I dont see any point in characters in B being 'a', 'b' instead of 'a' to 'z'.
•  » » » 2 years ago, # ^ |   +13 The characters being 'a', 'b' allows for a pretty easy solution that is barely programming. You can consider s and t as binary strings and iterate through their prefixes. While the prefix difference is less than k, you add it to the sum and when it grows larger you add k instead.
•  » » » » 2 years ago, # ^ |   +5 Of course, this solution could be adapted to a larger alphabet, but it only serves to make the implementation difficult.
•  » » » » » 2 years ago, # ^ |   +5 In my solution it would only the matter of replacing 2 with 26 and b with z...
•  » » » » 2 years ago, # ^ |   +2 OMG YOUR CODE IS INGENIOUSBut in your description you missed most important part — why you can don't care about overflows here which is why it is so clean and ingenious.
•  » » » » » 2 years ago, # ^ |   +2 Thanks :DStill managed to fakesolve Div2B, though. Yes, to avoid overflows you just notice that k is not large enough to overflow and that you stop updating the difference after a certain point.
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +8 I don't understand how does your program survives a possible case where both strings are bbbbbb... and bbbbb.. Your variables a and b will for sure overflow because the difference will be 0 at all times. Weird. Maybe weak tests, or maybe I'm missing out on some bit logic.
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +5 Notice that even if the variables overflow, they will do so to the same value.
•  » » » » » » » 2 years ago, # ^ |   0 Couple this with the fact that the variables will only overflow when they are equal, and notice that this means that even cases such as bbbbbbb...ba bbbbbbb...bbwill work due to the difference remaining accurate through overflow.
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Another curiosity is that dues to multiplying by two being equivalent to a left-shift it "overflows" to  - 1 when it multiplies to the sign bit and after that point it will not overflow again if the strings of b-s continues due to 2 * ( - 1) + 1 =  - 1.
 » 2 years ago, # | ← Rev. 2 →   +2 How about Div 2 C?
•  » » 2 years ago, # ^ |   0 it's hard for me to explain but I can give the hint to forget about all characters that are not 'a' and 'b', and count number of adjacent 'a's and store it in vector. Then find formula for it. Check my submission for maybe more info about formula.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 I also used the same approach as yours. Some coders used dp. I didn't get that. I also got AC though
•  » » 2 years ago, # ^ |   +1 It's simple combinatorics.You need to have atleast a 'b' if you consider more than 1 'a's of the sequence. So, what you can do is count 'a's in each segments seperated by a 'b'. Now, suppose for some segment you have x a's. So, you have x+1 choices(select 0, 1, ...x) to select 'a'. Multiply each segment's (x+1) values. Now, you need to subtract 1 as you need to have a subsequence of length atleast 1.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 In Div2 C : In first example test case , we are not taking a sequence [1,4,5].. can you please tell me why ??
•  » » 2 years ago, # ^ |   +4 hey i used a dp approach: consider there are x continuous segments of b's in the string which divide the string in (x+1) parts. Let the no of a's in the (x+1) segments be a1,a2,......a(x+1). Then DP[i]=(a[i]+a[i]*DP[i-1]+DP[i-1])%Mod, DP[i]->no of ways considering first i 'a' segments. Base case: DP[1]=a1 and final answer would be DP[x+1]. Also you would need to check separately when the string would contain no 'a' or no 'b'.
 » 2 years ago, # |   +5 Div1A, statement "Nut can't choose a path, which consists of roads, where he runs out of gasoline" does not affect the answer? Interesting.
•  » » 2 years ago, # ^ |   +11 That's pretty easy to see since if you would have negative amount of gasoline after some prefix, you can just disregard this prefix and get strictly better answer.
 » 2 years ago, # | ← Rev. 3 →   +19 Cheaters 46874750 46876196 ,I suppose that you will not do anything as always MikeMirzayanov ?
 » 2 years ago, # |   +21 You better have developed plagiarism checker. Check some codes and they are almost the same. No doubts most of them are copied from sites like "ideone". For example, two same submissions: https://codeforces.com/contest/1084/submission/46875019https://codeforces.com/contest/1084/submission/46876091
 » 2 years ago, # |   +459 Huh, it took me approximately 5 years and 5 months (since the first c++ code), but this moment is worth it, even if it's just a moment :P
•  » » 2 years ago, # ^ |   +15 Seeing your performance in recent contests I don't think it's going to be just a moment, congratulations!
•  » » » 2 years ago, # ^ |   +82 I sobered up after the holidays XD
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +69 But that won't last long. The sober part, not top1.
•  » » 2 years ago, # ^ |   +43 Yeah I think tourist has a script that registers him automatically to the next contest if he is not in the first place anymore,..
 » 2 years ago, # |   -11
•  » » 2 years ago, # ^ |   -10 weeaboo atrocity
 » 2 years ago, # | ← Rev. 3 →   +199 2 sysfails today :( but at least i got a christmas candy cane :)
 » 2 years ago, # | ← Rev. 2 →   +86 Congratulations Radewoosh.Number 1 on both rating and contribution.
 » 2 years ago, # |   +6 This Code of Problem B: while (sum < s){ sum += n; num[0]--; } I check is case: 1 999999999 1000000000 It's running for 2000ms on my computer,But gets an Accept in system test....
 » 2 years ago, # | ← Rev. 2 →   0 Can anyone provide a proof why this 2B passes??Tried around 10-15 tc but It didn't fail.
•  » » 2 years ago, # ^ |   0 ((i-x)+(i-1)+(x-1))*2. So x cancels out. Similarly when x> i.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +1 For x>i, i cancels out. So this proof is wrong.P.S. — This soln is correct because x=1 is among optimal solutions.
•  » » » » 2 years ago, # ^ |   0 sorry..my bad.
 » 2 years ago, # |   +2 E was solvable in 10-15lines with just sorting+deque without cht.46878899
 » 2 years ago, # |   +24 Thank you, Good contest, Great problems, Nice pretests.
 » 2 years ago, # | ← Rev. 2 →   0 can anyone explain me div 2 c with example
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Ways to choose some subsequence(not necessarily continues) of ‘a’ that between 2 element of this subsequnce there exist a ‘b’
•  » » » 2 years ago, # ^ |   0 can u explain with an example by telling subsequence ?
•  » » » » 2 years ago, # ^ |   0 ps : I am weak in combinatorics :(
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 aaaaggbbaaadddaa The subsequences of length 1 are every a = 9 The subsequences of length 2 are pair of 4 first ‘a’s and 5 other ‘a’s becuase there has to be a ‘b’ between every two ‘a’s that we choose so = 4 * 5 = 20
•  » » » » » 2 years ago, # ^ |   0 Solution: all you have to do is have the number of ways you can do this before the last b then for every a till next b answer is that sum + 1
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 in aaabbaaaabbbaa the answer should be 9+3*4+3*2+4*2?
•  » » » » » » 2 years ago, # ^ |   +3 Its 9 + 3 * 4 + 4 * 2 + 3 * 2 + 3 * 4 * 2
•  » » » » » » » 2 years ago, # ^ |   0 are u sure ?
•  » » » » » » » » 2 years ago, # ^ |   0 Lets count Length of 1 = 9 Length of 2 there could be from first pack of a and second then second and third and first and third Length of 3 is choosing one from each pack
•  » » » » » » » » » 2 years ago, # ^ |   0 Ps. Its like 12:40 am so Im going to sleep bye
•  » » » » » » » » » 2 years ago, # ^ |   0 ohh yes thanx
•  » » » » » » » » » 2 years ago, # ^ |   0 in india its 2:40 a.m xD
•  » » » 2 years ago, # ^ |   0 But Pi and Pi+1 are subsequences, so what does Pi < j < Pi+1 means?
•  » » » » 2 years ago, # ^ |   0 No pi isnt the subsequence its index’s pf subsequence
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +4 Thank you, but why do you think so? I see this: The Nut is a curious guy, so he wants to find the number of strictly increasing sequences p1,p2,…,pk, such that: 1... 2...Please, get me right — I'm not trying to be a jerk, and prove that I'm right and you are wrong — I'm just looking for clues, to understand it right next time.I mean non of n-a-sequences ("aa...aa" n times) is strictly increasing and k is the number of this sequences, not number of "a"s...
•  » » » » » » 2 years ago, # ^ |   0 K is the length of sequence it can be from 1 to n
 » 2 years ago, # |   +5 Div2E states: Recently, the Fair Nut has written k strings of length n, consisting of letters "a" and "b". He calculated c — the number of strings that are prefixes of at least one of the written strings.So he calculates all the possible strings that would be prefixes? Not only those k of length n, that where written?
 » 2 years ago, # |   0 Can someone give me some links where I can learn about convex hull opt? The old ones that are on codeforces blog's does not work.
•  » » 2 years ago, # ^ |   +5 Don't know what happened to PEGWIKI, but I recently learned it from it.And for Li Chao Tree (slope/queries are not in monotonic order) refer to: https://cp-algorithms.com/geometry/convex_hull_trick.htmlIf you want to avoid using std::complex refer to my implementation of Li Chao: https://pastebin.com/fLcs75A9
 » 2 years ago, # | ← Rev. 2 →   0 .
•  » » 2 years ago, # ^ |   0 try using long long instead of all ints. it may answer.
•  » » 2 years ago, # ^ |   0 i'll try
 » 2 years ago, # |   0 Hi I got accepted in problem B(div.2); but there's a test case that is not in your tests, but I will get TLE on it. The test case is this: 1000 10^12-1 10^9 10^9 10^9 .... please add this TC and rejudge
•  » » 2 years ago, # ^ |   0 46902714
 » 2 years ago, # | ← Rev. 2 →   -10 hell o what this is??rate?
 » 2 years ago, # |   0 Guys, what is needed to solve Div2 Problem D? I know DFS but I am not able to understand the approach to be used for this problem. For me, the editorial above is providing no clue/ help. Can someone help me with some explanation on this problem?Thank you.
•  » » 2 years ago, # ^ |   0 Think of it like this : You need to search for a path. So, for each node, you consider its subtree. Now 2 cases : a) You need to find the best one-ending path. That is, find the best path that starts somewhere in the subtree and ends in this particular node. This is the path that can be extended by the ancestor node. So, you need to store it in the DP state. b) You need to find the best possible path in this subtree. Also, it should pass through this particular node. The path in a) is one of them. The others can be found if we combine the best paths from the 2 of the children subtrees. Which we can do by sorting the children DP states.
 » 2 years ago, # |   0 how is Radewoosh pronounced? is it like Raydwoosh or Ra-De-woosh?
•  » » 2 years ago, # ^ |   +10 /ˈraˈdɛ.uʂ/ (the second)
•  » » » 2 years ago, # ^ |   0 thanks xD
 » 6 months ago, # |   +11 .