### DarthKnight's blog

By DarthKnight, history, 3 years ago, ,

— Hey, It's me again. Plain to see again...

— Oh crap, it's PrinceOfPersia again :|

I'm here to introduce you: Codeforces round 362. It's gonna take place on 196th day of 2016.

I'm the writer of this round. Not as always, there are 6 problems. I hope you enjoy.

I want to thank LiTi and Haghani for testing this round, dans and GlebsHP for helping me prepare the problems and MikeMirzayanov for legendary platforms of Codeforces and Polygon.

The main character of this round is Barney Stinson (high five ;)) and you're gonna help him with his problem.

I wish you all lots of Accepted solutions and hope to see no Skipped solutions ;)

Scoring will be posted soon.

GL & HF!

UPD: We decided that the contest has 6 problems (in each division, 4 shared). Duration will be announced as soon as we decide, but It's gonna be between 2 and 2:30 (inclusive).

UPD1: Duration is 2:15.

UPD2: Scoring is standard in both divisions: 500 — 1000 — 1500 — 2000 — 2500 — 3000

UPD3: Check out the editorial!

UPD4: System testing is over. Congratulations to the winners!

Div.1 Winners are:

Div.2 Winners are:

• +441

 » 3 years ago, # |   -36 Why are you talking to yourself? :/
•  » » 3 years ago, # ^ |   -23 You know I am Chinese, and I hate to read the foreign names such as Stinson.It is too hard for me to pronounce, so I decide change it in to “诗汀尚” in my mind.it is good for me to understand the meaning of problems!
•  » » » 3 years ago, # ^ |   -13 But I it is barney.... I improve...
•  » » » 3 years ago, # ^ |   0
 » 3 years ago, # |   +37 Nice to meet you again.
 » 3 years ago, # | ← Rev. 2 →   +56
 » 3 years ago, # |   0 Auto comment: topic has been updated by amd (previous revision, new revision, compare).
 » 3 years ago, # |   +83 announcement shud have been --The main character of this round is .... wait for it..................Barney Stinson
 » 3 years ago, # | ← Rev. 3 →   -40 Please do not put minuses :(
•  » » 3 years ago, # ^ |   +8 You always share photos with hands... :D
•  » » » 3 years ago, # ^ |   +4
•  » » 3 years ago, # ^ |   +3 Depends on problems, for example the last round was quite easy for tops.
•  » » » 3 years ago, # ^ |   +5 I agree. I wrote sometimes it's not enough time :)
•  » » 3 years ago, # ^ |   -31
 » 3 years ago, # |   +13
 » 3 years ago, # |   -63 It is Rated ??!
•  » » 3 years ago, # ^ |   +31 I think if this round won't be rated, they would write Codeforces Round #362(unrated).
 » 3 years ago, # |   0 hoping for an interesting problemset.. :)
 » 3 years ago, # |   +55 I hope non of the problems statments will be "you have to help Barney Stinson to meet your mother"
 » 3 years ago, # |   +6 Hope to See a Problem about the Brocode now that is going to be interesting to solve :D
 » 3 years ago, # |   +11 I hope the problems are translated properly to English. Some of the problem statements in the previous few contests could have been better.
 » 3 years ago, # |   +19 I extremely believe this round will contain less math problems than your past ones.
 » 3 years ago, # | ← Rev. 13 →   -18 Its going to be LEGEN..............wait for it......DARY LEGENDARY
 » 3 years ago, # |   -59 Is it rated?!
 » 3 years ago, # |   +133 Will it be possible to connect to codeforces.com during contest?
 » 3 years ago, # |   +1 I counted, Barney Stinson is truly have two hands and ten fingers, let's high five :P
 » 3 years ago, # |   0 Today is 2016/07/14, and it's 14^2 = 196 day of year =))Wish all contestants luck =))anw, this contest is my 40th contest, and I nearly get Expert =))
 » 3 years ago, # |   +24 So long that rng_58 has participated on CF. Waiting to see Petr and tourist too.
 » 3 years ago, # |   +2 Auto comment: topic has been updated by amd (previous revision, new revision, compare).
 » 3 years ago, # |   +78 I hope problems will be prepared better than Hackerearth June Clash 2016 (which is still haven't been rejudged)
•  » » 3 years ago, # ^ | ← Rev. 3 →   -123 Not my fault. shef_2318 prepared the checker for approximate problem(NOT ME) and we told admins to rejudge it and they did nothing :|
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +85 Your fault is that despite my warnings during the contest you haven't found bug in your checker. It was very easy to find, you just mixed up 1-indexation and 0-indexation.Actually I don't want to offend you, just want to say, that quality of those contest was not high, despite the fact that the problems were the cool. Hope that this one will be better.
•  » » » 3 years ago, # ^ |   +172 It's nice etiquette to say "sorry" instead of "that guy fucked up". It's not the first time I see your comment saying that sth is someone else's fault. Do you want to be necessarily mentioned by other organizers after you make a mistake?
 » 3 years ago, # |   0 i'm excited for this unusual round with 6 problems i'll try my best to solve atleast 3 of them.
 » 3 years ago, # |   +8 Hope that, Barney Stinson face easier problems than the previous (#361) Div2 Round.
 » 3 years ago, # |   +4 hope to get plus rating. I can't progress and getting frustrated :(
 » 3 years ago, # |   +14 I think it's going to be an awesome round because the awesome man is its main character!
 » 3 years ago, # |   +17 is it just me whose codeforces is working very slow and sometimes not even opening? its working slow since last night's contest, every other website opens instantly except codeforces.
 » 3 years ago, # |   0 Hope for 6 problems involving queries... :D
 » 3 years ago, # |   +2 I hope to turn to cyan color ! :D
 » 3 years ago, # |   +37 I have two wishes: 1. The English statements being clear. 2. Problem A loads up before 10 people get AC and we are like loading.. :/
 » 3 years ago, # |   +43 I'm lol about the duration time)
 » 3 years ago, # |   +13
 » 3 years ago, # |   +36 You were the author of round #326 and now it's round #362. Pretty much awesome :D :D :D
•  » » 3 years ago, # ^ |   0 So, can you tell which round will be next one?
•  » » 3 years ago, # ^ |   0 It will be awesome if he canbe the author of round #632 :D
 » 3 years ago, # |   0 нестандартненько
 » 3 years ago, # |   -6 It's going to be legen- wait for it......
 » 3 years ago, # |   +62 Except for maybe two rounds years ago, it's going to be my first round on Windows. I'm trying to install some IDE right now. Wish me good luck!#mylaptopbroke
•  » » 3 years ago, # ^ |   +5 Codechef has an online IDE if u need one :P :X
•  » » 3 years ago, # ^ |   0 Good luck, just keep your fingers crossed while running the code.. Nobody knows when he/she get a BSOD in windows :D
 » 3 years ago, # |   0 Auto comment: topic has been updated by amd (previous revision, new revision, compare).
•  » » 3 years ago, # ^ |   +30 People should problem E first it has got 25000 points :P
•  » » » 3 years ago, # ^ |   -15 Thank you, fixed.
•  » » 3 years ago, # ^ |   0 there's a typo in the scoring
 » 3 years ago, # |   0 there is an extra zero in "25000" :P
 » 3 years ago, # |   +52 I just captured a legendary pokemon
•  » » 3 years ago, # ^ |   0 On 19th, SRM and CF Round back to back! :D
 » 3 years ago, # |   +16 Congratulations to yao981113 for getting a perfect score on IMO! Celebrating by doing cf
•  » » 3 years ago, # ^ |   0 Congrats ! Who is he IRL ? My student got silver and I'm also really happy.
 » 3 years ago, # |   +64 'Barney consider a girl x to be better than a girl y if and only if: girl x has weight strictly less than girl y...'That's how K-pop fans harm their idols by putting them on a diet and making them skinny. I miss their healthy bodies.
•  » » 3 years ago, # ^ |   +60 1 kilogram is the ideal weight.
 » 3 years ago, # | ← Rev. 2 →   -70 You should be able to resubmit your hacked solution even after you've locked it. I feel like this is unfair for all those people who either lock problems for fun or by accident. Please bring justice. I know some people may copy other people's code, so maybe say able to resubmit up to 10-15 minutes after solution was hacked?
•  » » 3 years ago, # ^ |   +37 Wut?What if you copy someone's code? and btw you can't "lock" it by accident.
•  » » » 3 years ago, # ^ |   -26 Well if your solution is hacked, shouldn't you at least be able to have a chance to redeem yourself? How about when your solution is hacked, you can no longer view other people's solution for that problem? I feel bad for losing 750 points because of unable to resubmit...
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +6 You should lock your code if you are really sure. I just lost ~950 points because I missed one case.
•  » » » » » 3 years ago, # ^ |   +1 I guess you guys are right. Unfortunate, yes, but I am new to hacking/locking so sorry for complaint. Was fairly surprised and frustrated when I found out I couldn't resubmit. Ok, will reconsider to lock problems or not in the future.
•  » » » » » » 3 years ago, # ^ |   +22 If your problem is not locked, then you can resubmit if you are hacked. Resubmitting with a locked problem is totally unfair, because you could just upload another contestant's source code. Also, that's the beauty of it: "you can hack only if you lock, do you really want to?"
•  » » » » 3 years ago, # ^ |   +33 You can still redeem yourself by hacking other's solutions though.
•  » » 3 years ago, # ^ |   +25 This would be a very bad idea. If your not confident in your in your solution don't lock it. You can't allow someone to copy someone else's code in the middle of a competition.
 » 3 years ago, # |   +10 0.0e0 made my place Kappa
•  » » 3 years ago, # ^ |   0 "**b can not be non-zero if a is zero**" That shouldn't be allowed
•  » » » 3 years ago, # ^ |   0 read again, carefully
•  » » » » 3 years ago, # ^ |   0 I did, it means that either a or b must be positive, both of them can't be 0.
•  » » » » » 3 years ago, # ^ |   +1 "b can not be non-zero if a is zero"maybe this way: b has to be zero if a is zeroso 0.0e0 is totally fine (unfortunately for me... ).
•  » » » 3 years ago, # ^ |   0 0.0e0 a=0 d=0 b=0 what's wrong? b isn't non-zero
 » 3 years ago, # |   +1 I believe DIV2 D is a really cool problem :D I got the idea what to do but I couldn't finish in time :'( Really nice problem btw :D Thanks amd
 » 3 years ago, # | ← Rev. 2 →   +3 What's the idea behind Div2D/Div 1B? Couldn't find the formula for a vertex :/ Edit: I messed the letter, meant Div 1B :D
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 Div1A: You go up from each vertex up to their LCA. In query 1, you add cost to those paths, in query 2 you sum and print. I saw a nice trick to go up to LCA — at each step go to parent of the vertex with the largest index, until both vertices converge. But there are other ways, e.g. using set to find intersetction of two chains, or going up to root and then down to lca.
•  » » » 3 years ago, # ^ |   +5 I meant Div1B, I messed up, but thanks though :)
•  » » » » 3 years ago, # ^ |   +18 In Div1B, you first compute all subtree sizes; then for each node the expected time will be time of the parent + 1 + (sum of all subtree sizes of siblings)/2. Because by linearity of expectation, any sibling will go before current child with probability 1/2 and dfsing that sibling will take time equal to size of the subtree.
•  » » » » » 3 years ago, # ^ |   0 Thanks, I was not that far away from that :)
•  » » » » » 3 years ago, # ^ |   0 Thanks for this, I found it much better to understand than the editorial
•  » » » » » 16 months ago, # ^ |   0 thanks a lot! :)
•  » » » 3 years ago, # ^ |   0 I did that ^. But I stored the cost of the edges whose prices have increased in a map.Will this approach pass?
•  » » » » 3 years ago, # ^ |   0 Yea it should, mine did
 » 3 years ago, # |   -11 Auto comment: topic has been updated by amd (previous revision, new revision, compare).
 » 3 years ago, # |   0 Div 1 E: Heavy Light Decomposition?Find the minimum on each path and then set that node to Infinity?
•  » » 3 years ago, # ^ |   +44 Typing problem in Google gives HackerRank task with editorial available and codes being public as a first link :)
 » 3 years ago, # |   0 How can I avoid TLE in C? I made a program with matrix dynamic, So My program's time complexity is(KlogN) but It got TLE...
•  » » 3 years ago, # ^ |   0 The formula is 1 / 3 * (1 + ( - 1)k / 2k - 1). You just need to exponentiate 2^k modulo. Other computations are fast.
•  » » » 3 years ago, # ^ |   0 I got it. Matrix Computation was slower than I thought... Thanks!
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 Alternatively, you can note that it is sufficient to know the exponent for prime p, so you only need to do log(mod) exponentiation, instead of log(N). EDIT: 19131411
•  » » » » » 3 years ago, # ^ |   0 Hi, does that property works also for matrices? I mean if A is a square matrix and I the identity matris, then A^(MOD-1) = I mod MOD?
•  » » » » » » 3 years ago, # ^ |   0 Hmm, it seems I assumed it works during contest, and I have no proof or idea for proof. Will try to google around to find whether property is actually true.
•  » » » » » » » 3 years ago, # ^ |   0 I also assumed that, it worked. In yesterday's contest I tried to used in problem C but doesn't work. I already searched and that property doesn't apply for matrices. I would like to understand why in this particular problem it worked
•  » » » 3 years ago, # ^ |   +3 can you explain how to get such formula?
•  » » » » 3 years ago, # ^ |   0 Consider the matrix approach. The matrix is something like [[1 1 0][1 0 1][0 0 1]], and it equals to ([[1 1 1][1 1 1][1 1 1]]-I). Expand it.
 » 3 years ago, # |   0 Div2C test 3 and Div2B hack? ;(
•  » » 3 years ago, # ^ |   +1 Div2B 0.0e0
•  » » 3 years ago, # ^ |   +1 Div2B hack 0.0e0
•  » » 3 years ago, # ^ |   0 hack is 0.0e0
•  » » 3 years ago, # ^ |   0 The one I was hacked on in B is:2.0e0answer should be 2
 » 3 years ago, # |   +6 Kind of silly that a linear solution to Div2 A passes when such a nice O(1) solution exists.
•  » » 3 years ago, # ^ |   +17 Thats why it's Div2 A.
 » 3 years ago, # |   +2 Problem C: 5.0e0 hah. After an hour and before locking i realized my solution will fail such thing so fixed + submitted again. But then another guy in the room already did 11 hacks :| so couldn't make use of this to full extent
 » 3 years ago, # |   +6 I think pretest for problem B is very very not good :( :(
 » 3 years ago, # |   +38 I think Time Limit for Div1\C was too strict, at least my solution is O(k * log(a) * matrix_multiplication), which I thought was fine, but I need extra optimization to pass pretest. 19127740. I guess it will be TLE on final Test :(
 » 3 years ago, # |   0 I don't know why, but codeforces said that my input for a hack is invalid, however, it is valid, please check.
•  » » 3 years ago, # ^ |   +3 if a is zero b cannot be non-zero
•  » » » 3 years ago, # ^ |   0 i found the mistake, thanks.
 » 3 years ago, # |   0 Thank you for the quick editorial !
 » 3 years ago, # | ← Rev. 2 →   0 Sorry I am wondering what is wrong with these two solutions... Please tell me what is my mistake div2B 19118037 div2C 19132537Edit: i saw what i missed on div 2 b
•  » » 3 years ago, # ^ |   0 Compilation error maybe? :P
•  » » 3 years ago, # ^ |   0 Since you are using map, there needs to be a comparator function to compare its keys ie pair of bitset or bitset in this case. Apparently, there is no comparator function. Hence, the compilation error. You can either implement a comparator yourself and use it or change key of map to pair.Here is how to make comparator function: here (Although there is error in your logic as that gives WA)
 » 3 years ago, # |   +5 Dayum, first contest in div 1, problem A scared me, I thought I needed to do Lowest common ancestor, then I realized it was easy when 30 minutes remained. but I wrote v/x instead of v%x in my code, and realized 1 minute after contest ended :(
 » 3 years ago, # |   +26 I've always sucked at texting girls, so I didn't even bother with Div1D
 » 3 years ago, # | ← Rev. 6 →   0 Div 2. B: someone tried to overcome 0.0e0 hack: "for(; i < posE; i++){ sum += string[i] }; if(sum % 48 != 0){ print '.', ... }"; 0.888888e0 xD
 » 3 years ago, # |   +3 whats the idea in Div2 D ?? how in general to approach probability questions ??
•  » » 3 years ago, # ^ |   +6 Learn math ;)
•  » » 3 years ago, # ^ | ← Rev. 5 →   +8 There's no "general approach".But an important thing you should know is that expected value has linearity, i.e. you can add them directly. Then if you want to know the expected order of a node u, you can check how many nodes are visited before this node. There are 3 cases: u's ancestors: they are always visited before u u's decendants: they are always visited before u else: they are visited before u with probability 0.5 Then the answer is simply 0.5(n-u's decendants+u's ancestors+1).
 » 3 years ago, # |   0 You should improve pretest quality. It really weak this time.
•  » » 3 years ago, # ^ |   +17 Very strong pretests would make hacking much harder and an interesting feature of CF would be rendered useless. I assume, that in some cases problem setters might even avoid particular corner cases on purpose.
•  » » » 3 years ago, # ^ |   0 Well your right,But that '0.0e0' ruined my ranking!
•  » » » » 3 years ago, # ^ |   0 Same here
 » 3 years ago, # |   +3 tricky case in div2 B all digits are 0 including answer :)
 » 3 years ago, # | ← Rev. 3 →   +4 Couldn't hack Div.2 A C++ solutions with 0 2 1_000_000_000 :'(, only one Java.
•  » » 3 years ago, # ^ |   0 Same with me
 » 3 years ago, # |   0 Wasted an hour on precomputing for small values of n and trying to debug this whole thing in Div2 D only to find out that I have completely forgotten about the case when no additional subtrees are visited prior to entering the vertex.Managed to correct the solution, didn't manage to submit it in time. Damn.
 » 3 years ago, # |   +5 if (!prod) cout << 1/1;if (!prod) cout << 1/1;if (!prod) cout << 1/1;if (!prod) cout << 1/1;if (!prod) cout << 1/1;if (!prod) cout << 1/1;if (!prod) cout << 1/1;
 » 3 years ago, # |   +1 I tried to hack two solution on problem A_Div2 which use while loop with this test case :1 2 1000000000but I failed , I think it must give TLE on such solutions :\
•  » » 3 years ago, # ^ |   +19 10^9 simple iterations is easy for CF servers
•  » » » 3 years ago, # ^ |   0 If I've known this earlier, it could've saved me from getting WA53 with formula :p Thanks for the information.
 » 3 years ago, # |   0 This round's problems is so interesting! I like this round although i don't get many points
 » 3 years ago, # |   0 too much hacking in one round
 » 3 years ago, # |   0 Why so strict limits for div 1 B? I used double variables for answer and O(n) complexity and my solution runs in 750 ms(C++).
 » 3 years ago, # |   0 Ques 2nd should be rejudged. Your test cases don't contain 0.3e2. The solution 030 is also passed.
•  » » 3 years ago, # ^ |   +4 if the number before this decimal is zero, then the number after 'e' must be zero. Read the problem statement.
 » 3 years ago, # |   +11 The problem statement on Div1 B says "The second line contains n - 1 integers". This implies that there is a second line (just with 0 integers). Yet we are not given a blank second line. This is the only thing that broke my submission, isn't this test data invalid?
 » 3 years ago, # |   +34 The feeling when you have almost coded Div1F when the contest ends, and it would have passed the tests.
 » 3 years ago, # |   -10 Auto comment: topic has been updated by amd (previous revision, new revision, compare).
 » 3 years ago, # |   0 Can someone help me understand why my B gives TLE? it should be linear.Your text to link here...
•  » » 3 years ago, # ^ |   0 I found it.what I did was manually add for each node v, the sum S[w]+1 of the number of sons of each vertex w which is a son of the father F[v] which is not v.I should have just done S[F[v]]-S[v]-1. fail, sigh.
 » 3 years ago, # |   +8 WA on pretest 1 in Div2B. Any ideas?
•  » » 3 years ago, # ^ |   -14 Maybe it contains invisible characters.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +11 In your solution, line number #52.It should be "a < len". Why would you like to run till "a <= len"?Update:After correcting above mentioned error in your code, I was able to get AC on it. 19134004
•  » » 3 years ago, # ^ |   +9 You reminded me of this blog when I first started CP
•  » » 3 years ago, # ^ |   +15 After running your code locally, it has character with code 0 after the output but before the newline. 38 35 34 2E 39 00 0D 0A 
•  » » 3 years ago, # ^ | ← Rev. 4 →   0 Ehh... Thank you :/ I thought I would destroy my laptop after 10th submission :P I think that these types of invisible characters should be ingnored by the checker like it is done with "endl" at the end. It would be nice.
 » 3 years ago, # |   0 Any problem similar to div2D / div1B ?
 » 3 years ago, # | ← Rev. 2 →   +26 hey something is seriously wrong with the final testings.I submitted the same code again after the contest and it gives correct ans on on your system and my PC too.Please recheck it.You could even compare both codes.Problem "DIV2B"During Contest- http://codeforces.com/contest/697/submission/19126571After Contest- http://codeforces.com/contest/697/submission/19133631
•  » » 3 years ago, # ^ |   0 Yeah. You are right. Codes are same but output of 2 submissions are different. :/
•  » » 3 years ago, # ^ |   +3 Somebody answer this man ^
•  » » » 3 years ago, # ^ |   0 Ch is uninitialised, so atoi result might be wrong.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 .
 » 3 years ago, # |   0 Unlucky for me... If you use fermat little theorem on div2E... if you have a multiple of mod-1 then you cant let it stay at 0 to use formula... must say if (n==0) n=mod-1;
 » 3 years ago, # |   0 Why did I think that all strings are unique in div1D? :-(
 » 3 years ago, # |   0 Another one easiest way to drop 200 places! 19126039 19134075
•  » » 3 years ago, # ^ |   +5 Forget to write "if (y < 0) y += MOD — 1" and lost C.Thought that all strings are unique and wrote c[x] = a[i] instead of c[x] += a[i] and lost D. GGWP :D
 » 3 years ago, # |   0 For problem B when I run on my compiler it shows correct output but not on codeforces , why is this so ? Because of that I got wrong answer in B
 » 3 years ago, # |   +3 Really nice round, and a great problem set!
•  » » 3 years ago, # ^ |   -27 As always from amd :D
 » 3 years ago, # |   +106 Did anybody else find the problem statements, well, just "too much"?
•  » » 3 years ago, # ^ |   -31 I found it was kind of bitter sweet. I enjoyed the puns ("slapsgiving" in A was also nice). I also did not like that it took the focus out of the problem.BTW, isn't it the three eyed raven who has time traveling capabilities. Is Jon Snow the next three eyed raven? Can't wait for next season!
 » 3 years ago, # |   -6 How to fuck up your computer in three simple steps: Read Div2C/Div1A Assigns two huge vectors after seeing MAXU and MAXV Profit
 » 3 years ago, # |   0 I am new to python,and I wonder if there a way to read data like using freopen in cplusplus?if it has, need I delete the input code before I submit the code? Or it there if a way that I don't need to delete the input code like using ifdef definition in cplusplus?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 You can use sys.stdin.readline().strip() to read your lines. import sys sys.stdin = open('thing.in', 'r') # comment this out when submitting stuff = sys.stdin.readline() 
•  » » » 3 years ago, # ^ |   0 Thanks you XD I will have a try.
 » 3 years ago, # |   0 Hi can someone help me out why this solution for DIV II/Problem C is failing on testcase 39. I tried with lot of smaller test cases but couldn't figure out mistake.http://codeforces.com/contest/697/submission/19167786
•  » » 3 years ago, # ^ |   0 I can't solve your problem. But I want to put forward my idea about the problem. Each edge of a graph can be described as (u,u*2),(u,u*2+1). So we can use the larger node to record the cost of each road. http://codeforces.com/contest/697/submission/19431887
 » 3 years ago, # |   0 In A problem, why the input number 3 8 52 answer is "YES"??It is easy to work out 3+8*6 = 51[submission:20027674]