### chemthan's blog

By chemthan, 3 years ago,

Hello everyone!

I am glad to invite you to Codeforces Round #604, which will take place on Dec/05/2019 17:35 (Moscow time). The round will be rated for both divisions.

Exactly 300 Codeforces rounds passed since my first one (Round 304). I have learned a lot of things here and have much fun in participating in the competitions. Now, I want to contribute to this community by proposing some problems. I hope that you will find something interesting in solving them.

The contest is prepared by me, laoriu, I_love_Hoang_Yen, coordinator isaf27 and CF admin MikeMirzayanov. As usually, we must specially thank to below people who make contest possible:

There will be roughly 6 problems in each division. Scoring will be announced later.

GL & HF! See you on the scoreboard.

UPD 1: Scoring

• D1: 500 1000 1500 (1000+1000) 2250 3000.
• D2: 500 1000 1500 2000 2000 2500.

UPD 2: Thanks for participating! Congratulations to the winners!

Top 5 Div1:

Top 5 Div2:

UPD 3: Sorry for delay, this is editorial.

• +362

 » 3 years ago, # |   +53 roughly means subtasks ??
•  » » 3 years ago, # ^ |   +150 Ask codeforces contest style now. I'm also not fan of it.
•  » » » 3 years ago, # ^ |   +43 Let's talk more about this. You don't have decisive word on this matter? Then who decides it?
•  » » » » 3 years ago, # ^ |   +49 As far as I know it is MikeMirzayanov
•  » » » » » 3 years ago, # ^ |   +190 This is fucked up
•  » » » » » » 3 years ago, # ^ |   +57 Definitely)
•  » » » » » 3 years ago, # ^ |   -29 Seeing as you haven't been a CF problemsetter, I automatically doubt your knowledge is accurate.
•  » » » » » » 3 years ago, # ^ |   +64 Yes, I haven’t been problemsetter but I have tested many rounds recently.
•  » » » » » » » 3 years ago, # ^ |   -42 Fair 'nuff.
 » 3 years ago, # |   +120 Please, don't use the $+$ sign when you don't mean mixed round, it kinda confusees
•  » » 3 years ago, # ^ |   +71 Fixed, I just copy old one, didn't notice that. Thanks.
 » 3 years ago, # |   +196 Most problems are nice, recommend to participate :)
•  » » 3 years ago, # ^ |   +43 That means I won't be able to solve most problems :(
•  » » » 3 years ago, # ^ |   +9 Seems too much motivation for a guy asking others not to demotivate people(for those who dunno the context, see the below comment)
•  » » 3 years ago, # ^ | ← Rev. 2 →   -41 I am really excited then!
•  » » 3 years ago, # ^ |   +11 Thanks, Alexey, you haven't lied! (Не обманул)
 » 3 years ago, # |   +39 I guess this will be an easy contest for me to achieve my goal of becoming violet.
•  » » 3 years ago, # ^ |   +61 Your goal is blue not violet.
•  » » » 3 years ago, # ^ |   -32 Please don't demotivate anyone!
•  » » » » 3 years ago, # ^ |   +30 Just joke, he is my friend :)
•  » » » » » 3 years ago, # ^ |   +18 Am I beautiful?
•  » » » » » » 3 years ago, # ^ |   +13 Congrats for +1xx rating. Your dream comebacks now!
•  » » 3 years ago, # ^ |   0 Congrats your dream becomes true after years :)
 » 3 years ago, # |   0 one more amazing contest :))
•  » » 3 years ago, # ^ |   +13 yeah,i bought some rating from chemthan
 » 3 years ago, # |   0 It must be difficult and contains a lot of math-based problems =))
•  » » 3 years ago, # ^ | ← Rev. 2 →   -18 I hope you won't call it mathforcesyou downvote you gray
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +139 mathforces > hackforces > implementationforces/speedforces > bruteforces > 404ces
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +25 oh, so many force here. Anyway, may the force be with you guys <3
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +19 Mathforces in a nutshell
•  » » » » » 3 years ago, # ^ |   0 Staring in a nutshell.
 » 3 years ago, # |   0 Good luck!!!
 » 3 years ago, # |   +4 what does GL and HF mean?
•  » » 3 years ago, # ^ |   +16 good luck and have fun -_-
•  » » » 3 years ago, # ^ |   +55 Me reading them: what does good luck and have fun mean? good luck and have fun -_-
 » 3 years ago, # | ← Rev. 2 →   +28 The writers did awesome job this time — very interesting problems! I really enjoyed testing this round and I highly recommend to everyone to participate tomorrow.
 » 3 years ago, # |   -8 if i do bad it's automatically because mathforces not because i am bad
 » 3 years ago, # |   +90 every contest...
 » 3 years ago, # |   0 Technically how many problems need to be solved to become purple or orange?
•  » » 3 years ago, # ^ |   +11 At the worst case, you need to solve everything in order to become purple or orange.Usually, you need to consistently be among the first few hundred placed people in div2 in order to get purple.
•  » » » 3 years ago, # ^ |   +14 You got him wrong, he meant "Please add me to your friends and see me in top ten"
•  » » 3 years ago, # ^ |   +41 For purple : A + B + C fast enough, Easy D fast For orange : A + B + C + medium D fast enough, + easy E
•  » » 3 years ago, # ^ |   +7 at least 4
 » 3 years ago, # |   0 Have a good round!
 » 3 years ago, # | ← Rev. 3 →   0 As far as I understand there will be sub-tasks in the round, for me personally this discourages any desire to enjoy the round. Because on CodeForces you can simply not solve a more complex subtask, and at this time people who write a simpler solution will bypass you. Yes, I understand that it may be that the subtask is also solved in a non-trivial way, then such a unit has the right to exist, but as I understand it now, it is necessary to add a subtask rather than an interesting divisionwith all due respect to the author of the round, this most likely refers to the latest trend
•  » » 3 years ago, # ^ |   0 Subtask 1's solutions usually are simplified versions of Subtask 2 ones. Like you replace one advanced data structure from the harder subtask with a simpler data structure and then boom you get subtask 1. So don't mind solving easier subtasks because they probably give you hints on harder subtasks.
•  » » » 3 years ago, # ^ |   -8 You probably didn’t follow my thought, if this is a cool subtask, then of course, but now it’s like a TREND and there is a chance that the subtask is solved simply
 » 3 years ago, # |   -43 why my contribution went from 41 to 31 by itself :/ anyone knows ?
•  » » 3 years ago, # ^ |   +6 Focus on your rating instead of contributions
•  » » » 3 years ago, # ^ |   0 it's not that I care that much about contribution but that's weird
•  » » » » 3 years ago, # ^ |   +26 It's called decay. Older blogs and comments give a smaller part of the contribution.
•  » » 3 years ago, # ^ |   +3 It means your rating goes from 1441 to 1431 -_-
•  » » » 3 years ago, # ^ |   0 And me pupil again
 » 3 years ago, # |   0 Why no registration possible?
 » 3 years ago, # |   0 My mood is not beautiful.
 » 3 years ago, # |   0 are the contests always hard ?
 » 3 years ago, # |   +39 constructforces :v
 » 3 years ago, # |   0 .
•  » » 3 years ago, # ^ |   0 Neir:Automata <3
 » 3 years ago, # |   0 How to solve div.1 E ?
•  » » 3 years ago, # ^ |   +18 Minimise sum of squared outdegrees, I guess.Basically, any triple of vertices is either a cycle or there's one vertex with edges into the remaining two (while neither of them has edges to the other two, obviously). The number of triples with cycles is the total number of triples minus the number of such pairs of edges, which is $N(N-1)(N-2)/6 - \sum outdeg_i(outdeg_i-1)/2$.
 » 3 years ago, # |   +18 Nice D2 1000
 » 3 years ago, # |   +1 My summary of the contest: Phew.
 » 3 years ago, # | ← Rev. 2 →   -74 I don't want to be rude or impolite or intolerant or whatever, but the round is f*** up!
 » 3 years ago, # |   0 For me contest was hard, but problems were interesting. How to solve div2D(div1B)?
•  » » 3 years ago, # ^ |   +32 Notice that because of $|A_i - A_{i-1}| = 1$ condition, consecutive numbers can't have the same parity and hence $|cnt(even) - cnt(odd)| \le 1$Next step is to handle 2 more cases $\text{assuming 0-indexing}$:N is odd: if $cnt(even) - cnt(odd) = 1$, fill even positions with 0s then 2s and odd positions with 1s then 3s and vice versa when $cnt(odd) - cnt(even) = 1$N is even: try starting with both evens and odds Check if the array satisfies the conditions and print if it does
•  » » » 3 years ago, # ^ |   0 Thanks!It helped!
•  » » 3 years ago, # ^ |   0 Actually it can be solved in greedy approach.(in case nobody mentioned it before) the answer can start with either the smallest number or the second smallest number, try both of them. When filling a new digit $a_{i}$ , it could be either $a_{i-1}-1$ or $a_{i-1}+1$, try $a_{i-1}-1$ first, if you don't have more $a_{i-1}-1$ then try $a_{i-1}+1$, if you dont have it neither, then stop.Hopefully you can understand it cuz my english is not good enough.
•  » » » 3 years ago, # ^ |   0 Thanks!
•  » » 3 years ago, # ^ |   +2 1.Take a deque. 2.insert 0 if a>0 or insert 1 if b>0 or insert 2 or 3 using the previous condition for each number. 3.Now you have a head and a tail in the deque. 4.Then you continue pushing the remaining element.if its absolute difference with the tail element is one then push the element in the back of the deque. If it cannot be pushed to the back check whether it can be pushed in front. 5.if you have a+b+c+d>0 and you dont have any opportunity to push a new element you can break and print no.Otherwise the answer will be Yes and print the deque.
 » 3 years ago, # |   +13 How to solve probability question?
•  » » 3 years ago, # ^ |   +2 Expected days ( x )= sum of p[i]*number_of_days_passedx= (1-p[0])*(1+x) + p[0]*(1-p[1])*(2+x) + .... + p[0]*..p[n-2]*(1-p[n-1])*(n+x) + p[0]*p[1]*..*p[n-1]*nsolve the equation for x under modulo, p[i] being the probability ( after dividing by 100 )
 » 3 years ago, # |   +75
•  » » 3 years ago, # ^ |   +35 The meme of your account photo is so compatible with the picture.
 » 3 years ago, # |   +58 EXACTLY THE SAME PROBLEM WITH E Sadly, I didn't know before contest ended..
•  » » 3 years ago, # ^ |   +16 This problem too had almost the same idea. Too sad, I couldn't participate today :(
•  » » 3 years ago, # ^ |   +61 much much earlier one in CN Winter Camp 2007.
•  » » » 3 years ago, # ^ |   0 Congrats on a #1 finish :D
•  » » » » 3 years ago, # ^ |   +8 Try to sound chinese
•  » » » 3 years ago, # ^ |   +22 wxhtxdytxdy
 » 3 years ago, # |   +3 So, what is a "normal" way to implement B? (I did something very horrible: assume the string is of the form $(2)^e (3\, 2)^f (3\, 2\, 1)^g (2\, 1)^h (2\, 1\, 0)^i (1\, 0)^j (1)^k$; try values of $e, k, i$ and deduce the rest from those. Then handle special annoying cases.)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +61 I implemented it by trying all possible values of first number. Then, if the last number is 2, always prioritize going to 3 over 1 and if the last number is 1, always prioritize going to 0 over 2.
•  » » » 3 years ago, # ^ |   0 I am happy I did the same way! :D
•  » » » » 3 years ago, # ^ |   +3 Came out with the idea. Just slight late and couldn't implement.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 can you please give proof of correctness of your solution? why does prioritizing works here? I got accepted by your method but still don't know why it's correct :(
•  » » » » 3 years ago, # ^ |   0 Divide numbers into 2 groups (0, 2) and (1, 3). We can see that all numbers in each group will be put at either odd or even positions only. So we only have 4 possible adjacent pairs: (0, 1), (0, 3), (2, 1) and (2, 3). The only invalid pair here is (0, 3) so our strategy would be keep them as far as possible. Hence, we can arrange group (0, 2) like this: 0 0 ... 0 2 2 ... 2 (put all 0s to the left). For (1, 3) it is: 1 1 ... 1 3 3 ... 3 (put all 3s to the right). The first number can be either 0 or 1 and you can fill the following one using above strategy. Then just check if it is a valid sequence.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +32 My solution is like:Try to see what the finally path look like: First it will be ...->odd->even->odd->..., i.e. alternating parity. Also 0 and 3 can not be adjacent. So just put 0 as early as possible and 3 as late as possible, and fill in the rest of the positions.Upd: There are actually two cases. If you have a sequence starting with an odd number, you should put 3 as early as possible and 0 as late as possible; otherwise, it is just what I mentioned above. Sorry for the confusion.
•  » » » 3 years ago, # ^ |   0 Do you accomodate for strings like 101012121232323212101 ? [3,8,7,3]
•  » » » » 3 years ago, # ^ |   +9 You don't need to put these 3-s in the middle: you can do something like 101010121212121232323.
•  » » » » » 3 years ago, # ^ |   -8 I tried this, did not work.
•  » » » » » » 3 years ago, # ^ |   0 What do you mean, didn't work? You don't think the string above is a 3 8 7 3? I think your solution probably just has an implementation bug somewhere or you're missing some cases. It's definitely not necessary to put the 3-s in the middle like that in any case.
•  » » 3 years ago, # ^ |   +33 I implemented it in a very simple way:You must match 0 with 1, and so you do until you run out of 0 (otherwise it's impossible since you can't match the extra 0)Now you have "a first block" that looks like [0101...0]Do the same but for 3 and 2, you have "a second block" that looks like [323...3]Now you must merge both blocks with "a third block" that looks like [121...2]If you have an extra 1, you can plug it in into the first block. Same for an extra 2 but to the second blockSo the solution ends up being[extra 1][first block][third block][second block][extra 2]
•  » » » 3 years ago, # ^ |   0 What if you have 2 extra 1s?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 If you have more than a single extra 1, that means you couldn't match it neither with a 0 (otherwise this extra 1 wouldn't exist, as it would have been plugged into the first block) nor with a 2 (otherwise it would have been plugged into the third block). So the answer is noSame if you have more than a single extra 2
•  » » » » » 3 years ago, # ^ |   0 Won't it fail for 101012121232323212101 ? [3,8,7,3]
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +6 My solution will work as follows[first block] := [01010][second block] := [32323][third block] := [1212121212]extra 1s = 1extra 2s = 0So the answer is:[1][01010][1212121212][32323]Without brackets:101010121212121232323
•  » » » 3 years ago, # ^ |   0 it is not simple way for the second problem of the contest
•  » » » » 3 years ago, # ^ |   0 You can implement it in a few lines
•  » » 3 years ago, # ^ | ← Rev. 2 →   +23 I have very strange solution. Let's denote how many times x goes exactly before y as c(x, y). And assume path will go from s to t. So we have 4 equations: c(1, 0) — c(0, 1) = (t == 0) — (s == 0) c(0, 1) + c(2, 1) — c(1, 0) — c(1, 2) = (t == 1) — (s == 1) same for 2 & 3... and another 4: c(1, 0) + (s == 0) = a c(0, 1) + c(2, 1) + (s == 1) = b c(1, 2) + c(3, 2) + (s == 2) = c c(2, 3) + c(4, 3) + (s == 3) = dFor fixed s and t it is system of linear equations, take any 6 of them, solve with Gaussian elimination. So we know how many times we have each pair of elements adjacent, let's make c(x, y) edges from x to y in new graph. now we need Euler path in this graph if it exists. Check it with well known dfs in 10^5.Now just try all 4 x 4 pairs for s and tSay no to greedy solutions)
•  » » 3 years ago, # ^ |   +8 I wonder if this solution is intended or not, I just went through all permutations of [0,1,2,3] and tried to find the answer if we use numbers in that order: https://codeforces.com/contest/1265/submission/66375662
 » 3 years ago, # |   0 Is there any efficient way I can increase my implementation ability? I got stucked in implementing A, C resulting to be unable to solve D(still implementation difficulty). I get stucked when I get multiple conditions and specially corner cases.
•  » » 3 years ago, # ^ |   +4 It's alright to get stuck,you'll now solve the problems you were stuck on and won't get stuck in the future. :D
•  » » 3 years ago, # ^ |   -8 How to solve B?
•  » » 3 years ago, # ^ |   +1 Implementation is probably the easiest skill to improve because it's literally just practice. You can look at other people's solutions to see if there is a cleaner high-level idea that you are missing (and a lot of these carry over to other implementation problems as well), but in general just doing a lot of implementation problems makes you much better at it.
•  » » 3 years ago, # ^ |   +1 For A the key observation is that you can substitute all ? by any of the three chars what is fitting there, ie simply check the previous and the next index.C and D simply anoying. There is surely some greedy, but that kind of problem is just search for corner cases.
•  » » » 3 years ago, # ^ |   0 It's not common, but I actually think the nice insight in Div2D is one that lets you eliminate the corner cases (it's mentioned above, where you just try all possible starting values and force an order after that).
•  » » » 3 years ago, # ^ |   0 C was simple. Take gold less and it's done. This idea needed a 30 minutes of coding. Can you imagine? I am dealing with the problem of implementing a solution quicker
•  » » » » 3 years ago, # ^ |   0 I tried. Giving as less gold as possible. Then as less silber as possible. Then as much bronze as possible.Sound fairly simple greedy, did not work for some reason.
•  » » » » » 3 years ago, # ^ |   0 This solution works, you must have a bug. You can check my submission if you have any problems debuging yours. 66332463
•  » » » 3 years ago, # ^ |   0 66352986 check this out for D, no corner cases at all.
 » 3 years ago, # |   -63 Was not able to find the interesing problems in this contest, div2. A, B was more or less simple. C, D anoying, I assume there is some greedy, but thats trial and error programming, at least for me. How can one find a proved solution ?E is boring math and F way out of sight.
•  » » 3 years ago, # ^ |   +3 Wow!
•  » » 3 years ago, # ^ |   +34 yeah no, C D are not trial and error programming. Obvious greedy is obvious. Ain't the contest's fault if you don't know how to do greedy.
•  » » 3 years ago, # ^ |   0 Div. 2 A and B were always intended as obstacles for starters. They were not intended to be complex for people who have already been blue. C and D were greedy, yes, but you can easily prove their solutions. It was not even remotely hard to prove a greedy solution for C/D. Obvious greedy is obvious. If you don't like trial-and-error style of programming, then C can be solved with basic DSU, and, well, the math behind D can be easily proven with some analysis. I'm sure that such solutions wouldn't be too heavy in the implementation, and still satisfy what you called as "interesting". Okay, let's admit that E is too easy for an average div.2 E — but the math behind it was a nice practice for everybody, and encourages blue/cyan competitors to try out probabilities problem. F was hard, yes, but it was intended as a challenge for the best (among blues, at least). Most div.2 F is often 2100+ — what did you expected? E 1500, F 1600, and you need to solve all 6 problems to be in top 1000?Overall, the round does have some problems — E being a bit too easy, D's tricky 16th test case — but it was nowhere abysmal as you described. It's not the contest's fault when you sucks in the contest, and the contest wouldn't care either.
 » 3 years ago, # |   +43 D1 was a nice subtask this time. The depth can be calculated as follows: Pick some position, count number of ( on the left side, count number of ) on the right side, answer minimum of those. But there could be multiple positions giving the maximum depth. The observation we need is that there always exists a unique position where the count on the left side equals the count on the right side, and further at that position the count is always maximal.To show this, find any position where the minimum is maximal, and move the position left (if there are more ('s) or right (if there are more )'s) until there is an equal amount of both. At that position both counts are equal, and the position where both counts are equal is unique (moving left either adds 1 to the number of )'s or decrements 1 from the number of ('s, and similarly for right.So we can calculate for every position, for every count, the number of ways to have exactly that many ('s on the left side and exactly that many )'s on the right side, then multiply this by the count and add it to the answer. This is easy to do in $\mathcal{O}(n^{2})$, but I did not figure out how it could be done in $\mathcal{O}(n)$ for the second subtask.
•  » » 3 years ago, # ^ |   -30 It was a useful subtask, but still not very interesting. It's just some DP(number of ways such that the i-th character is the d-th opening bracket) and DP(number of ways such that we have at least d closing brackets among the last i characters).At least D2 offers "hmm, how do I solve this?" rather than "yeah I'll obviously do this".
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +16 A unique maximal position existing wasn't immediately obvious for me, that took longer to figure out than writing the implementation, so for at least the subtask was interesting.
•  » » » » 3 years ago, # ^ |   +42 When the depth is at least $D$, we need $D$ opening brackets before $D$ closing ones, so for a fixed sequence, we just want to find the $D$-th opening bracket and check if there are at least $D$ closing ones after it. That was my way of thinking.
 » 3 years ago, # | ← Rev. 2 →   +44 Is anything random in Div1.E intended to fail?
•  » » 3 years ago, # ^ |   0 For me it looks that they are trying to hack all greedy solutions now :) It would be great if someone knows counter-testcase for greedy, just to stip waiting :D
•  » » 3 years ago, # ^ |   +10 Well, some heuristic solutions passed and some failed, classic
 » 3 years ago, # |   0 Okay contest. div2D was quite interesting.
•  » » 3 years ago, # ^ |   +1 Irritating for me. Corner after corner
 » 3 years ago, # |   0 How to solve Div2 B? Really stucked with it.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +4 You iterate $\mathrm{i}$ from $\mathrm{1}$ to $\mathrm{n}$, update $\mathrm{left}$ (leftmost position of all previous iterations) and $\mathrm{right}$ (rightmost position of all previous iterations) with position of $\mathrm{i}$, and $\mathrm{i}$ is beautiful if $\mathrm{right-left+1=i}$
•  » » » 3 years ago, # ^ |   +3 That is a really beautiful solution. Thanks for it. :) My solution during contest was much messier. I would just like to explain the intuition that I derived out of your solution: Since, we know that if there is a range possible for some $i$, it must only contain all elements $\le i$. So, at every step, we ensure that we are maintaining the smallest range $[l, r]$ s.t. all elements $\le i$ are contained in it, and just check to see whether it contains some other elements or not. If it does, the answer is $0$, otherwise $1$.
•  » » 3 years ago, # ^ |   0 Make an array of pairs of (number,index) and sort this array by number. Now for each prefix (1-i) of this array, we only need to check if all indices of this prefix form a subarray in the original array. If they do, then answer for i is 1,else 0.To check that, let S be the sum of the indices of prefix (1-i). And let M be minimum index in all these indices. Then (S- M*i) should be the sum of first i whole numbers (i.e sum(0-(i-1)) =(i*(i-1))/2.
•  » » 3 years ago, # ^ |   +3 Keep index of all numbers in map, now start with i=1 to i=m use a set and result string initially which is initially emptyfor each m insert m in set, now take the first and last value from set, if this is equal to size of set then append '1' else append '0' to the result string
 » 3 years ago, # |   -14 division 2 be like everybody do 3 questions and forget about the contest.
•  » » 3 years ago, # ^ |   0 Why ? div2D solved by 700 participants — it's normal!
•  » » 3 years ago, # ^ |   0 yes , you are right .
 » 3 years ago, # |   +8 Can Div. 1C/2E be solved by segment tree and merging its left and right equation?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +31 Sure. When you know the formula for expected value, the rest is fairly standard "compute function over interval". It also works for a more general version of this problem where $P_i$ can be updated too.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +8 Oh wait, my wip solution actually works when the Pi can be updated too. I was overthinking on how to merge 2 intervals, where you have to store 2 value for each end. Turns out you just need a function to compute each interval value and can lazily update the checkpoint. Guess I'm still far away from being a master :<
•  » » 3 years ago, # ^ |   0 Probably, but that's a bit overkill for the problem. You really just need prefix computations of certain sums (in particular the product of the first i probabilities and then prefix sums on the product of the first i probabilities). Then you can answer any segment in log time by calculating the numerator and denominator independently and using modular inverse.
 » 3 years ago, # |   +8 It was a very cool contest, especially considering that Div1B has so weak pretests, that solution from contestant, that didn't understand the statement, pass all of them.
•  » » 3 years ago, # ^ |   0 whaaaat?There were sooo many WA16 and several WA6 as well, and until I checked all cases thoroughly I got WA...
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +7 I thought that all abs(s[i]-s[i+1]) should be equal to each other, not equal to 1. And my solution passed all pretests. There are no tests like 0 2 0 0 or 2 0 2 0.
 » 3 years ago, # |   -13 I participated after 1 month and totally disappointed that....i couldn't do what was my minimum expectation -_-
•  » » 3 years ago, # ^ |   0 You will improve don't worry :)
 » 3 years ago, # |   -6 Thank you for perfectly balanced round! I will wait your next rounds :)
 » 3 years ago, # |   +10 How to solve div.1 C?I can only solve its easier version div.2 E with a simple probability dp...
•  » » 3 years ago, # ^ |   +5 I couldn't finish impl it on time.but this should work, if you can get E(i,j)=from ckpoint i to ckpoint j. in O(1). since each update just change adj-ckpoint.you need to preprocess prefix sum of $P_i= p_1*..*p_i$, $S_i = \sum P_i$, $T_i = \sum P_i*i$since $E(i,j) = j-i + [dT_{i-1,j-1} - (i-1)*dS_{i-1,j-1} - (dT_{i,j} - i*dS_{i,j})] / P_j$.
•  » » » 3 years ago, # ^ |   +10 Thanks very much, I get your main idea.But I failed to understand your formula.According to yogeshk972 's comment, $E$ equals expected days from $1$ to $n+1$. $E=(1-p_1)(E+1)+p_1(1-p_2)(E+2)+p_1p_2(1-p_3)(E+3)+ \dots + n\prod_{i=1}^n p_i \\ (\prod_{i=1}^n p_i) E=1+p_1+p_1p_2+\dots+\prod_{i=1}^{n-1}p_i \\ E=\sum_{i=1}^n \prod_{j=i}^n 1/p_j$Prework the suffix product of $p$, and the suffix sum of $\prod_{j=i}^n 1/p_j$, since we can get $E(i,j)$ in $O(1)$.
•  » » » » 3 years ago, # ^ |   0 damn it, you're right. The formula could much simpler as yours. perhaps that's why I didn't finish impl it on time:(.my formula is just directly calc all positive, and all negative. yes you can get much simpler form $(i+1)*Pi - iP_i=P_i$.
•  » » 3 years ago, # ^ |   0 Can you explain the simple DP approach?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +21 $E(X) = (E(X-1) + 1) * \frac{1}{P_{i}}$$E(0) = 0Where E(X) is the expected amount of days to get a "you're beautiful" from the X'th mirror. Intuition — To transition reach the i'th mirror, we first need to reach mirror i-1, which takes E(i-1) days. After we get a yes from mirror i-1, we need one extra day (hence + 1) to get an answer from mirror i. Now we have a "cycle" of (E(i-1) + 1) days for the amount of days we expect until we have reached the i'th mirror and gotten an answer from it. Then it will take \frac{1}{P_{i}} (geometric distribution) passes through the cycle until we expect the the i'th mirror to return "you're beautiful".Final answer is E(N) •  » » » » 3 years ago, # ^ | 0 i have seen most of the solution involve this power(p[1], mod — 2, mod) why are we raising it by mod-2 •  » » » » » 3 years ago, # ^ | 0 1 / p[i] means the inverse of probability p[i]. As we have to get the result modulo something, we can't simply just divide it with p[i], we have to take the modular inverse of p[i]. •  » » » » » 3 years ago, # ^ | ← Rev. 2 → +8 Because the modulus is prime, a^{m-2} \equiv a^{-1} \pmod m via Fermat's little theorem (which is a special case of Euler's theorem). It's a popular way of obtaining the modular multiplicative inverse a^{-1} where a \cdot a^{-1} \equiv 1 \pmod m, which is the easiest way to "divide" numbers in a modulo field.  » 3 years ago, # | 0 Expected number is too complex in wikipedia.Can anyone explain it more simple? •  » » 3 years ago, # ^ | ← Rev. 2 → +10 Expected number of x is summation of all possible values of x, each multiplied by its probability of occurrence. If x is a continuous (not discrete) variable the summation is converted to integration. •  » » 3 years ago, # ^ | +10 Check the blogs of Errichto. :)  » 3 years ago, # | 0 How to solve Div2 C? Really stucked with it. •  » » 3 years ago, # ^ | +1 take minimum gold, take silver until it"s greater than gold rest till n/2 is bronze. Also you can't take the contestants with minimum solve and can't divide contestant with equal solve between silver and bronze or bronze and no prize. •  » » » 3 years ago, # ^ | 0 Thanks, It really helps me a lot! •  » » » 3 years ago, # ^ | 0 I used same idea. But it gives me WA.Can you please tell me what wrong in my approach?Here is my Code •  » » » » 3 years ago, # ^ | 0 I think problem is with your global array a. You are not initializing it to zero for each test case. •  » » » » » 3 years ago, # ^ | 0 Thanks.  » 3 years ago, # | -21 I just want to say problem C has too long of a statement. So, statementforces?  » 3 years ago, # | +6 Well, that was an interesting round. Thanks to the creators!  » 3 years ago, # | +5 My dreams of reaching blue seems impossible now •  » » 3 years ago, # ^ | +8 Be calm see my profile I have struggled more than you but still I have not become an expert this site is more challenging. •  » » 3 years ago, # ^ | 0 Keep calm. And solve problem after the contest.  » 3 years ago, # | +17 Did anyone else solve div2B using DSU, where the adjacent values in permutation to be considered an edge, and we join them one by one while processing for each i, and the number being beautiful when the number of roots in dsu being 1? •  » » 3 years ago, # ^ | 0 Used 2 pointer technique •  » » 3 years ago, # ^ | 0 No need for that though  » 3 years ago, # | ← Rev. 2 → +9 https://hastebin.com/vezonuxuve.csSo I'm relatively new to this, and I was pretty stumped on Problem A, Div 2 (got a TLE). https://codeforces.com/contest/1265/problem/ALooked over a correct solution and noticed that instead of creating and adding to a string like I did, they first converted the inputted string to a list, and went through and modified the list.Is working with a list, and not creating any new variables like this, really that much faster? Is it something else? Or is there a roadblock in my code that I haven't mentioned yet? Would appreciate any help •  » » 3 years ago, # ^ | 0 From my point of view using a list does not give advantage in this problem. One hast to check the chars at position +1 and -1, both is a[i+-1], using a list or a string.  » 3 years ago, # | 0 DIV2 A DFS FTW! •  » » 3 years ago, # ^ | 0 Why do you need it? You can look at the front and back for questions and find the answer from this. •  » » » 3 years ago, # ^ | 0 I'm just too lazy to think of a greedy solution.  » 3 years ago, # | +73 needless to say, pretests are shit •  » » 3 years ago, # ^ | +38 So my B failed because of this dumb typo:if (a + b == b + d)I decided to look at the pretests and found that out of 17 pretests, 11 have no answer and the remaining 6 have an odd total numbers. Don't know if it's intentional or not ¯\_(ツ)_/¯ •  » » » 3 years ago, # ^ | +22 No, it was not intended. It's just you are unlucky.  » 3 years ago, # | 0 In problem B, what thinking or method has to be applied ?  » 3 years ago, # | ← Rev. 2 → -19 For Div2 ProblemD: It was said that "The only input line contains four non-negative integers a, b, c and d (0 •  » » 3 years ago, # ^ | +13 I think 0 is non-negative. •  » » » 3 years ago, # ^ | 0 Oh. My bad! Sorry!  » 3 years ago, # | +3 Why the answer for DIV2, D for 10th pretest (1 3 40001 40000) is NO? Why can't we do this like: 1 0 1 2 3 ... 3 2? •  » » 3 years ago, # ^ | +3 it would be 1 zero and 2 ones but test case needs 1 zero and 3 ones. •  » » » 3 years ago, # ^ | 0 OK, so why it couldn't be with one more one at the end of answer, I mean: 1 0 1 2 3 ... 3 2 1, now I think it would be correct...? •  » » » » 3 years ago, # ^ | 0 This test case will have an answer according to question. That can be either 1 0 1 2 1 2 3 2 3 .. or 1 0 1 2 3 .. 3 2 1. •  » » » » » 3 years ago, # ^ | 0 So why the answer is "NO"? •  » » » » » » 3 years ago, # ^ | +6 The answer is "YES" but your output is "NO" •  » » 3 years ago, # ^ | ← Rev. 2 → +1 NO is your output. Correct answer is what you say. Read the detail of your submission carefully. •  » » 3 years ago, # ^ | ← Rev. 4 → 0 Answer would be YES 1 0 1 2 1 then (23) 40,000 times •  » » » 3 years ago, # ^ | +3 Read the detail of your submission carefully. •  » » » » 3 years ago, # ^ | +11 OKK, right, so sorry.  » 3 years ago, # | +11 so sad. D has weak pretest :((  » 3 years ago, # | 0 Can someone please explain how do we get 112 as the answer in E second example? I was getting 100. Probably applying a wrong concept here!  » 3 years ago, # | -21 66326596 Someone stole my code from ideone.com. It wasn't intentional but I used ideone.com with the default settings (public access to your code), Here is the link: https://ideone.com/pwlcr1 but I used the same link to write the answer for problem B in the Div 2 contest: 66336397 and as you can see it is the same as in the link.UselessDev  » 3 years ago, # | 0 how can I increase my ability to solve B C D type problem easily??just improving my skill in data structure.... is it enough ?? •  » » 3 years ago, # ^ | 0 Lmao, good one •  » » 3 years ago, # ^ | +10 This old comment might help: link •  » » 3 years ago, # ^ | ← Rev. 2 → 0 Nop , for solve those problems on CF is most important the experience , and always do upsolving reading the editorial and read betters codes of others contestants.  » 3 years ago, # | ← Rev. 2 → +15 Finally I have a nice rating. tfw not nice anymore •  » » 3 years ago, # ^ | +5 Nice •  » » 3 years ago, # ^ | +10 Nice  » 3 years ago, # | -6 This is my 3rd contest on codeforces, and I am confused about the ratings change. In my first contest I was able to solve A only , my rating was 1370. In 2nd contest I was not able to solve any, my rating was 1255. In this contest I was able to solve A,B,C and my rating is 1314 ! lesser than the 1st contest even after solving more problems ?How is this possible ? •  » » 3 years ago, # ^ | +7 Rating is determined based on the rest of the competition. Let me give a fake example. 9000 people participate in one contest and 8000 of them are able to get >1 problem right. Let's suppose there is another contest with equally good people and the same number of people in which only 3000 of them get >1 problem. Then, if you solve a problem in the first contest, it is not as impressive as if you solve a problem in the second contest. So your rating does that; it is based not exclusively on how many problems you solved but how many you solved relative to how many other people solved. For more detailed information, see here. •  » » 3 years ago, # ^ | +6 Here's an outline of how the rating system works. Contest rating != performance in only the last contest. It's a cumulative measure. It increases if you perform better than the expected performance (which depends on your rating before the contest began), and decreases (or stays constant) otherwise. Also, before the first contest, your base rating is taken as 1500, so think of the first contest as a change in rating from 1500 to 1370. •  » » » 3 years ago, # ^ | ← Rev. 3 → -12 Thanks bighead, you live here free of a rent for whole year — Jin yang  » 3 years ago, # | -11 I think problem c on div1 is be more beutiful if have one more query that change the Possibility •  » » 3 years ago, # ^ | +31 Nah it's pointless a bit more codin'. Doesn't make it any more "beautiful"  » 3 years ago, # | ← Rev. 4 → +22 For anyone interested to know why the expected number of trials in mirror j before going to mirror (j+1) is \dfrac{1}{p_j} (0 •  » » 3 years ago, # ^ | 0 Can you please explain how to build the solution to Div2 E using this ? •  » » » 3 years ago, # ^ | ← Rev. 2 → 0 I don't understand this , but you can see XLor comment https://codeforces.com/blog/entry/71916?#comment-562459 you can easily understand it. •  » » » » 3 years ago, # ^ | ← Rev. 2 → 0 This is essentially needed to solve Div1C. But you can solve Div2E in an easier way. •  » » » 3 years ago, # ^ | ← Rev. 2 → +3 90qvBI was just proving why the expected number of trials in mirror j is \dfrac{1}{p_j}.This is how I solved Div2E:Let E(i) be the expected number of days we have to spend before going to mirror i+1 if we started at mirror i. If we calculated E(i) for all i from 1 to N, the answer is just \sum_{i=1}^N E(i). To calculate E(i):For i=1: E(1) = \dfrac{1}{p_1} (because every trial at this mirror corresponds to one day).For i>1: E(i) = (\dfrac{1}{p_i}-1)*\sum_{j=1}^{i-1} E(j) + \dfrac{1}{p_i} (because every trial from the first \dfrac{1}{p_i}-1 trials corresponds to going back to mirror 1, and we have to spend \dfrac{1}{p_i} trials (days) in total at mirror i itself. •  » » » » 3 years ago, # ^ | 0 Thanks a lot for the solution, never used Expectations this way. I solved it sometime back using the idea mentioned in this comment which appears slightly more intuitive. You may wish to look at it, in case haven't. •  » » » » » 3 years ago, # ^ | 0 Thank you, your solution is even simpler. •  » » » » 3 years ago, # ^ | 0 I don't understand "expected number of trials in mirror j is \dfrac{1}{p_j}".Won't that be the case if with probability 1-p_j you started back at j. But here, we are going back to 1 right?I have read both your comments again and again, am I missing something obvious? •  » » » » » 3 years ago, # ^ | ← Rev. 4 → 0 I feel like I finally understand. I am too used to thinking about it using the Law of Total Expectation, so sharing it for others who might be stuck too. So, we haveE(j) = E(j|B)*P(B) + E(j|not B) * P(not B)$$E(j) = (1)*(p_j) + (E(j)+1)*(1-p_j)$Here, B is the event that the $j$th mirror tells you that you are beautiful, and $E(j)$ denotes expected number of days until we reach mirror $j$.Solving, gives the same thing, $E(j) = \dfrac{1}{p_j}$.
•  » » » » » 3 years ago, # ^ |   0 Yes, this is the case if we started back at $j$. And since we actually start at $1$, each of the $1^{st}$ ($\dfrac{1}{p_j}-1$) trials is followed by going back to $1$, and hence we add $\sum_{k=1}^{j-1} E(k)$ ($\dfrac{1}{p_j}-1$) times.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I meant that, we cannot calculate time spent at $j$ this way.This first line you used, $E=\sum_{i=0}^{\infty} (i+1)*p*(1-p)^i$I still don't understand how the calculations are working out.This, according to me, assumes that with probability $1-p$ we start again at $j$.Also, in my own calculation above, when I use "expected number of days until we reach mirror $j$" it makes sense, but that means it's wrong, because then the answer would simply be $\dfrac{1}{p_n}$.
•  » » » » » » » 3 years ago, # ^ |   0 Yes this assumes that we will start again at the same mirror, as if this mirror was a checkpoint.
•  » » 3 years ago, # ^ | ← Rev. 4 →   +24 $E = 1 + (1 - p) \cdot E$ (We do one step and with probability (1 — p) we start over)You could start from this as well =)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thank you. I didn't express expected values before using this way, but it seems really great.
•  » » 3 years ago, # ^ |   0 Generally, your explanation is the same as the expected value of Geometric distribution?
•  » » » 3 years ago, # ^ |   0 Yes it looks similar. Some example (as mentioned in the Wikipedia page) would be the expected number of dice throws until the number $1$ appears (here $p=\dfrac{1}{6}$, so the expected value is $6$).
 » 3 years ago, # | ← Rev. 2 →   +41 For Div1 E，it can be showed that this problem is quite similar to a problem in Chinese Contest WinterCamp 2007，the code can be easily searched by Baidu or Google. for example,the following blog posted the code in 2018 https://www.cnblogs.com/zhoushuyu/p/9146420.html According to the rule about the Third Party code，i think i should not be unrated. MikeMirzayanov Please investigate this matter，Greatly thanks
•  » » 3 years ago, # ^ |   +6 I have the same problem, and I use the code from https://www.luogu.com.cn/problemnew/solution/P4249.
•  » » 3 years ago, # ^ |   +6 Actually I used the first solution code at https://www.luogu.com.cn/problemnew/solution/P4249, which was published in 2018. I don't think this breaks the third-party code rule according to http://codeforces.com/blog/entry/8790.
•  » » » 3 years ago, # ^ |   +8 Hope the rating can come back..lol
 » 3 years ago, # |   +24 Crazy match！ I only solved A in the first hour. Thanks to E, It's very similar to bzoj2597 I solved. It gived me hope.
 » 3 years ago, # |   +36 Beautiful Sequence gives me a beautiful FST :(
 » 3 years ago, # | ← Rev. 3 →   +42 For div1 C, by mistake I output n lines. And perfectly, The pretests satisfy n=q, so I get a perfect FST......
•  » » 3 years ago, # ^ |   +8 What does FST means, i'm curious :P
•  » » » 3 years ago, # ^ |   +1 Failed System Test.
 » 3 years ago, # |   0 Nice problems <3 BUT too many corner cases. BTW, Thanks for such a awesome contest <3
 » 3 years ago, # | ← Rev. 2 →   +3 This is my solution for Div1 D1:Let's first think about how to calculate the depth for a definite bracket sequence.If the first element is ) or the last element is (, then it's useless and we can reduce the length of the sequence by one or two.Otherwise, the first element is ( and the last element is ), so they form a match and we can increase the depth by one.So we can define $\operatorname{solve}(x, y)$ for calculating the sum depth of interval $s[x\ldots y]$:For the situation that $x\geq y$, the result is obviously $0$.If $s_x$ is ) or $s_y$ is (, then $\operatorname{solve}(x, y)$ equals to $\operatorname{solve}(x+1, y)$ or $\operatorname{solve}(x, y-1)$.Otherwise there is ability to increase the depth of the interval $s[x\ldots y]$: $s_x$ is ( and $s_y$ is ): No matter how you determine the ? between $s[x+1\ldots y-1]$, $s_x$ and $s_y$ always form a match to increase the depth by one, so $\operatorname{solve}(x, y)=\operatorname{solve}(x+1, y-1)+2^{k}$, where $k$ equals to the number of ? in the interval $s[x+1\ldots y-1]$. Either $s_x$ or $s_y$ is ?: You can determine whether the ? can be matched or not, and if matched, it's similar above, else we can just ignore the ?. Both $s_x$ and $s_y$ are ?: If we determine $s_x$ to be ( and $s_y$ to be ), it's $\operatorname{solve}(x+1, y-1)+2^{k}$. If we determine $s_x$ to be )(and keep $s_y$ undetermined), it's $\operatorname{solve}(x+1, y)$, and $s_y$ to be (, it's $\operatorname{solve}(x, y-1)$. Note the situation that $s_x$ is ) meanwhile $s_y$ is ( will be calculated twice, so we need to subtract $\operatorname{solve}(x+1, y-1)$ from it. Then we can solve Div1 D1 in $O(n^2)$. But I had trouble optimizing it to $O(n\log n)$ or better. Can someone help?Upd: My code for Div1 D1: 66373927
 » 3 years ago, # |   +8 In problem D. Beautiful Sequence The only input line contains four non-negative integers a, b, c and d (00
•  » » 3 years ago, # ^ |   +14 The problem statement says $0 < a+b+c+d \leq 10^5$. I see why this could be misinterpreted, however it is not a mistake as it does not imply $0 < a, b, c, d$.
•  » » » 3 years ago, # ^ |   +8 you are right. I misinterpreted. Thank you for pointing out
 » 3 years ago, # |   0 Is there any reason that my all the solutions were skipped???
•  » » 3 years ago, # ^ |   +3 Either you've shared your codes with somebody during contest or probably you'll be using online compiler like ideone in default mode public . And during the contest someone else have just copied and pasted your code and so you have been removed from this contest.
•  » » » 3 years ago, # ^ |   0 Thank you so much
 » 3 years ago, # |   0 I coded E 10 minutes into the contest. When I was thinking of whether I should submit or not because it seems improbable for me to be able to solve E in 10 minutes, my PhD advisor called me and saved me the dilemma.I just submitted and found out the solution was correct after all :(
•  » » 3 years ago, # ^ |   0 The important part is you can solve it.
 » 3 years ago, # |   +12 When will the editorial be published?
 » 3 years ago, # |   0 can anyone explain me how to solve div2-D/ div1-B ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Form a graph with 0,1,2,3 as the nodes and edges from i to i+1 and i to i-1 for each i in [1,2] and the edges 0->1 and 3->2. Then perform a DFS from each node and check if all the frequency of occurrence of each node can be made zero. Whenever a node is visited, decrement its frequency. When the frequency of a node becomes 0, then you can't visit it. Also, the DFS should be modified, since from one node, you should visit only one of the adjacent nodes. The answer is the order in which the nodes are visited if the frequency of all the nodes are made 0.https://codeforces.com/contest/1265/submission/66381723
•  » » » 3 years ago, # ^ |   0 I get the idea now!
 » 3 years ago, # |   -24 easily passed div2c&e... pity went sleep early last night, or maybe rating++
 » 3 years ago, # | ← Rev. 2 →   +118 My approach for problem Div.1D :Given a string $s$, how to calculate its depth? It equals the number of positions where it reaches a depth for the first time. For a position $i$, suppose that there are $a$(s in $s[1,i]$ and $b$)s in $s[i+1,|s|]$, then we count this position if and only if $s[i]=$( and $a\le b$. Example: for string (()()), we count positions $1,2$.When the string contains ?, things become harder. We iterate each position and find the number of string in which this position should be count. For a position $i$ that $s[i]=$( (if $s[i]=$?, we assume it's (), $a$ and $b$ are the same as above, $c$ is the number of ?s in $s[1,i]$, $d$ is the number of ?s in $s[i+1,|s|]$. Then the answer for this position is \begin{aligned} \sum_{i\le j}{c\choose i-a}{d\choose j-b} \end{aligned}Bruteforce is $O(n^2)$. But we can find that \begin{aligned} &\sum_{i\le j}{c\choose i-a}{d\choose j-b}\\ =&\sum_{i+a\le j+b}{c\choose i}{d\choose j}\\ =&\sum_{i+a\le j+b}{c\choose c-i}{d\choose j}\\ =&\sum_{c-i+a\le j+b}{c\choose i}{d\choose j}\\ =&\sum_{i+j\ge a-b+c}{c\choose i}{d\choose j}\\ =&\sum_{i\ge a-b+c}{c+d\choose i} \end{aligned}$c+d$ is a constant (or minus $1$ when $s[i]=$?), thus the problem is solved in $O(n)$.
•  » » 3 years ago, # ^ |   +13 In the second step $\sum_{i+a\leq j+b} \binom{c}{i}\binom{d}{b}$shouldn't it be $\sum_{i+a\leq j+b} \binom{c}{i}\binom{d}{j}$ ?
•  » » » 3 years ago, # ^ |   0 Yes. Thanks. Now it's fixed.
•  » » 3 years ago, # ^ |   +10 share a simple way to get formula instead of math.just let all ? be ( first. then $delta = b - k$, where $b=$#( before i, $k=$#) after i.then any ? no matter before/after i, change to ). will make $delta$ $-1$. and we wanna goal that $delta <= 0$. then get the answer equal to prefix sum of binomial.
•  » » » 3 years ago, # ^ |   +16 Elegant idea! Thanks for sharing!
 » 3 years ago, # |   0 Anyone want to explain their solution for Div1 E? I saw from other comments that it is a problem that has appeared before, but it seems like it's mostly appeared on Chinese contests so I can't read the solutions :(
•  » » 3 years ago, # ^ |   +21 Brief Outline: The problem is equivalent to minimizing the sum of squares of outdegree of each node. Create a min cost flow graph where each unassigned match corresponds to an auxillary node, connected with cap 1 cost 0 to source and cap 1 cost 0 to the two players. For each player, add edges of cap 1 with costs $2o+1, 2o+3, ...$ where $o$ is the current outdegree of the node.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Ah thanks, the sum of squares reduction was not at all obvious to me. Neat trick, in the end I guess it's just complement counting. The MCMF after that makes sense. It's a cool problem!
 » 3 years ago, # |   0 Good Luck!
 » 3 years ago, # |   0 how do you solve div2 E
•  » » 3 years ago, # ^ | ← Rev. 3 →   +7 Let $E(i)$ represent the number of days to reach the $i^{th}$ mirror. Then we have:$E(i) = E(i-1) + 1*(p_i/100) + E(i)*(1-p_i/100)$Basically the equation means that if you reach the $(i-1)^{th}$ mirror, then with $p_i$ probability you reach the $i^{th}$ mirror the very next day, or you start over and reach it after the expected number of days to reach the $i^{th}$ mirrorYou can rearrange the equation to get a formula for $E(i)$ in $p/q$ form and solve using modular arithmetic.Base case is $E(1) = 1$ and final answer is $E[n+1]-1$
•  » » » 3 years ago, # ^ |   +4 I use similar approach.But i think (1−pi)/100 may be replaced with (1-pi/100)
•  » » » » 3 years ago, # ^ |   0 My bad. You are right. I forgot while writing that $p_i$ is given as a ratio to 100. Edited
 » 3 years ago, # |   +16 The constraints of div1.E is too small. Actually it can be solved in $\Theta(n^4/w)$ by optimizing the process of cost flow.
 » 3 years ago, # |   +37 Please provide the editorials.
 » 3 years ago, # | ← Rev. 2 →   +66 There is a hard version of Div.1 B (s_i can range in [1,20000]) from my own host contest in the past: https://codeforces.com/group/gRkn7bDfsN/contest/210347/problem/DEverybody can give it a try~
 » 3 years ago, # |   0 For div2 problem A: I am getting a segmentation fault which I am trying to debug but unfortunately was unable to debug. Can anyone help me find the error I have made? Here is the link to code: Link
•  » » 3 years ago, # ^ |   +3 You have a typo in line 14 — it should be j++, not i++.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 But it becomes confusing for me when I print t. How this typo assigning t to a garbage value? where he is not using t later in the while loop.
•  » » » 3 years ago, # ^ |   0 Thank you so much for pointing that out :)
 » 3 years ago, # |   +63 Where is editorial ?
 » 3 years ago, # |   +35 Hi chemthan, we need an editorial, thanks!
•  » » 3 years ago, # ^ |   +3
•  » » 3 years ago, # ^ |   +10 Sorry for delay. We are busy now. Hope can do it asap.
 » 3 years ago, # |   0 Waiting for author's solutions to the problems...)
 » 3 years ago, # |   0 It's O(n). Why am I getting TLE. https://codeforces.com/contest/1264/submission/66382862
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Your last while doesn't have any reason to stop
•  » » » 3 years ago, # ^ |   0 Oooo... got it. What a bug?
•  » » » 3 years ago, # ^ |   0 I get into problems during contest for these silly mistakes. And can't find what's wrong? How can I get rid of that?
•  » » » » 3 years ago, # ^ |   +18 Print debug statements. For example, your while loop bug can be found by just including a debug statement in the loop. Imagine you're the compiler and run everything in your head. Take a deep breath and tell yourself that you love debugging and there's nothing else you can't debug.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +10 It's not a silly mistake, or at least I don't call it so. You learn not to make these mistakes after failing at them. Next time when you have TLE you probably will look for infinite loops first, and after couple of times you'll start paying more attention to them while you're coding. Best way to not make these mistakes during the contest will be to make them during the practice!
 » 3 years ago, # |   +3 Well I am so weak,Can somebody tell me how to do Div2 C?Thanks!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 take minimum gold (all with maximum solve)take silver until it's greater than goldrest til n/2 is silverwhile taking g,s,b make sure you are not violating rules 2,4,5finally have a check if conditions are fulfilled with your g,s,b
 » 3 years ago, # |   0 How to solve Div2 prob B, my solution is getting TLE. What is wrong with it? Would someone please explain
•  » » 3 years ago, # ^ |   0 I think your submission has complexity like t*n*n which is very large to complete in 1s even the sum of n from all test cases in the input doesn't exceed 2⋅10^5
•  » » » 3 years ago, # ^ |   0 What is the efficient solution
•  » » » » 3 years ago, # ^ |   0 See the editorial I use the same approach
 » 3 years ago, # |   0 When will the editorials be uploaded?
 » 3 years ago, # |   0 Waiting for the editorial....
 » 3 years ago, # |   +17 At least let us know when the editorial will be published? I am bored and tired of checking.
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   0 https://codeforces.com/contest/1264/submission/66453921Looking at the comments my idea is similar, we first calculate answer with no checkpoints (which works, since I pass Div2E), and afterwards if we add a checkpoint j in interval [i, k], we have to decrease the answer by prod(i, j — 1) * prod(j, k) and add val[j — 1], when we delete j we need to merge intervals [i, j — 1] and [j, k], we do the opposite (add products, subtract val). This fails on first checkpoint addition on big test, so I cannot research that manually. Any ideas what I did wrong?
 » 3 years ago, # |   +11 I get the error message "You are not allowed to view the requested page" when trying to view the editorial. chemthan please take a look.
•  » » 3 years ago, # ^ |   0 Either it has been updated or there is some problem on your end because I can see the ediotrial. https://codeforces.com/blog/entry/71995And wow, 2-line code for F. :)