### GlebsHP's blog

By GlebsHP, history, 6 years ago,

Dear friends!

We are glad to invite you to take part in Codeforces Round #363, featuring some problems of the VK Cup 2016 Final Round that took place in Saint Petersburg at the beginning of July. The second part of the problemset will be used to conduct Codeforces Round #364. Of course, we made some new problems to complete the set to fulfill the requirements of the regular round and it now contains problems of the appropriate difficulty for participants of any color.

We will obey the good old tradition to publish the scoring distribution right before the start of the competition.

We wish you good luck and an interesting contest!

UPD1. Scoring distribution will be standard in both divisions 500-1000-1500-2000-2500-3000 (yes, there will be six problems featured in both div1 and div2).

UPD2. Problems were prepared for you by MikeMirzayanov, Errichto, fcspartakm, qwerty787788 and Radewoosh.

UPD3. System testing is over, congratulations to winners!

Div. 1:

Div. 2:

UPD4. Analysis is almost here

• +444

 » 6 years ago, # | ← Rev. 2 →   -174 You are a bit of shit:D
•  » » 6 years ago, # ^ |   -162 second comment :D
•  » » » 6 years ago, # ^ |   -158 third comment :D
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -67 Check the first comment:D
•  » » » » » 6 years ago, # ^ | ← Rev. 4 →   +37 What gets upvoted and downvoted in CodeForces, as usual, is beyond prediction... (screenshot in case the upvotes/downvotes change)
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   -67 check the first comment:D
•  » » » » » » » 6 years ago, # ^ |   -35 Since it's continuing on getting downvotes, it can show that the assumption from here http://codeforces.com/blog/entry/46077 is certainly correct :D Have fun,codeforces!
 » 6 years ago, # |   -11 Very inconvenient time.
•  » » 6 years ago, # ^ |   +12 As my college has started now i have to wake up early and get ready for the class and late Codeforces round make my routine little bit hactic...Thank you so much GlepsHP for choosing such a nice time for the contest.. Hoping to gear some of my rating points and wish everyone a high rating :)
 » 6 years ago, # | ← Rev. 2 →   -70 another good old tradition, thank someone
 » 6 years ago, # | ← Rev. 2 →   -10 The way the TooDifficult has been improved with past rounds , one day sure he may defeat even Petr and tourist . Waiting to see that happen.
•  » » 6 years ago, # ^ |   +37 Wow!! You made all three of them Headquarters. Mike has got competitions
•  » » » 6 years ago, # ^ |   +12 I still don't get it. Why is his title "Headquarters" ?
•  » » » » 6 years ago, # ^ |   -37 Because he's in the Headquarters of Codeforces
•  » » » » » 6 years ago, # ^ |   +5 .
•  » » » » 6 years ago, # ^ |   -26 So that people don't compare themselves to him.Also, he's the fucking admin so he can do whatever he wishes. Hell, he can define his rating as touristsrating + 1 if he pleases.
 » 6 years ago, # |   +59 Yesterday I thought I'll be able to participate in two CF rounds this week... Ouch :)Can you add part about VK Cup to the contest registration message as well?
•  » » 6 years ago, # ^ |   +138 Want another Christmas tree?
•  » » » 6 years ago, # ^ |   +30 What do you think dreamoon_love_AA is trying to paint, sir?
•  » » » » 6 years ago, # ^ | ← Rev. 16 →   +46 Maybe he is a mountaineer?
•  » » » » » 6 years ago, # ^ |   +13 I'm the mountaineer
•  » » » » » » 6 years ago, # ^ |   +6 Yours is more like two-hump camel now :)
•  » » » » » » » 6 years ago, # ^ |   +8 I...I thought they were boobs at first.
•  » » » 6 years ago, # ^ |   +6 tweety himself was producing a very nice sine curve, but he just had to break it :v
 » 6 years ago, # |   +12 SRM 695 ends just 5 minutes before the CF contest.
•  » » 6 years ago, # ^ |   +35 How so, by my calculations it ends 30 minutes before the CF contest? As TC contests are 1hr35min, not a full 2 hours right?
•  » » » 6 years ago, # ^ |   0 Oh yes! You are right! I don't know why the Coder Calendar chrome extension shows that duration is 2h. :P
 » 6 years ago, # |   0 Wait but doesn't that mean that the contest isn't going to be rated?
•  » » 6 years ago, # ^ |   +146 "we made some new problems to complete the set to fulfill the requirements of the regular round""the requirements of the regular round""regular round"(there, tried to make that as dramatic as possible)
•  » » » 6 years ago, # ^ |   +62 Good attempt, but make a picture next time :P
•  » » » 6 years ago, # ^ |   +13 triggered *
 » 6 years ago, # |   -17 At first I was very happy about the upcoming round.Then I noticed the starting time....why 16:05 and not 19:35 as always?
•  » » 6 years ago, # ^ |   +8 However, a Chinese is cheering for that. :P
 » 6 years ago, # |   +46 Palindrome Contest "363" :)
 » 6 years ago, # |   +20 Thank you for changing the start time! The usual 16:35 UTC is in the middle of work for me and I feel guilty doing CF at work :)
 » 6 years ago, # | ← Rev. 3 →   +3 Who are the problemsetters of the round?UPD: thanks for adding them into the main post.
 » 6 years ago, # |   +26 I think you forgot about saying this "..I want to thank Mike for legendary platforms of Codeforces and Polygon. " :D ;
 » 6 years ago, # | ← Rev. 2 →   -16 it will be a PALINDROME contest in this month 363 :v
 » 6 years ago, # |   -35 Many user will miss this contest for unusual time
•  » » 6 years ago, # ^ |   +125 Come on, do you think users don't miss contests at the regular time?I haven't done a contest since 351. It's not because I didn't want to, it's because almost every contest is at 2:35am here.So yes, I'm a little bit salty that some people get almost all competitions at a decent time and then start complaining as soon as one competition is at a different time.(btw nothing personal to you, I just didn't know which comment to reply to so I just chose one)
•  » » » 6 years ago, # ^ |   0 Hey it's even worse (4:35am) here in New Zealand ok.
•  » » » 6 years ago, # ^ |   +19 Actually I tried to say that regular codeforces round always starts at a common time. For this reason some user never check the time.
 » 6 years ago, # | ← Rev. 3 →   -28 :)
 » 6 years ago, # |   +44 Very convenient time.
 » 6 years ago, # |   +11 Feels good to have an early contest. :D
 » 6 years ago, # |   +22 The starting time is very good for those living in Eastern Asia, since most of the CF rounds ends at 2 AM for us. I'm really happy.
 » 6 years ago, # | ← Rev. 2 →   -6 Wow,what a special time! It's very good for us.We dont't have to stay up late for the contest. :)
 » 6 years ago, # | ← Rev. 2 →   +65 CF can consider arranging contests at different times regularly I think. It's a big community from all over the world and definitely some times are completely impossible for some people. I am in a time zone where usual time is at 9/10 PM and this contest will be at 7pm. Very much convenient for me but this is not the case for all.
 » 6 years ago, # |   -13 Но могут ли участники "VK Cup 2016 Final Round" участвовать ??!!
•  » » 6 years ago, # ^ |   +32 Sure, no.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +18 your question is equal to !("is it rated?").
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +6 No, it's equal to is it unrated.
•  » » » » 6 years ago, # ^ |   +5 !("is it rated") == ("is it unrated")
•  » » » » » 6 years ago, # ^ |   -15 Do you mean !("is it rated") == ("is it unrated")== true == true == ....
•  » » » » » » 6 years ago, # ^ |   0 No, I guess as Mike is saying the round is rated
•  » » » » » 6 years ago, # ^ |   0 Good revision saved yourself from an wrong answer. :D
•  » » » 6 years ago, # ^ |   +25 Are you banned on GoogleTranslate?
 » 6 years ago, # |   -13 Dont know if it is true or not, but if some problems are from vk cup 2016, then it is possible that some of us already know some of the problems!
•  » » 6 years ago, # ^ |   +13 The participants of final round cannot participate in this round.
•  » » » 6 years ago, # ^ |   +11 And the problems of the final round were not disclosed?
 » 6 years ago, # |   +1 Does this contest contain original problems of VK Cup 2016 Final Round or easier version of them?
 » 6 years ago, # |   -29 for the sake of tradition, is it rated?
 » 6 years ago, # |   0 i hope the problems will be short like this entry
 » 6 years ago, # |   0 This VC Cup 2016 Final Round problems will be only at div1 problemset or only at div2 problemset or both :/
 » 6 years ago, # | ← Rev. 2 →   +34 More and more comments like " oohh .. good time " ; " bad .. bad time "...))) Despite of fixed time for constest , it be always inconveniently for part of us , but convenient for other, or it is not clearly? :D ... The earth is round and here are contestants from each part of earth , it's impossible to set a good time for all.
•  » » 6 years ago, # ^ |   +2 There aren't many competitors living in the middle of the Pacific Ocean. (And those that do aren't able to code during the day.)
 » 6 years ago, # |   0 interested in participating in this Contest :))
 » 6 years ago, # |   +6 This Time i will be in top 10.
•  » » 6 years ago, # ^ |   +74 of your room ?
•  » » » 6 years ago, # ^ |   0 No......overall
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +6 Counting from the last ? :D p.s No offence !! Wish you to be first in TOP.
•  » » 6 years ago, # ^ |   0 It was my turn XD
 » 6 years ago, # |   +17 So excited to participate in a Div.1 round after a while.P.S: tourist is not participating, so it could be the one(if Petr participates)!
•  » » 6 years ago, # ^ |   -13 How do u know tourist won't participate?
•  » » » 6 years ago, # ^ |   +26 He just asked his astrologer
•  » » » 6 years ago, # ^ |   +25 The participants of final round cannot participate in this round.
 » 6 years ago, # |   -6 Rated or not?
 » 6 years ago, # |   +12 No matter what the starting time is, The servers will be slow and by the time I'm able to see problem A 100 people would get AC already, as usual. :P
 » 6 years ago, # |   +4 As a Chinese student, late Codeforces round make my routine little bit hactic...Thank U so much for choosing such a nice time for the contest.. Hoping to gear some of my rating points and wish everyone a high rating~~ :)
•  » » 6 years ago, # ^ |   +4 666
•  » » » 6 years ago, # ^ |   0 77777
 » 6 years ago, # |   0 How can i register ? It shows extra registration has time left, but how to register ?
 » 6 years ago, # |   0 Thanks
 » 6 years ago, # | ← Rev. 2 →   +6 What is pretest 5(Div2D)?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +3 I got past it when I fixed the case42 3 4 2Answer should be:12 3 4 4so maybe it was something similar to that. Then I got stuck on case 8 :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 some thing like it32 1 3answer is13 1 3 or 2 3 3
 » 6 years ago, # |   +2 I solved problem A and B very quickly, but failed C for the rest of the contest. Anyone know what test case 6 for C is?
•  » » 6 years ago, # ^ |   0 I think it is 3 1 1 1
•  » » » 6 years ago, # ^ |   0 Mine gives answer 1 on this but fails Test case 6.
•  » » » 6 years ago, # ^ |   -15 The answer is 1, Wright? (Ahahaha) (People who didn't understand the joke: don't downvote, okay?)
 » 6 years ago, # | ← Rev. 2 →   +36 Will Petr overtake tourist today? He's in rank 1 of the standings !!! If it happens, it will be after long time (does someone has the data) for someone else to take 1 in overall rankings.EDIT : He does it infact. :D Glad to see him at the top here.
 » 6 years ago, # |   0 Does anyone know the hack for Div 2 B?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 4 4 ...* .... .... *... Also 500 * 500 star grid for tle test.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Answer should be yes (1,1), correct?
•  » » » » 6 years ago, # ^ |   0 Yes.
•  » » » » 6 years ago, # ^ |   +1 Or YES (4,4)
•  » » 6 years ago, # ^ | ← Rev. 6 →   0 2 cases: 5 5 ..*.. ..*.. **.** ..*.. ..*.. Answer: YES 3 3 3 3 ... ... ... Answer: YES 1 1 (or any other valid position on table)
•  » » » 6 years ago, # ^ |   0 1st one should be:YES 3 3and 2nd one should be:YES 1 1right? Or should the second one be No cause there are already no bombs so you can't destroy all bombs?
•  » » » » 6 years ago, # ^ |   +1 The answer for 2nd one is Yes (we can put the bomb in any position). My solution will fail this kind of test :(
•  » » » » » 6 years ago, # ^ |   +1 :( That test case had me worrying the entire contest.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +1 A cool one: 3 3 .*. *.* .*. 
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 3 3 .*. *.. .*. 
 » 6 years ago, # |   0 I am not really sure why I am getting memory limit exceeded for Div2D. Can anyone explain?
•  » » 6 years ago, # ^ |   0 Seems to me you getRoot(i) can not deal with the situation when cur is a "tail" to a loop. For example: 1 -> 2 -> 3 -> 4 -> 2 if you call getRoot(1), "start" will be set to 1, but you will never reach 1 again.The best way to deal with this (as I read somewhere on this site before), is to have two pointers, say l and r, l goes one step each time while r goes two steps each time. If r==l for some timestep, it is a loop.
•  » » » 6 years ago, # ^ |   0 Oops , that should be it, thanks! should have simply used a visited array. But with the MLE I was thinking in the opposite direction :/
 » 6 years ago, # | ← Rev. 5 →   +9 Why this O(n²) solution http://codeforces.com/contest/699/submission/19241016 didn't exceeded the time limit? My hack attempt failed :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 ignore.
•  » » 6 years ago, # ^ |   +20 Maybe compiler threw away for with j during optimization, since it is never used.
 » 6 years ago, # |   +3 How to solve Div1-B correctly?
•  » » 6 years ago, # ^ |   0 I managed to pass pretest with union find — disjoint set.... but I think there may be some corner cases that I haven't handled
•  » » 6 years ago, # ^ | ← Rev. 3 →   +5 this is how my solution work : iterate ocer all i : 1 -> n et for each i , if it isn' t marked " visited " , you use a recursion to search for his lowest unvisited ancestor : if you find a cycle in the tree ( same method as searching for cycles using dfs ) , you push its root ( highest parent ) into a vector v containing root of different connected componnents .... after iterating over all i , you sort v such that for i < j , cyc [ v [ i ] ] <= cyc [ v [ j ] ] to make sure that you make less changes and you consider v [ 0 ] as the root of the only new tree ...sorry for my bad english link : http://codeforces.com/contest/699/submission/19261372
•  » » 6 years ago, # ^ |   +8 Good day to you, here's my approach:A) Try to find "ANY" root (node which points too itself)B) Re-edge all other roots to itC) Do cycle-finding dfs (Open+Closed states) from all nodes (going to parents). If a cycle is found, re-edge ANY node which is in the cycle to "chosen" root.If none root chosen in "A", then promote the first one found in "C" as "chosen root".Here is link to solution (anyway not self-documenting :'( )Don't hesitate do discuss more of it, if not understood anything or if you have doubts :)Complexity O(N)Good Luck & Have Fun ^_^
•  » » » 6 years ago, # ^ |   0 I was thinking again, and you can avoid step "B", if you forbid visiting "chosen root" in dfs (because in "C", the self loops will do the "B" step automatically — silly me)New (but almost same) code.GL & sorry for the inconvenience ^_^
•  » » 6 years ago, # ^ |   0 I think it only have two case like number 6 (loop) and 1 (or a point) :)) :)) The first line ans is total tree — 1 (if have at least 1 tree like number 1) or total tree (if all tree like number 6)
 » 6 years ago, # |   +9 I guess that we will have an another unlovely system testing with a lot of wrong answers on main tests.
 » 6 years ago, # |   0 How long do system tests take on CodeForces?
 » 6 years ago, # |   +3 Div 1 C — DP with matrices?
•  » » 6 years ago, # ^ |   +24 Nope :DSince the operations are completely independent, try making them in reverse. Now question is "what is the probability that i is among the first k videos accessed in the first 10^100 hits?"But it is extremely likely that you will access at least k videos before you do that many hits, so you can simply ignore the last part and answer "what is the probability that i is among the first k videos accessed?"
•  » » » 6 years ago, # ^ |   0 Well.. This seems easy. But what then? I got stuck on writing DP in less than O(2^n * n^2)...
•  » » » » 6 years ago, # ^ |   +13 Well, you only care about the current set of "activated" videos and the next video you add, O(2n * n). But I think O(2n * n2), whatever the idea is, could theoretically also pass TL...
•  » » » » » 6 years ago, # ^ |   0 2^n*n^2 is 4*10^8 so if the constant factor is large it will fail. In this problem we need double computation so it is not surprising if it fails.
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 We had O(n2·2n) during the original contest and it passed
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Ignore.
•  » » » 6 years ago, # ^ |   +5 What do you mean by making operations in reverse? Could you elaborate? It seems to me that processing request in reverse is a totally different game.
•  » » » » 6 years ago, # ^ |   +8 Well,the fact that moves are independent of each other helps much. Don't take into account the LRU game,the problem reduces to the last k different videos in the end. Take it this way: I want to know which are the last k videos <=> I want to know which are the first k videos looking from the end. BUT the moves are independent,so the probability of choices x1,x2,..,xn with fixed y1,y2,...,yk at the end is the same as the reversed one with fixed y1,y2,...,yk in the beginning.You can also see it as a bijection,pointing a sequence to the reversed one. If video i is in the last k videos of a sequence,it is surely in the first of the reversed one. So the answer for video i will be calculated correctly.Making the reverse problem may not seem different,but it is much easier. There is no game to apply now,as we calculate the answer for bit masks with at most k 1 bits. So no need to remember the order of videos ,which was a pain.
 » 6 years ago, # |   +1 How to solve Div 2 D ? My approach was to count total components and number of such components which are cyclic among them. If all components are cyclic then answer is No. of components and then we can assign root to any vertex and then print parents accordingly. Now, if at least one component is non-cyclic then answer is No. of components-1 and main root can be assigned to the any vertex which is root in its corresponding non-cyclic component. But it fails on pretest 5. Any hints where I should think more ?
•  » » 6 years ago, # ^ |   +1 I followed exactly your method and managed to pass pretests. Must be some small bug in your code. And I think my solution may also fail in main test. I can't shake off the feeling I missed some corner case :/
•  » » 6 years ago, # ^ | ← Rev. 9 →   +3 You forgot about jellyfishes ( cycles with "legs" attached to various nodes on a cycle). You can't assign root to any vertex. It has to be a vertex belonging to the cycle. For example in this graph below you can't set 3 as root. 3 2 1 1 
 » 6 years ago, # | ← Rev. 2 →   0 I think it is better if an example about how LRU algorithm works couble be added on the Note part of problem LRU.Just discribing it by works is a little bit ... confusing. Like this : We have 4 videos and 3 caches the queries are {4,3,4,2,3,1,4} at first the caches are 0,0,0 ask 4,then become 4,0,0 ask 3,then become 3,4,0 ask 4,then become 4,3,0 ask 2,then become 2,4,3 ask 3,then become 3,2,4 ask 1,then become 1,3,2 ask 4,then become 4,1,3
 » 6 years ago, # | ← Rev. 4 →   -37 In todays contest, Div 2D/1B considered only sample 1 as non penalising pretest, which is slightly unexpected and odd. I think such cases should be mentioned in the Problem Statement(I got -1 due to this). It was also slightly confusing as I thought it wasn't same as Sample 3 and something else instead.UPD: Sorry, my bad. I always thought all samples were non penalising. I'm not sure why they wouldn't be? Is there a good reason behind this?
•  » » 6 years ago, # ^ |   +11 The only time that you don't receive a penalty for a problem is on Test Case 1 (whether it be Compile Error, Wrong Answer, Time Limit Exceeded, etc.). Even if Test Case 2 is a sample and you get it wrong, it will count against you.
•  » » 6 years ago, # ^ |   +32 In all problems and all rounds only sample 1 is nonpenalising.It says that somewhere in the rules, which you confirmed to have read when you registered for the round, so you must know them by heart, right?
•  » » » 6 years ago, # ^ |   +17 Had he known the rules, this wouldn't have happened.
 » 6 years ago, # |   +3 What is N equal to in Div2A test8?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +3 Same here. I got WA at 2A test 8 and 2B test 53. It's weird.
 » 6 years ago, # |   -24 I will be BACK
 » 6 years ago, # |   0 BLUE?
•  » » 6 years ago, # ^ |   +6 Purple?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Yeaaaah! Grats to your purple. Switching to C++ has made me more powerful (see my new pic)! No more random time outs like with Python.So close to solve Div2 F... but close is not solved (unless you are at Hackerrank where you sometimes get 72 out of 80 with brute-force)
 » 6 years ago, # | ← Rev. 2 →   +76 semiexp and I think the testcase of F is weak.In our solution, We check only the map is surjective, not injective. Our solution get WA on the case N=14, p[5]=7, p[14]=14, and others are zero. The answer should be zero but our solution outputs some positive value.
•  » » 6 years ago, # ^ |   +17 It's my fault, I'm very sorry for that. I will add this exact test today, for upsolving. The already accepted submissions won't be rejudged (of course). If you have some more thoughts about this problem (any particular big tests that should be added?), please write PM to me. Thanks for sharing.
 » 6 years ago, # |   -6 That moment when you are thinking too much to find an optimized solution, and your head become so 'still' that it does not come across the simple solutions 'dancing around it'. ;)PS: I was referring to Div2 A, B, C.
 » 6 years ago, # |   0 That moment when you have to switch to windows to hack, because your ubuntu doesn't have adobe flash player >_>
 » 6 years ago, # |   +4 Isn't it a bit strange the N<100 for Div2C. I kept on thinking that my solution (which is correct) must be wrong because the time constraints can't possibly be so lenient. :(
 » 6 years ago, # |   +101 Petr > tourist!!!!!
 » 6 years ago, # |   +4 My solution for D failed for a really minor bug, such a weak pretests :(P.S: Was backtracking intended? Mine got AC in practice.
 » 6 years ago, # |   +73 Finally Petr Beats tourist
 » 6 years ago, # |   +13 Now Petr Top Rated 3597.
 » 6 years ago, # |   +35 Petr got rating 3597 now! It's rank 1!
 » 6 years ago, # |   +28 So tourist has to settle for second on CF even after winning the official VK Cup Finals. #JustTouristThings
•  » » 6 years ago, # ^ |   +8
 » 6 years ago, # |   +14 Can someone please help me. The output is correct but it says the formats mismatch. submission for div2-B
•  » » 6 years ago, # ^ |   +8 I believe that is caused by the extra space at the end.
•  » » » 6 years ago, # ^ |   +5 Oh! But it never was there in other problems right? Dunno why is it called "format" then..
•  » » » 6 years ago, # ^ |   +5 Thanks man! It indeed was the problem. Corrected solution worked.I always thought the judge is lenient about "\n" and " ". But I did learn my lesson with 1 hr of contest time. Should be careful in the future.
•  » » » » 6 years ago, # ^ |   +11 This shouldn't have happened. :( Judge should usually ignore trailing white-spaces.
•  » » » » » 6 years ago, # ^ |   0 Is it possible to tag some admin to see this post so that they notice this and it doesn't happen to anyone in the future? 1 hr of contest time is significant...
•  » » » » » » 6 years ago, # ^ |   +3 I don't know actually if this will work or not:MikeMirzayanov, can you please look into this matter?And desikachariar, you may write a blog entry explaining what happened.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Whether format about whitespaces matter depends on the checker of the problem. It's obvious that for this problem, the author needs to write a checker by himself.(The checker cannot just compare tokens like yes/no, integers or floating point numbers) And it tends to has less tolerance about wrong formatting.
 » 6 years ago, # |   +70 It is MiracleFaFa when you Top3 but still fell in rating..
 » 6 years ago, # |   +30 So.... What is test 107 in problem D, i can't seem to have any idea why i am giving wrong answer
•  » » 6 years ago, # ^ | ← Rev. 2 →   +59 Here is a shorter test, your answer is 25 but it is possible to get all 26: test4 26 0 0 6 6 12 6 9 9 6 0 6 1 6 2 6 3 6 4 6 5 12 0 12 1 12 2 12 3 12 4 12 5 18 0 17 1 16 2 15 3 14 4 13 5 16 1 14 2 8 5 7 3 8 6 11 3 10 6 9 3 The idea is that you have to first kill (9, 3), then it opens paths to both (6, 0) and (12, 0), and finally, you can get to (18, 0).
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Thank you very much for the test!
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 To make (18, 0) safe, add something like (9, 4), right above the center monster. There will be 27 monsters, but only 26 will be endangered. (This is an answer to rev.1 of the comment.)
•  » » » » » 6 years ago, # ^ |   0 Thank you very much! Both test cases work well with my solution, but I still get WA on test 5.
•  » » » » » » 6 years ago, # ^ |   0 Consider this example, where the last monster (5, 0) is unreachable: 2 3 1 0 3 0 2 0 4 0 5 0
•  » » » » » » » 6 years ago, # ^ |   0 Thank you! This test works too.
 » 6 years ago, # |   +35 when will be editoral?
 » 6 years ago, # |   0 Can someone explain me the dp solution for the Div2-C/Div1-A ?
•  » » 6 years ago, # ^ |   +7 dp[i][0] :- Represents answer when you choose gymming on ith day. dp[i][1] :- Represents answer when you choose contest on ith day. dp[i][2] :- Represents answer when you choose to rest on ith day. Clearly, dp[i][0] = min(dp[i+1][1], dp[i+1][2]) dp[i][1] = min(dp[i+1][0], dp[i+1][2]) dp[i][0] = min(dp[i+1][0], dp[i+1][2], dp[i+1][1]) + 1Do this for all i b/w n-1 and 0. Finally answer is min(dp[0][0], dp[0][1], dp[0][2]) http://codeforces.com/contest/699/submission/19242139
•  » » » 6 years ago, # ^ |   0 Thanks.
 » 6 years ago, # |   +74 Petr _/_ won SRM,won CF round same day!
 » 6 years ago, # |   0 After seeing nice codeforces round problems eager to see nice editorial soon to learn from my mistakes. PLEASE upload it quickly can't wait more.I think other people are waiting too :)
 » 6 years ago, # |   +27 Congratulations to Petr for becoming the highest rated person at the codeforces site. <3
 » 6 years ago, # |   0 Gosh, forget to set a good value of maximum in Div.2 Problem A gets me a WA.My ratings...
 » 6 years ago, # | ← Rev. 2 →   0 Can Div2 D / Div1 B be solved using Disjoint Sets?Could you please tell me how it is solved?Thanks
•  » » 6 years ago, # ^ |   +6 First find out that there can be any root of the given tree(if any make ans = -1 otherwise 0)ans = -1 is for when you have p[i] == i case , the root of the tree.For every i , check whether (i,p[i]) are from the same set , if it is then make the parent of i as root(if any or create this i as root ) and increment ans each time when you find they are from same set.Here is my code : 19259242
 » 6 years ago, # |   +31 E was such a beautiful task <333
•  » » 6 years ago, # ^ |   +15 Are you kidding? :D
•  » » 6 years ago, # ^ |   +10 I'm surprised I was the only one who used Python's builtin time libraries :P
 » 6 years ago, # |   0 In B problem (Div 2) for test case:2 2 .* *.My answer is: YES 2 2But the system said: NOWhy my answer is wrong?
•  » » 6 years ago, # ^ |   +1 You are mistaken.The case is that your answer is NOWhile the right answer is :YES2 2
 » 6 years ago, # |   0 Still wondering why my code fails for test #45 of Div2 B. The report says "There is an obstacle after the bang". Can someone give a simple testcase that breaks my code? 19245284
•  » » 6 years ago, # ^ |   0 There are still a wall left after the bomb placed. E.g. 4 4 **.. .... .... .*.. give answer 4,2 and wall at 1,1 still survive. It should be placed at 1,2
•  » » » 6 years ago, # ^ |   0 Oh, thank you very much. Better luck to me next time.
 » 6 years ago, # | ← Rev. 2 →   +107 Thanks everybody for participating, especially all those guys who were so glad to let me into top-10 without participating in a contest :)
 » 6 years ago, # |   0 it was century contest for Petr :D congretulations !
 » 6 years ago, # |   0 Till when the editorials will be published?
 » 6 years ago, # |   +1 Div2 D, 19261965 Where did I go wrong? This test case has 0 roots. Can someone please help?
•  » » 6 years ago, # ^ |   +1 Good day to you,I'm not sure, whether this will help you, but here's a more simple TC, which it might fail:Input: 4 2 1 4 3 Your output: 2 2 2 4 3 Well it seems you counted "2" changes but made only one (2 is correct but well... :))Good Luck!
•  » » » 6 years ago, # ^ |   +5 Thanks for the test case! 19278465
 » 6 years ago, # |   +6 we need one more nice tradition: to announce when editorial will be published can't sleep without editorial :( awhhhhhhhhhhh sorry for my impatience
 » 6 years ago, # |   -19 Finally the legander of tourist had destroyed. petr became the first in codeforces
 » 6 years ago, # |   0 I think copied code not only skipped your submission. I think should subtract rating of copier code. (sorry my bad EL)
 » 6 years ago, # |   +29 Why does it seem that Petr has improved dramatically recently based on CF rating, while tourist seems to be plateauing a bit relatively? It is a bit surprising given that Petr is older, and one would expect greater improvements in younger contestants. Of course I guess question could be a bit meaningless given variance in contests.
 » 6 years ago, # | ← Rev. 5 →   0 Hello people, Can you give me a code, which shows my mistake in Problem 2, Division 2: http://pastebin.com/HsG1G5YVThe test that breaks it does not show fully.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I just brute forced Div2 B. Store how many walls are on each row and column at each x and y, then iterate through each pair of x and y. If the amount of walls on the row of y and column of x (I use y for 'i' and x for 'j') subtracted by the overlap wall in the intersection of the row and column (if there exists one) equals the total amount of walls, then you know that pair of x and y is a viable place to put the bomb. If you don't find a working pair then output "NO".19242096Hope this helped. :)
•  » » » 6 years ago, # ^ |   0 Thanks, plenty of good solution out there, but I am just interested in why my solution fails. Unfortunately, the test on which it fails is too long and codeforces have not written it at whole. Thus, I can only guess.
•  » » » » 6 years ago, # ^ |   0 Your welcome! There is a large variety of good solutions to learn from out there. As for your solution, I can't read C# so I'm not exactly sure what you are trying to do. Hopefully you figure it out. Debug will help out a lot too :)
 » 6 years ago, # |   0 Can anyone please tell me how to solve div2 D?
•  » » 6 years ago, # ^ |   0 Let us make the graph from the sequence given in problem. You can make diagrams and see that in any component there can be at most one cycle, I don't have a proof. Now for all components, when you get a cycle, just direct any edge of it towards any root(that is present in a component without a cycle). If all components have a cycle, just take any component and make any node on that cycle as root, and do the above things.
•  » » » 6 years ago, # ^ |   0 The proof is simple. If a component is tree it would consist of n — 1 edge. So the maximum wrong edge in the component is only one.
 » 6 years ago, # |   -13 So...Since I started programming, tourist was always on the top. But now something is different!
 » 6 years ago, # |   +16 Waiting for Round 364 :)
 » 6 years ago, # |   +32 Congratulations on semiexp for becoming IGM in only 7 rounds!I guess that is the fewest number of participation on becoming IGM in CF history!!
 » 6 years ago, # | ← Rev. 2 →   0 Hi, can the admins/moderator please link this editorial to the contest page? Thanks.
 » 6 years ago, # | ← Rev. 2 →   0 Can I solve problem D by choosing the root ( any vertex such that (p[i] == i) ) , and choose any vertex from each Cycle in the graph and merge it with the root ? . Thank you in advance :D
•  » » 6 years ago, # ^ |   0 Yes , but not when there is no i such that p[i]==i. In that case, you need to pick root as one of the vertex forming a cycle.