### 300iq's blog

By 300iq, 5 months ago, translation, ,

Hello everybody!

Now the winter SIS (Summer Informatics School) is taking place, and we, as part of the parallel A+ with its teachers, have prepared a complete Codeforces Round.

The round will happen at Jan/05/2019 19:35 (Moscow time) and will last for 2.5 hours. There will be 6 problems in each division.

The tasks of the round were invented and prepared by 300iq, scanhex, cookiedoth, allrats, osaaateiasavtnl., Qlukva, Forestryks, Dimon, LordVoldebug, romanovsavelij, golub, ismagilov.code,alexey_kuldoshin, LadyPython, UnstoppableSolveMachine under the guidance of teachers izban, VArtem, _meshanya_, pashka.

Also thanks for testing isaf27, isaf27_loves_me, Kurpilyansky.

And, of course, thanks to MikeMirzayanov for great systems Codeforces and Polygon.

Good luck everybody!

UPD: Since the registration opens before the recalculation of the rating after Hello 2019, in case of a division change, the participants will be moved to another division.

UPD: Editorial.

• +645

 » 5 months ago, # |   -62 and also thank me for commenting :)
 » 5 months ago, # |   +16 I'd very much like to see rated rounds which are shorter than 2 hours, not longer.For me, it's much easier to dedicate 1.5 consecutive hours to writing a contest than to have 2.5 or 3 hours available.
•  » » 5 months ago, # ^ |   -79 then you should make the contest
•  » » » 5 months ago, # ^ |   +42 Your comment was downvoted desperately, therefore we can conclude that CF community is unfavourably disposed towards Gassa making a contest.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 sorry, what i replied above means i look forward to Gassa's marathon contest ..
•  » » 5 months ago, # ^ |   0 I think that 1.5 hours isn't enough for CF contest with current format (5-6 problems).
•  » » » 5 months ago, # ^ |   -16 We should add a contest that runs for 1.5 hours on 2 or 3 problems of high difficulty with batch scoring. Unrated, of course.
•  » » 5 months ago, # ^ |   +8 I think maybe the div.3 rounds could be set as 1.5hrs long.
 » 5 months ago, # |   -44 2 consecutive contests to start the year? bring me some of that
•  » » 5 months ago, # ^ |   -36
 » 5 months ago, # | ← Rev. 6 →   -47 Cool! 300iq is now purple!Edit: Not anymore :(
 » 5 months ago, # |   -48 10 min delay :|
•  » » 5 months ago, # ^ |   +60 Haha, maybe you're comment in the wrong thread
 » 5 months ago, # |   -51 13 problem setters for 8 problems ...........
•  » » 5 months ago, # ^ |   -42 And that's excluding testers
 » 5 months ago, # |   -143 Dear CF, is it very cold there?Why are you freezing up?
•  » » 5 months ago, # ^ |   0 Do you have any idea about ICPC rules ? -_-
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yes, I have! I know that the standings were Frozen(or Paused)But I think no one got my joke! :(
•  » » » » 5 months ago, # ^ |   +57 Then learn How to Joke before Joking -_-
 » 5 months ago, # |   +24 The contest length is 2.5 hours in the blog but it shows 2 hours in the upcoming contests.
•  » » 5 months ago, # ^ |   -16 I think it is of 2 hour because normally all the contest of this type is of 2 hours... @300iq please make us sure
•  » » » 5 months ago, # ^ |   +8 It will be 2.5 hours length
•  » » 5 months ago, # ^ |   0 It is updated now.
 » 5 months ago, # | ← Rev. 3 →   -257 I think CODEFORCES hates me! Whatever comment(or reply) I make (I tried many kinds. Contributed, Made Memes, Helped people etc.), always get dozens of downvotes. I'm really sad about it. I don't want to contribute anymore! It's already -24 and going down.
•  » » 5 months ago, # ^ | ← Rev. 5 →   +3 grey-dude >:( it's under -24 now
•  » » 5 months ago, # ^ |   +15 well, think about the person you helped or people who laughed when they saw your memes,what i'm saying, is "Care about community!" and not about contribution points. if you helped somebody, that is good enough for you to keep doing it.
•  » » » 5 months ago, # ^ |   -93 Thank you so much @Khaner, I realize! I won't care about the contribution points from now on and put emphasis on contribution, studying, and practice.
•  » » 5 months ago, # ^ |   +12 The way you comment reminds me of attention girls in instagram
•  » » 5 months ago, # ^ |   -19 ask me bro ~:~
•  » » 5 months ago, # ^ |   0 awwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww!!!!!!!!!! I want to cry for you :'(
•  » » 5 months ago, # ^ |   +27 Because people are rankist!
•  » » 5 months ago, # ^ |   0 This is so sad alexa play despacito
 » 5 months ago, # |   -6 Oh no, the magic has gone :( Now I can't play to the chameleon
•  » » 5 months ago, # ^ |   0 No, it only changed because of rating update.
 » 5 months ago, # |   -9 After a bad experience of acm icpc, finally I am going to start this year with a new way and this is the first contest for my new journey for this year..
•  » » 5 months ago, # ^ |   +5 Good luck dude!
•  » » » 5 months ago, # ^ |   0 Thanks
•  » » 5 months ago, # ^ |   -16 you see, you guys see, that... everyone like you, like yourself, the attention seekers... Nobody cares you.. not even a little bit... you can go to the street and simply beg for attention.... you can come to pakistan even, but nobody cares.So the bottom line, NOBODY CARES.
 » 5 months ago, # |   0 I wonder about UPD2
 » 5 months ago, # |   +177 the winter SIS (Summer Informatics School) Hold up.
 » 5 months ago, # |   -13 Every JBer show me ur hands up
 » 5 months ago, # |   +5 The registration page says the contest is two hours long--is it still intended to run for 2.5 hours?
•  » » 5 months ago, # ^ |   +8 Maybe, Yes! (2.5 hours) Now it shows the length correctly. (Maybe it's updated)
•  » » » 5 months ago, # ^ |   0 Yup, looks like they corrected it :)
 » 5 months ago, # |   +7 Another contest with 300iq in problemsettersLooking forward to good tasks
 » 5 months ago, # |   0 The time of the match is very unfriendly to Chinese players.
•  » » 5 months ago, # ^ |   0 Practically everybody in East Asia too
•  » » » 5 months ago, # ^ |   +1 Yah. But south-east Asins are having a good time I think >_<
•  » » » » 5 months ago, # ^ |   0 Nope :( I'm in the part of South-East Asia where the contest starts at 11:35 PM :(
•  » » » » » 5 months ago, # ^ |   0 Yah, it will start at 10:35 PM in our country. I think we are almost at the same area . By the way, think about chinese people. they have to sit for contest at midnight :( Maybe we are a bit lucky :D
 » 5 months ago, # |   +22 Oof.. Red and Orange problemsetters in disguise! XD
 » 5 months ago, # |   -19 IS IT RATE...DELAYED?
 » 5 months ago, # |   0 Seems like it’s going to be a good round
 » 5 months ago, # |   -36 Is it rated?
•  » » 5 months ago, # ^ |   -18 yes.
 » 5 months ago, # |   -59 The comment is hidden because of too negative feedback, click here to view it.
 » 5 months ago, # |   +17 starts at 01:35 in South Korea... I'm willing to exchange tomorrows day time to a codeforce round XD
 » 5 months ago, # |   +21 Score distribution?
 » 5 months ago, # |   -9 newbie is coming !!
 » 5 months ago, # |   +2 Scoring Distribution?
 » 5 months ago, # |   +15 lol what a contest :D
 » 5 months ago, # |   +26 Wow!!! Problem F of div2 in not present in div1.wonder!! why it is so??
 » 5 months ago, # |   0 Nice difficulty-balanced div2D and div2E/F
 » 5 months ago, # |   +36 Is there a straight-forward solution for Div1B that's not a disgusting ton of mindless casework? That problem ruined the contest for me, so I hope there's something at least somewhat neat.
•  » » 5 months ago, # ^ |   0 I think its just two cases and then DP
•  » » 5 months ago, # ^ |   0 I don't think I have done any caseworking
•  » » 5 months ago, # ^ | ← Rev. 3 →   +48 If my solution is correct:Good table is either 1) Each row is XYXYXYXYSo after you fix 2 symbols in the first row (just iterate over all possible combinations), symbols in all other rows are known. For each row you should check what is "cheaper" to make — XYXYXYXY... or YXYXYXYX...2) Same, but with rows instead of columns.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +14 Blah, you're right, I suck. Did the first part of that observation and then did the second still with the mindset of rows, which made stuff blurry.
•  » » 5 months ago, # ^ |   +20 Either each row or each column consists of two alternating symbols.
 » 5 months ago, # |   +18 A was a little difficult to understand.
 » 5 months ago, # |   0 what is test 6 in Div2 D ?
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 n=7 p[i]={1 2 3 1 5 5} s[i]={1 -1 2 -1 -1 5 5} ans = 6 a[v]= {1,1,0,0,4,0,0};
•  » » 5 months ago, # ^ |   0 It's not optimal to make the value of node U as s[U]-s[parent of parent of U] if S[U]!=-1
•  » » » 5 months ago, # ^ |   0 why not
•  » » » » 5 months ago, # ^ |   0 If value of mid node (s[mid] is equal to -1) val then it contributes to answer only val and child of mid will contribute S[child]-s[parent of mid]-val but if val is 0 then they contibute sum of S[child]-S[parent of mid]. First case is sum of S[child] — sum of S[parent of mid]-val * numberofchild which is betterOptimal value of val is minimum of S[child]-S[parent of mid]
•  » » » » » 5 months ago, # ^ |   0 @CopeCope, Can you please say, why this code get WA? http://codeforces.com/contest/1099/submission/48076693
•  » » » » » » 5 months ago, # ^ |   0 Oh Got The Point .. I messed it up.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 If your subtree's root is at an even depth, then making its value 0 is not optimal. Consider the tree with edges 1-2, 2-3 and 2-4. If the values are 0,-1,5,5 respectively, you want the node 2 to take 5 and not pass on the value to the nodes 3 and 4
•  » » » 5 months ago, # ^ |   0 so what is the optimal answer ?
•  » » » » 5 months ago, # ^ |   0 The total optimal sum is 5, and not 10. Since node 2 is the root, it contributes to the sum for both 3 and 4, hence effectively reducing the total sum.
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 yes I understood the testhow to get the optimal answer in general
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +8 Check minimum sv from even node's sons, substract sv from node's father and you get optimal av (and sv too) for this node. If node is even and hasn't sons, you set its av as 0. For odd nodes you just calculate sv — sfather.
•  » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 mj
•  » » » » » » » » 5 months ago, # ^ |   +8 Suppose we calculated optimal sv and av values for every node on path 1 -> Parent of CurrNode. Let SumOnPath be sCurrNodesFatherIf CurrNode's depth is odd, we can unambiguously determine its av, the sv is given in input.Now move to the even depth case with 1+ sons Setting aCurrNode only affects contiguous sons ason value — the sson is constant. Since we can set aCurrNode to any value, we want to choose one that minimizes sum of ason. ason can be represented asason = sson — aCurrNode — SumOnPathSo is constant, so maximizing the value of aCurrNode will minimize a Also, av cannot be negative, so maximum value of aCurrNode is minimum of sson - SumOnPath Starting from root (where we have av and sv ) we can calculate all the values using dynamic programming.
•  » » 5 months ago, # ^ |   0 Try: 4 1 2 2 3 -1 8 5
•  » » » 5 months ago, # ^ |   0 Is the answer 8 ?
•  » » » » 5 months ago, # ^ |   0 yes
•  » » 5 months ago, # ^ |   0 Consider the case : 4 1 2 2 3 -1 7 7Answer should be 7
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Try this: 3 1 2 2 -1 3 Answer is 3
 » 5 months ago, # |   0 Can someone give a hint for E Div2?
•  » » 5 months ago, # ^ |   0 Notice that either all the rows or all the columns must have only 2 letters each. Thus, iterate for all the possibilities.
•  » » » 5 months ago, # ^ |   0 Why ? I get it, instincts, no one demonstrates it himself during the contest. But why is it so ?
•  » » » » 5 months ago, # ^ |   +46 It is clear that no column/row has only 1 letter. Then, we need to show that if some row has 3 or 4 different letters, then all of the columns must have only 2 different letters (and the same switching rows and columns).Then, suppose that row i has 3 different symbols. As no two consecutive letters can be the same, we can guarantee that there is an index j such that si, j - 1, si, j and si, j + 1 are pairwise different. Also, as {si, j - 1,  si, j,  si + 1, j - 1, si + 1, j} = {si + 1, j - 1,  si + 1, j,  si + 2, j - 1, si + 2, j} (= {'A', 'C', 'G', 'T'}), it must happen that the letters in si, j - 1, si, j are the same as those in si + 2, j - 1, si + 2, j. Analogously, {si, j, si, j + 1} = {si + 2, j, si + 2, j + 1}. Since si, j - 1 ≠ si, j + 1, from our construction, in order to accomplish these two equalities si, j = si + 2, j, and thus, si, j - 1 = si + 2, j - 1 and si, j + 1 = si + 2, j + 1. You can continue this argument for the whole row, and discover that row i and row i + 2 are the same. Using induction, every row j such that i mod 2 = j mod 2 must be the same.But then, every column repeats characters every 2 steps, as we wanted to show.
 » 5 months ago, # |   +53 The problems were very good! Fantastic! Thank you for great contest!!!
•  » » 5 months ago, # ^ |   0 Nice to hear, thanks
•  » » 5 months ago, # ^ |   +1 Why did this post get so many upvotes ? I get it, the contest was awesome but anybody could've commented that...
 » 5 months ago, # |   0 Can anyone share their approach to E? Also, for div 2 F, I think the solution would be dfs-based, at each step finding how many cookies can be eaten if Mitya ends the game at that point. Can someone confirm this?
•  » » 5 months ago, # ^ |   +11 Yes that's right if we sort all cookies from root to node v, we want maximum x such that the first x cookies cost is smaller equal to T — 2 * (sum of all edge from root to v). We can do it with segment tree and after that in every move (except root) Mitya goes to the second child (by amount of its dp) and we can find the answer.
•  » » » 5 months ago, # ^ |   0 Hey..could you elaborate further on how to find the maximum x using segment tree? The remaining solution is clear.. Thanks!
•  » » » » 5 months ago, # ^ |   +5 For each node save number of cookie and sum of cookie and determine that go to left node or right node plus number of left node cookie.My code :48007201
 » 5 months ago, # |   -29 Horrible, misleading problem statements!!
•  » » 5 months ago, # ^ |   +3 But you did very well. Congratulations!!!
 » 5 months ago, # |   +26 In problem Div1D, don't you have to dynamically keep the Huffman tree in order to answer the queries, or is there an easier approach?
•  » » 5 months ago, # ^ |   0 You can change it to just insertions and undoes with the dynamic connectivity trick. However I don't see how to do undoes without persistence, which would definitely TLE.
•  » » 5 months ago, # ^ |   +7 Sort the numbers. Calculate the partial sum. At first, set ans = cnt-1. Then, for each i reduce ans by one if a[i] > partial_sum[i-1]*2. This can be done with a segment tree because the number of such cases is at most lg(1e9).
•  » » 5 months ago, # ^ |   +1 I passed pretests with this idea: sort all numbers in ascending order, count how many numbers such that they are bigger than twice the sum of all previous numbers, let this count be K and N is total number of numbers, then the answer is N — K.
•  » » 5 months ago, # ^ |   +18 There is an observation, that the result is #fishes - #(fishes which are more than 2 timesheavier than all fishes lighter than them (after sorting)).Next observation: is some fish can decrease the result by one, it is a result of a lower_bound operation for some power of 2. It helps easily find fishes which can decrease the result.
•  » » » 5 months ago, # ^ |   +14 Yeah, once you figure out the observation, it’s easy.
•  » » » 5 months ago, # ^ |   +10 How did you prove 1st observation ??
•  » » » » 5 months ago, # ^ |   +105 I don't prove, I code :P
•  » » » » » 5 months ago, # ^ |   +5 Then, where did you come up with that from?
•  » » » » » » 5 months ago, # ^ |   +3 I guessed/observed that they should eat themselves from the smallest ones. What happens when second smallest fish after eating the smallest fish becomes greater than the third smallest fish? The order is distorted, but the intuition is, that because of that the fishes became very close to each other, so now I will be able to do many dangerous fights (until the situation with much greater fish happens, because then for sure I won't be able to do the dangerous fight).
•  » » » » » 5 months ago, # ^ |   +13 what do you do when you get WA in this case? I mean how do you tell whether it's a bug or wrong observation? :P
•  » » » » » » 5 months ago, # ^ |   +5 It appears he never has bugs:))
•  » » » » » » » 5 months ago, # ^ |   +7 apparently he never make wrong observations too :D
 » 5 months ago, # |   0 went for overkill on DIV2D with hld and still WA
 » 5 months ago, # | ← Rev. 2 →   -82 What a great contest!!
 » 5 months ago, # |   0 Was O(QlogQlog109) supposed to fail in D1D or only my implementation has a too big constant?
•  » » 5 months ago, # ^ |   0 I passed pretests with such complexity.
•  » » » 5 months ago, # ^ |   0 :( Maybe the 3000 ms TL was too high then. :/
•  » » 5 months ago, # ^ |   0 Your implementation has a very bad constant. We have java solution which uses less than 1,3 seconds in all tests
 » 5 months ago, # |   +10 Why would Div1C be excluded and not being used for problem F of Div.2 version, instead there comes a new problem in place of this? :O
•  » » 5 months ago, # ^ |   +8 I guess they just had too many problems (because they were doing this as a class work) and wanted to include all of them.
•  » » » 5 months ago, # ^ |   -18 It was no a classwork. We just thought that div2 is too easy for div1 and we didn't want to give our div1 for div1 because it can be too hard for them, and we wanted to give for div1 more problem there you need to write not very simple code, so we decided to put it there
•  » » 5 months ago, # ^ |   0 They got too much problems in the set bruh. Current div2f is bit easy for div1c
 » 5 months ago, # |   -7 Most contests are imbalanced these days :'(
 » 5 months ago, # |   +4 problem D was very nice :DD , how to solve Div2E ?
 » 5 months ago, # |   0 HELP,what is pretest 4 for the ACTG problem?
 » 5 months ago, # | ← Rev. 2 →   0 what is test 14 in Div2 D ?
•  » » 5 months ago, # ^ |   0 n=7 p[i]={1 2 3 1 5 5} s[i]={1 -1 2 -1 -1 5 5} ans = 6 a[v]= {1,1,0,0,4,0,0};
•  » » » 5 months ago, # ^ |   0 my output is 6,is it correct?
•  » » » 5 months ago, # ^ |   0 can u check whats wrong in my code? link
 » 5 months ago, # |   0 Very great contest for non Div-1 coders like me. I particularly liked the gradient of submissions and the Div2-D problem. Ideal contest to increase rating for a graph lover like me.
 » 5 months ago, # |   0 what is test 4 in div2 F?
•  » » 5 months ago, # ^ |   +5 Mine was reading the statement again "The total time , including the descend and ascend". I don't know if yours failed from the same cause;
•  » » 5 months ago, # ^ |   0 It was just a random test
 » 5 months ago, # |   0 Does anyone know what was pretest 16 for Div2D?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Answer needs to be long long. Explanation : s[i] <= 10^9. Sample case : 5 1 1 2 3 1 -1 -1 10^9 10^9
 » 5 months ago, # |   +3 Isn't it a O(n) solution(Div2 B)? 48005949. If so, why did it pass a test n = 1e9?
•  » » 5 months ago, # ^ |   0 May be 1e9 was not part of the pretests
•  » » 5 months ago, # ^ | ← Rev. 2 →   -7 It should be possible to do about 1e9 cpu instructions in less than a second.So it can fit into a 1e9-for if the constant is small enough.
•  » » » 5 months ago, # ^ |   0 No
 » 5 months ago, # |   0 is Div2 F binary search? I was trying to check whether it is possible to eat x cookies, but couldn't succeed.
•  » » 5 months ago, # ^ |   +3 No. We don't have a solution, using binary search, it is just dp with data structures, you will be able to read it in editorial soon
•  » » » 5 months ago, # ^ |   0 alexey_kuldoshin pshishod2645 I do have a solution with binary search. BIT+binary search. submission
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 Oh, ofcourse you can do fenwick + binary search, but u don't need binary search here! U can use binary lifting!) Your complexity will be nlogn but not nlog^2, and fenwick with binary lifting was our main correct solution
 » 5 months ago, # |   0 What is testcase 7 in div2 d ?
 » 5 months ago, # |   +11 That moment when you solve E 5 minutes before the end of the round but yiu cant submit it because you have the worst internet connection in the universe :( :( :( I fucking hate my life :( :( :( Hope its not correct :( :( :(
 » 5 months ago, # |   +118 The problem setter of Div1E should stop creating problems.
•  » » 5 months ago, # ^ |   +6 Yes, it is a quite idea-less task. It is a pure technical problem.
•  » » 5 months ago, # ^ |   +13 first tell who r u
•  » » » 5 months ago, # ^ |   0 lul he's problem setter of Div1E
•  » » 3 months ago, # ^ |   0 And you should stop creating fake accounts.
 » 5 months ago, # | ← Rev. 2 →   0 i thought the instructions where relatively unclear. My reading comprehension is poor so it was an unnecessary challenge:/
 » 5 months ago, # |   +62 My screencast will be available here after it finishes processing: https://youtu.be/WR9rMvE-d9Y
 » 5 months ago, # |   0 C felt so empty :(A how could initial height be 1 if we have two rocks.. and calling the second rock "second rock" doesn't that mean the first one is heigher but that wasn't mentioned.sadly I'm not good in graphs to try D .
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 if you had examined the sample inputs you would have noticed that wasn't true (for A).
•  » » » 5 months ago, # ^ |   0 that's called invalid input and they should not do tricks here
 » 5 months ago, # |   0 Is there a specific reason why integer overflow hacks didn't work on this contest? A person I tried to hack used int everywhere, but somehow his submission in C++11 managed to print 3000000000. Is the int limit bigger than 2^31-1? :O
•  » » 5 months ago, # ^ |   +13 Classic trick: #define int long long 
•  » » » 5 months ago, # ^ |   0 Oh, I see now, I fell for that.Thank you!
 » 5 months ago, # |   +45
 » 5 months ago, # |   +5 i got the #victoryroyale on this contest
 » 5 months ago, # |   +35 Let me ask. Is F just a HLD on a suffix tree with segment tree with operations like "do x[i]=x[i]+1 on the interval" and "get sum of x[i]*a[i] from the interval"? I think that I was close, I had tree and HLD already but the fact that we have to do queries in a middle of an edge defeated me and I run out of time.
•  » » 5 months ago, # ^ |   +31 I don't know how to do it with 1D queries, our solution have sweep line at each heavy path...
 » 5 months ago, # |   +12 cool picture in div2F
 » 5 months ago, # |   0 Is there anyone solve Problem C (div.2) with DP ?
•  » » 5 months ago, # ^ |   0 Yes I do; 1 line typo .. BAAM!!
•  » » 5 months ago, # ^ |   0 yes, I did but unfortunately wrote 'n' instead of 'k' in the inner loop and not even a single pretest had k>n case. AC solution after the contest: submission
 » 5 months ago, # | ← Rev. 3 →   +1 How to solve Div2 F?
•  » » 5 months ago, # ^ |   +8
•  » » 5 months ago, # ^ | ← Rev. 4 →   +1 We can solve this problem by using minimax + greedy and segmentation tree. Assume we are at some node u in the tree, then we have remaining time = T - 2 * sum_l, where sum_l is sum of l over all edges from root to current node u. Now we can use a segmentation tree to greedily eat as many cookies with our remaining time from min. time required per cookie to max. time required per cookie for cookies on path from root to u. This segment tree has a leaf for each possible value of ti (so 1...1000000), and stores per interval total cookies in the interval and total time required to eat all cookies in the interval. When we arrive at node u, we add x[u] cookies to all intervals t[u] lies in. When we backtrack from u, we remove the x[u] cookies. Vasya always cuts the edge that leads to the best result, but in the root Mitya can choose an edge before Vasya is allowed to cut. This solution is O(N log 1000000). Corresponding code: https://codeforces.com/contest/1099/submission/48030249 .
 » 5 months ago, # | ← Rev. 2 →   -19 .
•  » » 5 months ago, # ^ | ← Rev. 2 →   -16 .
 » 5 months ago, # |   +33 Just curious, why is div2 F not available in div1?
•  » » 5 months ago, # ^ |   +1 No it was rated, but ratings will be updated later.
•  » » » 5 months ago, # ^ |   0 thanks :)
 » 5 months ago, # | ← Rev. 2 →   -13 My solution for the problem C was shown as "accepted" but then after the contest, they realised I had a wrong answer? Like.. How is that allowed!!?
•  » » 5 months ago, # ^ |   +157
•  » » » 5 months ago, # ^ |   0 Not anymore..
•  » » 5 months ago, # ^ |   +52 To give a serious answer:There are pretests for the contest, where you will be given a particular verdict (in your case, Accepted). Afterwards, the submissions are run on a more thorough set of test cases, where the real verdict is made.There are a few reasons for this – one is that it lightens the load on the servers to only run the submissions on <20 cases, as opposed to ~100. Another is that it allows for "hacking", where you can look at other people's submissions for a problem that were accepted on pretests but have a bug in them, and create a test case that exposes the bug. All the successful test cases created from hacking are added to the total test case suite that runs after the contest. This is pretty beneficial to problem setters, because it can be difficult to think about the wrong solutions that will be made, and the corner cases that must be created to expose the bugs in the wrong solutions. The hacking system essentially crowdsources the creation of thorough test cases, making a more accurate problem for everybody.Failing on system tests is, unfortunately, part of the game here. On the bright side, it could be worse: Some contests, like Topcoder and Facebook HackerCup don't run your code on any test cases until after the contest is over.
•  » » » 5 months ago, # ^ |   +26 actually verdict is "pretests passed" that should give one some hint
 » 5 months ago, # |   0 Is it only me or somebody else also who was expecting a higher rating change? Rating Predictor is showing +162 but I got just +73 whereas my friends' ratings changed as per shown in rating predictor.
•  » » 5 months ago, # ^ |   0 I saw the same bug previous round
•  » » » 5 months ago, # ^ |   0 Did it get resolved?
•  » » » » 5 months ago, # ^ |   0 IDK, i think it`s not resolved for this moment...
 » 5 months ago, # |   0 For those who are afraid of precision errors.. Div2-B Solution
•  » » 5 months ago, # ^ |   0 Can you explain it,please
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 We begin with a single square and then add more squares gradually. let a[0] and a[1] be the length and width(so both are 1 initially) Now, each time I'll pick the smaller of the two(which is a[0] since it is sorted) and increment it by 1(i.e. add one more segment to it)..with this extra segment drawn, I'll be able to complete a[1] more squares using this new segment as guide. Stop when at least n squares are drawn(i.e. while cur
•  » » » 5 months ago, # ^ |   +13 always put a space after a comma.
•  » » » » 5 months ago, # ^ |   +28 Always start a sentence with a capital letter, grammar.nazi!
•  » » 5 months ago, # ^ |   0 Or just notice that solution can only be 2*sqrt(n),sqrt(n)+sqrt(n)+1 or 2*(sqrt(n)+1).
•  » » » 5 months ago, # ^ |   0 How you proved it?
•  » » » » 5 months ago, # ^ |   0 Optimal solution is to have sides (horizontal and vertical) as much as equal as you can. If you have x horizontal lines and y vertical, then number of squares formed is x*y. So square root minimize number of lines needed.
•  » » » » 5 months ago, # ^ |   0 how did you prove it?*
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +22 H ow did you prove it? *(Every sentence starts with a capital letter.)
•  » » » 5 months ago, # ^ |   0 Or it can be 1+floor(sqrt(4n-3))
•  » » » » 5 months ago, # ^ |   0 How did you get that?
•  » » » 5 months ago, # ^ |   +5 Or just check sqrt-20 to sqrt+20 :)))Code: 47977441
 » 5 months ago, # |   0 How to solve Div2 D???
•  » » 5 months ago, # ^ |   +3 Hint: the best S[i] for some unknown node is the minimum S[j] of its children, or the same of its parent if it has no children. After figuring out the optimal S[i] for every node, you can restore the original A[i] for each node.
•  » » 5 months ago, # ^ |   0 SpoilerFigure out the lower-upper bound lu[i] of s[i] . If s[i] is determined then lu[i] = {s[i], s[i]} else lu[i] = {s[p[i]], min(s[u]) with u is a child of i}. Well this is because a[i] >=0 then s[i] >= s[p[i]] and for every single child u of i then s[i] <= s[u].Obviously a[i] = s[i] — s[p[i]]. Sum it up : S = Sum of a[i] = Sum of s[i] — Sum of s[p[i]]. So now for i = 1 to n you could calculate how many times of s[i] contributes to the sum S above, let call it cnt[i];To satisfy S is as small as possible: -if(cnt[i] >=0 ) then s[i] must be the lower bound-if(cnt[i] < 0) then s[i] must be the upper bound.So here you now all about s[i] it would be easy to calculate S
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 thanx juanigsrz and lantrungseo
 » 5 months ago, # |   +16 Editorial?
 » 5 months ago, # |   -20 is it rated?
 » 5 months ago, # | ← Rev. 2 →   -26 this contest was little bit easier then this (https://codeforces.com/contest/1092) div3 contest
 » 5 months ago, # |   0 editorial?
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 It's hereUPD: Oh... It's not translated yet.
•  » » » 5 months ago, # ^ |   -19 yeah you know what about writing it in English in the first place like a normal person not in your language that no one cares about
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   -20 Considering Codeforces owners, authors of this contest and a huge part of this community are russians, I think your trolling sucks.
•  » » » » » 5 months ago, # ^ |   0 no one cares. and it's not trolling it's a fucking fact.
 » 5 months ago, # |   0 I did'nt get the problem statement of div2-B, can anyone pls elaborate it.
•  » » 5 months ago, # ^ |   +1 here -> Visualized solution. Solution : -find the first number square num_sqr , which is bigger then n. -if n > (num_sqr — sqrt(num_sqr), print 2 * sqrt(num_sqr) — else print 2 * sqrt(num_sqr) — 1
•  » » » 5 months ago, # ^ |   0 Why is it true?
•  » » » 5 months ago, # ^ |   0 Thanks for the Visualized solution !! Now I got it.
 » 5 months ago, # |   +12 Where is the editorial?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 It's here!It's not Complete/Translated fully yet.
•  » » » 5 months ago, # ^ |   -13 fully translated yet*
 » 5 months ago, # |   0 when editorial will come ??
•  » » 5 months ago, # ^ | ← Rev. 2 →   -20 when will the editorial come?*
•  » » » 5 months ago, # ^ |   +12 When will you shut the fuck up dumb nazi reeeeeeeeeeee
 » 5 months ago, # |   0 when the tutorial will be available?
 » 5 months ago, # |   -29 In the previous contest, the editorial was uploaded so early(before the contest). But the editorial of this contest is not uploaded yet! -_-
•  » » 5 months ago, # ^ |   0 in general it is grammatically incorrect to start a sentence with "but".
 » 5 months ago, # | ← Rev. 2 →   0 The Editorial is here from 15 hours but it's not finished (code & English translation isn't found): https://codeforces.com/blog/entry/64331
 » 5 months ago, # |   0 As the editorial is not published till now can somebody tell how to solve div2E and div2F?
•  » » 5 months ago, # ^ |   0 I have explained how to solve Div.2 F here: https://codeforces.com/blog/entry/64296?#comment-482494 .
 » 5 months ago, # |   -13 is it rated?
 » 5 months ago, # |   0 I love that contests are being held so often now :) I am learning a lot of things thanks to that , I have high hopes that it will keep going this way !!!!
•  » » 5 months ago, # ^ |   0 i don't think so lul
•  » » 5 months ago, # ^ |   -9 you do not need to put a space between the last word in your question/sentence and the question mark/exclamation mark.
•  » » » 5 months ago, # ^ |   +40 Every sentence starts with capital letter.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   -7 I appreciate your work, grammar.nazi. But I think you're in a wrong place. It's a community of Programming/Programmers. People type their comment here to express their idea. So, grammar doesn't matter here that much. People may learn many sides of grammar and be aware of grammatical mistakes but it's kinda disturbing. I think you'll get a bunch of downvotes every time you try to correct people's comments (I upvoted your reply). Don't mind.[Sorry that my reply may also have some grammatical mistakes. (I'm not a native speaker of English and I think many people aren't too.)]
•  » » » » 5 months ago, # ^ |   0 The account was created for the sole porpuse of trolling so please do not encourage him.
 » 5 months ago, # |   0 is there a DP approach to solve C?
 » 5 months ago, # |   +1 When is the editorial translation going to be here?
 » 5 months ago, # | ← Rev. 2 →   0 Is there some one know the link of this problem: given a string, and some query [l,r] find the maximum i such that s[l,i]==s[r-i,r]... I'm pretty sure it is in codeforces gym thanks
•  » » 5 months ago, # ^ |   +9
•  » » » 5 months ago, # ^ |   0 thank you sir
 » 5 months ago, # | ← Rev. 3 →   +18 I have a sol to solve problem F:first we can solve the lcp[i,l] l<=i<=r not consider the bound of r restriction.then we can try the minus old and add new value of point i s[l,l+i]==s[r-i,r].we can solve first question by sweepline the increasing orderof rank[l], and build 2D segment tree, it can be solvedby O(n*lg(n)^2)then we consider to find point s[l,l+i]==s[r-i,i].there is a problem in gym find the maximum i, if we got maximum i, then we can got sec maximum j thats[l,l+j]==s[r-j,r] so we can get it is a repetition of s[r-i,r-j-1]==s[r-j,r-j+i-j-1].....it is a arithmetic progressionwe can find the next bound of this arithmetic progression by O(1) and this number of segment is not bigger than log(n) with small constant factor
•  » » 5 months ago, # ^ |   +8 happy new year!! brute force Accepeted I think my code can be hacked,welcome to hackhttps://codeforces.com/contest/1098/submission/48087000
 » 5 months ago, # |   +22 What a great contest!!
 » 5 months ago, # |   -36 Such shameless authors , nearly 25 people involved in the round and still no translation for the editorial. I think this affects not only the authors but also codeforces's reputation.
•  » » 5 months ago, # ^ |   +50 We sincerely apologize for the delay with the English version of the editorial. It's now available (link).However, before writing offensive & demanding comments, please understand that yesterday was the last day of the camp, and all of us needed to travel really long way home. Quite obviously English is not a mother tongue for any of the high-school students who prepared the round, and it takes a lot of time to write something readable.
•  » » » 5 months ago, # ^ |   +8 I apologise for being so unthoughtful.
•  » » » » 5 months ago, # ^ |   0 I apologize too