### IlyaLos's blog

By IlyaLos, 3 years ago, translation, ,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #346 (Div. 2). It'll be held on Wednesday, March 30 at 16:05 (UTC) and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time! Also, the round itself will be unusual: there will be 7 problems for two and a half hours.

Me (IlyaLos), Edvard Davtyan (Edvard), Dan Sagunov (dans), Roman Glazov (luigi_vampa) and Vladimir Petrov (P1kachu) prepared the tasks for this Round. Great thanks to Gleb Evstropov (GlebsHP) for helping us preparing the contest, to Maria Belova (Delinur) for translating the statements into English and to Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform, for helping on preparing the contest and for ideas for some tasks.

The scoring distribution will be announced later. Good luck everyone!

UPD Score distribution: 500-1000-1000-1250-1500-2000-2500

UPD2 Competition completed! Thank you all! Editorial

• +274

 » 3 years ago, # |   +11 Expecting a good round :)
•  » » 3 years ago, # ^ |   +11 all newbie people need that :'(
 » 3 years ago, # |   +59 A regular Codeforces round after a long time :).
•  » » 3 years ago, # ^ |   +5 Well, sort of regular.
•  » » 3 years ago, # ^ |   0 yooo :D
•  » » 3 years ago, # ^ |   0 A usual round at unusual time!
•  » » » 3 years ago, # ^ |   0 that is more than right. it will beign at 00：05 in BeiJing and there are leasons tomorrow !
 » 3 years ago, # |   +74 Just learnt coding about two weeks ago and this is my first round. Wish me luck!
•  » » 3 years ago, # ^ |   -57 For someone like you I don't think you need luck
•  » » » 3 years ago, # ^ |   +23 non egyptians will not understand xD
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 Great way to learn. Best of luck.
•  » » 3 years ago, # ^ |   -8 9 months ago I was in your position, and now I'm here (further than I expected). Good luck!
•  » » » 3 years ago, # ^ |   +1 I started 6 months ago and still a pupil, any advice?
•  » » » » 3 years ago, # ^ |   +1 maybe this topic can help you: http://codeforces.com/blog/entry/17842
•  » » » 3 years ago, # ^ |   -15 This contest has rating or doesn't it?
•  » » » » 3 years ago, # ^ |   +19 Not again the same question.... Tired of same question everytime
•  » » 3 years ago, # ^ |   +6 k0sk
•  » » 3 years ago, # ^ |   +9 That's my boy, well done. Dude, wish me luck next contest.
•  » » 3 years ago, # ^ |   +5 i think that is fake xD
•  » » » 3 years ago, # ^ |   -6 You never know! XD Maybe he's a natural genius so he managed to come third after 2 weeks of coding! XD
•  » » 3 years ago, # ^ |   0 Thanks for your support everyone. :) ♥
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +12 Why create fake and then leave them ? It is obvious that if you learnt coding two weeks ago you wouldn't be able to solve G...
•  » » » » 3 years ago, # ^ |   +39 He's very smart. Smarter than everyone. I think he's even on par with Kim Jong Un.
•  » » 3 years ago, # ^ |   0 What the hell, man!
•  » » 3 years ago, # ^ |   +7 When will you bring your army to take tourist's rating?
•  » » 3 years ago, # ^ | ← Rev. 2 →   -39 جرا ايه يا عرص؟ طلعت ال٦٧ يا حيلتها؟ ما تجيب جيشك وتيجي تنفخهم
•  » » » 3 years ago, # ^ |   -38 بالراحة علي الواد يا حوس حوس، لسه بيتعلم
•  » » » 3 years ago, # ^ |   -38 اسفين يا ريس، المرة الجاية هعمل معاهم الصحبالمناسبة، انا عملت الحساب ده عشان الناس عارفاني اكتر بالاسم ده
•  » » » 3 years ago, # ^ |   -38 طلعني من السجن بس وانا هنفخك الكونتست الجاية يا عرص
•  » » » 3 years ago, # ^ |   -39 عند امه يا ادهم
•  » » » 3 years ago, # ^ |   -39 يا ريس انا اخترعت جهاز يخليك تطلع الاول علي الكونتست من غير ما تكتب ولا سطر كود
•  » » » 3 years ago, # ^ |   -38 يلا ياد روح العب بعيد، الحاجات دي انا اللي بخترعها
•  » » » » 3 years ago, # ^ |   0 Ok seriously cut it out.
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   +12 Hope to advance to Div1 this time!
•  » » 3 years ago, # ^ |   +4 Best of luck :)
•  » » » 3 years ago, # ^ |   +9 Thank you mate. I made it! :p
•  » » » » 3 years ago, # ^ |   +3 Great ... congratulation :)
 » 3 years ago, # |   +39 Just wondering : If there are 7 problems then why not make a Div.1 Round too?
•  » » 3 years ago, # ^ |   -48 No, because tourist now has a 4000+ of rating. I respect that!
•  » » » 3 years ago, # ^ |   +12 tourist's rating won't decrease if they make a Div 1 round :P
•  » » 3 years ago, # ^ |   +10 Kinda related, I wonder if it would be difficult to allow for div1 users the option to register to div2-only rounds as ranked competitors. If I'm not mistaken, it's not allowed because div1 users might run out of problems to solve, but if they wanted to register as ranked competitors into div2-only rounds, they'd have to accept that possibility, yet could still get the fun of competing in a ranked round. Many div1 competitors usually can't solve any problems past the first 3 anyway (I know I can't).
•  » » » 3 years ago, # ^ |   0 It would be nice. We can just have separate rankings, which means some may loose rating even though they solve all problems (but too slow).
•  » » » 3 years ago, # ^ |   0 Div1 competitors will quickly solve problems and will begin constantly hack others. Poor chance for div2 competitors to hack somebody (and learn how to hack).
•  » » 3 years ago, # ^ |   +12 Probably because the F and G problems in this round would be way too easy as Div1 D and E.
•  » » 3 years ago, # ^ |   +3 Is someone going to answer his question!?
•  » » » 3 years ago, # ^ |   +25 I can try. Because the problems are too easy for Div 1?
 » 3 years ago, # |   -6 Hope it will be a good contest! :)
 » 3 years ago, # |   +11 Let's hope this be a nice round for everyone :D
 » 3 years ago, # |   0 Hope to have some Nice Problem with Short, Precise & Easy to Understand Problem Statement .
 » 3 years ago, # |   +25 Good luck everyone
 » 3 years ago, # |   -7 It's been a long time since a totally normal rated Codeforces Round. :(
•  » » 3 years ago, # ^ |   +12 Except this one has 7 problems and 2.5 hours and is only rated for Div.2.
 » 3 years ago, # | ← Rev. 2 →   -28 When Soni says something, you repeat it!When Soni does something, you do it!When Soni has something, you don't have it!And that's so because Soni is a cool guy!
•  » » 3 years ago, # ^ |   +7 a div1 guy with fake acc
•  » » » 3 years ago, # ^ |   -6 Soni>Div1!
 » 3 years ago, # |   +14 Why 7 problems for div.2???
•  » » 3 years ago, # ^ |   +9 maybe for easy problems :-"
•  » » 3 years ago, # ^ |   +5 I guess maybe they found those problems were too easy for div.1. So, 7 problems for div.2. lol Okay,frankly, maybe just for fun.
 » 3 years ago, # | ← Rev. 2 →   +3 I wonder if there's something that could tell me my expected ranking to get a +rating. Even 5 minutes before the contest would be great. Don't know if that's even possible though.
•  » » 3 years ago, # ^ |   +6 you expected rank can't be computed before the contest is finished, because it depends on the people who make at least one submission
•  » » 3 years ago, # ^ |   +3 Try the NBHEXT extension for Chrome. It is not completely accurate because systest, but you get a rough estimate.
•  » » » 3 years ago, # ^ |   0 I think that it consistently gives lower ratings because it interprets newcomers as having "0" rating instead of "1500" rating.
•  » » » » 3 years ago, # ^ |   0 Yup, and it also occassionally shows a 0 difference for Legendary Grandmasters when it obviously shouldn't be 0. But like I said, rough estimate.
 » 3 years ago, # |   +6 Can I request a 10 minute delay? The bus is slow : O
•  » » 3 years ago, # ^ |   0 5 min? hah
•  » » » 3 years ago, # ^ |   0 if I don't mistake it has extra registration...
 » 3 years ago, # |   0 Funny. When using CHelper, you can see "April Fools Day Contest 2016" before today's round. Did that one already happen?
•  » » 3 years ago, # ^ |   0 I guess it's because it was added to the contest list earlier?
 » 3 years ago, # | ← Rev. 2 →   0 Is something changed regarding contest registration. Though I registered, it's still asking for registration while submission.http://i.imgur.com/35uAN1W.jpg---  Now option to register re-appeared, and can submit after re-registration.
 » 3 years ago, # | ← Rev. 2 →   0 .
 » 3 years ago, # |   0 Why is problem A blocked? I want to resubmit my solution.
 » 3 years ago, # | ← Rev. 2 →   0 I am not put in a room for hacking, so I cannot hack. Is this a bug?EDIT: I also registered late, so I don't know if this is the problem?
 » 3 years ago, # |   0 smart problems :) (y)
 » 3 years ago, # |   +24 I don't want to see all human defeated by AlphaGo, but this will happen if AlphaGo passes all system tests
•  » » 3 years ago, # ^ |   +22 His submissions look suspicious though. He got B and C accepted in the same minute, and it only took him 8 minutes to solve G.
•  » » 3 years ago, # ^ |   0 By the way, I think that the problem statements are pretty formal and the next challenge for the DeepMind team could be trying to compete in the programming contests. Correct me, please, if I am wrong and there is something about artificial neural networks that doesn't allow them to compete here.
•  » » » 3 years ago, # ^ |   +40 Are you joking? Sometimes I can't figure out what the hell the authors want from me by myself, and you want to make computer understand that?
•  » » » » 3 years ago, # ^ |   +1 Well, aren't computers better at solving CAPTCHAs than humans already? But I agree that it seems very unlikely to happen
•  » » » » 3 years ago, # ^ |   0 You know that can't be an argument :)Sometimes we cannot recognize faces on the pictures, but Google can (despite the millions of years of evolution that crystallized our ability to recognize human faces).
•  » » 3 years ago, # ^ | ← Rev. 2 →   -11 I wanna see AlphaGo vs tourist face-off assuming AlphaGo is AI and not a team/user.
•  » » » 3 years ago, # ^ |   +11 If AlphaGo is an AI I will eat my hat.
 » 3 years ago, # |   0 Interesting contest, what was the solution to F?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Loop through all the cells. If k is evenly divisible by the number in the cell, and cellnum*m*n is greater than k, then do a BFS across adjacent cells that are greater than or equal to cellnum. If we have processed k/cellnum nodes, immediately print YES, print a matrix such that any cell examined in this BFS is given number cellnum and all other cells are 0, and then return. If the loop completes without finding anything, print NO.
•  » » » 3 years ago, # ^ |   +5 Won't this time out, if all the cell numbers are divisible by k and none have required adjacent cells greater than its value?
•  » » » » 3 years ago, # ^ |   0 You are correct... for example, the 1000x1000 checkerboard pattern of 3 and 7 with a 1 on the bottom right and k=3000000 times out horribly with the wording I gave. I should add, then, that I kept track of which cells I had visited in BFS's for a given factor, so I wouldn't do duplicate work (i.e., a full BFS every time I ran across the number 3). With this addition, it doesn't time out in practice because the number of distinct factors of k such that you will need to examine a sizable subset of the matrix is exceedingly small.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +3 Mine didn't. I used the same approach. But I used some heuristics to reduce the time (eg. I consider only those values in the arr[][] such that k/arr[i][j] <= n*m). Please refer to 17055152.
•  » » » » » 3 years ago, # ^ |   0 Thanks, that did help.
•  » » » 3 years ago, # ^ |   0 If you want O(nlogn), you can use DSU on components to store the number in each component and a priority queue to process cells by descending height so that you dont have to process any large amount of area twice.
 » 3 years ago, # |   0 Please someone explain problem 5. I think it is somewhat related to cycle finding or some trick to be used using dfs/bfs.
•  » » 3 years ago, # ^ |   +10 Answer can not exceed the number of connected components. So define answer=number of connected components. If there is a cycle in a connected component then decrease answer.
•  » » » 3 years ago, # ^ |   0 Thank you. Now seems it was to easy and seeing many people solve it.
•  » » 3 years ago, # ^ |   +3 Consider each connected component separately.If the connected component is a tree, the answer is 1. This is because there are only V - 1 edges — not enough edges for all vertices. It is not more, we can root the tree and direct all edges from parent to child. Only the root will have no incoming edges.If the connected component has cycles, the answer is 0. To see this, take an arbitrary cycle and direct the edges in it the obvious way. Now you can throw out some edges (and direct them randomly) to get a tree for every vertex in the cycle. Direct all those trees from parent to child and you'll see that all vertices have incoming edges.So, for each connected component, check if it is a tree, and if it is, add one to the answer.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Alternate (greedy) solution: count undirected edges as "inward" edges use a min-heap to store number of incoming edges to each node assign "inward" edges by popping off min heap at the end, the answer is the number of nodes without any "inward" edges (http://codeforces.com/contest/659/submission/17054791)
•  » » 3 years ago, # ^ |   0 Consider a connected component If it has a cycle it is possible to assign directions to edges such that no vertex has zero incoming edges If it has no cycles there will be exactly one such vertex So just count connected components which do not have cycles
•  » » 3 years ago, # ^ |   +4 if you don't want to find cycles, then just count the number of edges in each connected component, you can do it by summing up the degrees of all nodes in that component then divide it by 2. if the number of edges is equal to number of nodes minus 1 then it's tree and there's no cycle, otherwise there's a cycle
 » 3 years ago, # |   +3 Hacking test of B?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 5 2 Ivanov 1 763Andreev 2 800Petrov 1 800Sidorov 1 800Semenov 2 503
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Isn't the answer of that Sidorov Petrov Andreev Semenov
•  » » 3 years ago, # ^ | ← Rev. 3 →   +8 3 1 a 1 1 b 1 1 c 1 0 ans a b 3 1 a 1 1 b 1 0 c 1 0 ans ? 3 1 a 1 0 b 1 0 c 1 0 ans ? 3 1 a 1 0 b 1 0 ans a b 
•  » » 3 years ago, # ^ |   0 4 2 Ivanov 1 800 Andreev 2 763 Petrov 1 800 Semenov 2 503
•  » » 3 years ago, # ^ |   +12 some people wrote if (list[i][0] == list[i][2]) printf("?"); else print answer, which is wrong (should be list[i][1] == list[i][2])
 » 3 years ago, # | ← Rev. 2 →   0 Problem B Hack3 1dushyant 1 20sumit 1 16snigdh 1 16Answer --> ?PS — My submission will fail. :(
 » 3 years ago, # |   +32 Look to the solutions of problems B and C user AlphaGo , they sent in 10:48 and 10:51, and had so different style code, i think it wrote by different people
 » 3 years ago, # |   +2 why geometry why :'(
•  » » 3 years ago, # ^ |   0 I kept trying to solve D for two hours. Did you solve it? . I couldn't get my algorithm right for finding whether a line segment will properly cut any segment of the polygon when extended in the direction given.
•  » » » 3 years ago, # ^ |   +9 All of the left turns are dangerous, while right — not. If we know this, we can solve the problem with no geom using some conditions.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 It is never stated that she is travelling clockwise. If she goes counter-clockwise, then a right turn is dangerous, and left is not.Edit: I retract my statement, I didn't realise that the staring positions was always the bottom left
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 if she starts at the bottom left and the first move is to go north, there's no way the water will be on the left side (since you end up at the starting position, see http://codeforces.com/contest/659/submission/17049036).
•  » » » » » » 3 years ago, # ^ |   0 Yes, I realise that now, I never saw that part
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 Checking whether the direction is clockwise is actually really easy. Consider the following equation:.The direction is clockwise if and only if the sign is negative.EDIT: Friggin' Codeforces Latex
•  » » » 3 years ago, # ^ |   +1 the answer is the number of left turns (you can get that by cross product)
•  » » » 3 years ago, # ^ |   0 My approach to D was to keep a counter for the dangerous turns if the water is on the left and if the water is on the right. While iterating through all the points, use the previous point, current point and next point to determine whether she is turning left or right. If you are turning left, the it would be dangerous for the water to be on your right, so increment the right counter. If you are turning right, the it would be dangerous for the water to be on your left, so increment the left counter. Then when you are done iterating through every point, just output whichever counter is smallest.
•  » » » » 3 years ago, # ^ |   +3 Starting point is at the left-bottom most point, there is no way the water can be in the left.
•  » » » » » 3 years ago, # ^ |   0 Ah, I didn't see that. I made more work for myself than I needed.
•  » » » 3 years ago, # ^ |   +6 My solution is simply (N-4)/2. Consider 90 degree and 270 degree angles.
•  » » 3 years ago, # ^ |   +5 After some minutes of thinking how to solve it in a nice way, I give up and seek for pre-written geometry library that do the job for me (I hope there's no bug inside tho).For those who solve it without a generic written code, how do you guys managed to write decently? (e.g. without using lots of if)
•  » » » 3 years ago, # ^ |   0 Which library did you use?
•  » » » » 3 years ago, # ^ |   +5 Actually it's not a library, just a codebook containing the function Point_Inside_Polygon which is exactly what question asked :)I forget why the function work tho
•  » » » » » 3 years ago, # ^ |   0 It malfunctioned. I kept modifying it. Something kept breaking :(
•  » » » » » » 3 years ago, # ^ |   0 I used the built in Java function that does that, but fiddled with it a little as the function sometimes seems to be buggy if the point is directly on the side of a polygon.http://codeforces.com/contest/659/submission/17053372
•  » » » 3 years ago, # ^ |   +1 I used 4 ifs (in fact 8 so that the conditions are more clear), is that a lot?
•  » » » » 3 years ago, # ^ |   0 I coded along a similar structure with 4 ifs. But the intersection part i couldn't get it right for the second sample. It fails for the cases where a line goes through the edge of the polygon rather than through it :(
•  » » » 3 years ago, # ^ |   +1 You can solve it with just basic things like calculate area of polygon & CCW
•  » » » » 3 years ago, # ^ |   0 Turns out area isn't even needed because you start at the bottom left...
•  » » » » 3 years ago, # ^ |   0 As it has been said the answer is (N-4)/2 since when you have more than 4 edges on the polygon all the left turns will have one corresponding right turn. I am amazed how almost none of us didn't figure that out, going instead for a longer solution...
•  » » » » » 3 years ago, # ^ |   +8 Hahaha almost thought of convex hulls and stuff until I realized "hey could I find a pattern". and I noticed it was something like linear (clearly it must) and then I remembered of 90 and 270 degrees. Basically if we have an n-gon composed of 90 degrees and 270 degrees suppose there are a 90 degrees and b 270 degrees. Total angle is 180(n-2). Then 90a+270b=180n-360... a+b=n. Solving we get b=(n-4)/2. Yay
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 You can do it without calculating the area or point-in-polygon queries, by just checking 4 conditions regarding the previous and next directions of movement, for each corner point. Please refer 17044429.
•  » » » 3 years ago, # ^ |   0 Collect all if's in one place and use enums: 17046342
 » 3 years ago, # | ← Rev. 2 →   +6 Who is AlphaGO?
•  » » 3 years ago, # ^ |   0 chameleon
•  » » 3 years ago, # ^ |   +9
•  » » 3 years ago, # ^ |   +23 By seeing submission gap between B and C, probably a team.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 What if he thought to first solve both problems and then submit?
•  » » » » 3 years ago, # ^ |   0 Thats, why I wrote "probably".
•  » » » » 3 years ago, # ^ |   0 Maybe he had a stupid bug in B, submitted C, corrected B and this resulted in both submissions the same minute :)
•  » » » » 3 years ago, # ^ |   +23 What if he's an AI?
•  » » » » » 3 years ago, # ^ |   +35 And his codes have different styles because he searches and combines codes from a huge database of solved problems.
 » 3 years ago, # |   0 Please suggest an approach to solve F and G.Thank you.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +3 F is already explained, as regards G I did dp:dp[i][0] — the number of ways where you remove something from position i and the remaining height is not greater than h[i+1]dp[i][1] — the number of ways where you remove something from position i and the remaining height is greater than h[i+1]Obviously if h[i] <= h[i+1] then dp[i][1] = 0;Hope that helps.Edit: If not, here is the submission implementing that logic: http://codeforces.com/contest/659/submission/17059428
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 I think it can be solved in a greedy manner, using DSUs. Start processing the cells in decreasing order of their values. When you process a particular cell, check its neighbouring 4 cells. The cells among those 4 which have their values >= value of current cell, are combined with the current one using DSU. After each combination, check whether that set has the required number of cells (if value of the cell is v, the set should have at least k/v elements). The moment this occurs, you have found the answer. Assign exactly k/v cells of this set to v, and assign all remaining cells in the grid to 0.
•  » » » 3 years ago, # ^ |   0 i have been doing that ... but got a lot of errors and ended up with a WA on case 95 :/ this is my submission 17066234 any help will be appreciated
 » 3 years ago, # |   +136 Hack you back.
•  » » 3 years ago, # ^ |   +16 Lol, payback. There should be an achievement for a thing like this.
•  » » » 3 years ago, # ^ |   0 Haha, there actually is! I've earned that, see: http://cfa.yuldashev.net/profile/ehsanoo It's called Peresvet & Temir-murza.
•  » » » 3 years ago, # ^ |   0 There is "Speck in your brother's eye", however I don't know if it counts only failed systests or also hack back.http://cfa.yuldashev.net/achievement/5
•  » » 3 years ago, # ^ |   +8 That's so me in past contests, lock one problem, read others' solutions and realize mistakes in mine...
 » 3 years ago, # | ← Rev. 2 →   +5 Nice and balanced problem set, perfectly suits for div2 difficulty in my opinion. But, Problem statements were not easy to understand (at least for me).
 » 3 years ago, # |   0 Wasted my whole time on a silly mistake with B, could have easily solved 4 problems :( :( :(
 » 3 years ago, # |   +1 Codeforces team: Please check FlappyBird's submissions. http://codeforces.com/contest/659/room/112 Seems like he wasn't codding alone.
 » 3 years ago, # |   0 Any ideas how to solve C? I did simple greedy algo but it failed on tc #10.
•  » » 3 years ago, # ^ |   0 Greedy was okay.. Can you post your code ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 You just made 100100 sized array to mark used toys, but that can be from 1 to 1e9. Your update will fail if used toy is greater than 100100.Your code-> const int N = 100100; int n, m; bool toys[N]; 
•  » » » 3 years ago, # ^ |   0 That's what I get for reading too fast. Thanks a lot.
 » 3 years ago, # |   0 What is approach to solve question D ?
•  » » 3 years ago, # ^ |   +27 (n-4)/2
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 Are you serious!? Does that actually work?!?Edit: Ah, I see now! First there is the 4 turns which MUST be made to get back to the start, so subtract them. Then every variation other than those 4 turns require 2 turns to go straight again (1 safe turn and 1 dangerous turn), hence the division by two.
•  » » » 3 years ago, # ^ |   0 Can you provide some explanation for this?
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   0 very rough idearectangle-> 4sides,0turnings,take a side possible modification gives 2 turns for 4 more extra points
•  » » » 3 years ago, # ^ |   0 ...and here I thought I was being clever with my vector solution counting the left turns.
•  » » » » 3 years ago, # ^ |   +1 not my idea some in my room did this , i tried to hack but was not able to get any test case
•  » » » » 3 years ago, # ^ |   0 Me too, I also counted left turns)
•  » » » 3 years ago, # ^ |   +13 Lol and here was I dangling with geometric algorithms and what not :P
•  » » » » 3 years ago, # ^ |   0 Me too :( Although I didnt get it right? Did you solve it using any geometry algorithm? If yes, what was your approach?
 » 3 years ago, # |   +3 Before that contest finished, I was 1200 and now I have two failed problem and I am 3200. Ohhhhhh noooooo.
 » 3 years ago, # |   0 Anyone else not realize that you couldn't add to piles in problem F? I had the solution but made that dumb mistake ugh.
•  » » 3 years ago, # ^ |   0 Or not. TLE lol
 » 3 years ago, # |   0 Can someone tell me some hacking tests for 'A'. A guy I know made 11 successful hacking attempts :D
•  » » 3 years ago, # ^ |   +1 Possible mistake can be giving output a negative number, because of improper modulo operation. Mine failed at this->10 6 -100answer should be 6.my code outputs -4.
 » 3 years ago, # |   +9 Please enable upsolving !
•  » » 3 years ago, # ^ |   0 It starts when system testing is done, which is going on and will complete soon.
•  » » » 3 years ago, # ^ |   0 Seems enabled now.
 » 3 years ago, # |   +3 I hate that kind of simple but tricky problems like A!
 » 3 years ago, # |   +5 How is this even working?? Problem D. answer is n/2 — 2 ; http://codeforces.com/contest/659/submission/17055800
•  » » 3 years ago, # ^ |   +1 n/2 — 2 is the exact same as (n-4)/2, to which there are multiple explanations in the above comments. One of them should help you out.
 » 3 years ago, # | ← Rev. 2 →   0 The difficulty of C, D, E problems weren't even of Div2 level.. The contest should be renamed to "DIV 3". 1000+ people solved C,D,E
•  » » 3 years ago, # ^ |   +7 I liked problem E!
•  » » 3 years ago, # ^ |   0 But A and B were?
•  » » 3 years ago, # ^ |   +3 Can you please explain how you solved problem E?
•  » » » 3 years ago, # ^ |   +4 If you are given a tree, then the answer will be 1. Let's say you root the tree from a certain vertex, then we can draw directed edges from parent of all vertexes to them (And none of them will be seperate). Except the root (which has no parent) .. So in a tree we will always have answer 1.But, if we add one more edge to the tree. We can satisfy the earlier separated node (i.e root). So, if we have a cycle in the tree. It would have answer 0.So finally see all the connected components that doesn't have a cycle (count all the connected components that are actually trees). This could be done easily with a DFS.
•  » » » » 3 years ago, # ^ |   0 Got it. Thanks! :)
 » 3 years ago, # |   +6 Please someone explain this solution ( http://codeforces.com/contest/659/submission/17054528 ) for problem D.
•  » » 3 years ago, # ^ |   0 Yes they will. In the comments above.
•  » » 3 years ago, # ^ |   +3 Its really an absurd verdict.
 » 3 years ago, # | ← Rev. 2 →   0 I first submitted a solution in problem E which got WA in pretest 9, then i get a new idea which gets AC, but i do not understand why my first idea was wrong!!I gets the in degree for each node and greedlly subtract the highest m value of them (one by one using priority queue ) and the answer is the number of zero in degree after that, and this is the code 17050130why this is wrong?! what i missed here?!
•  » » 3 years ago, # ^ |   0 Your code fails in a test like this 6 7 1 2 2 3 3 4 4 1 2 4 1 3 5 6 
•  » » » 3 years ago, # ^ |   +3 Thanks Mr.president :D :V
 » 3 years ago, # |   0 When will the ratings be updated? Has anyone's been updated yet?
 » 3 years ago, # |   0 Can anyone help me please ? Why I am getting WA at Test 15 for Problem B ???http://codeforces.com/contest/659/submission/17059710
•  » » 3 years ago, # ^ |   0 you are checking an extra condition, which is wrong and not required. I have submitted modified code of yours to get AC. Refer this -> http://codeforces.com/contest/659/submission/17060205
•  » » » 3 years ago, # ^ |   0 Thank You ... But Why this Happens so? do you please Explain ??
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 When only 2 candidates belong to some region and have same top score, you were giving output of "?". Which is wrong. As top scorers are the winners of that region.
 » 3 years ago, # | ← Rev. 2 →   +44 Is AlphaGo not a single coder?The coding style of the submissions by this account are different. For examples, solutions on C and F used: #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif while others don't.And solutions on E and F used: #include while others don't.We can find that the coding styles of different codes are not similar.On the other hand, AlphaGo used only 3 seconds to submit B after C. Should this kind of accounts be banned?
•  » » 3 years ago, # ^ |   +2 OK this account is fake, but there is no proof so he can't be banned.
•  » » » 3 years ago, # ^ |   +11 If it doesn't get banned, this may create a precedent for others to cheat.
•  » » » » 3 years ago, # ^ |   +11 Looks like PPFishIsADoge is not a single coder too.
•  » » » » » 3 years ago, # ^ |   0 Yeah, I looked upon his submissons a moment ago and the coding style is different.
•  » » 3 years ago, # ^ |   0 Also there seem to be 2 very distinct templates being used.
 » 3 years ago, # |   0 Can someone tell me why I am getting TLE in my solution for B , I am trying to find bug around 2 hours : 17055144 ?Thanks in advance.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 linkyour sort function is not good. if (compare(a, b) == true) then (compare(b, a)) should be false.
•  » » » 3 years ago, # ^ |   0 Thanks! It is silly mistake :)
•  » » 3 years ago, # ^ |   +6 Hi. Your comparator must return 0 for (a, a). Ac.
•  » » » 3 years ago, # ^ |   0 Thanks for help :)
 » 3 years ago, # | ← Rev. 2 →   0 First time to solve A-B-C-D-E during the contest time and guess what!! my rate decreased :(
 » 3 years ago, # |   +3 Please let us open the problemset now
 » 3 years ago, # |   +6 This is my first round to get an AC problem, nice problems (y)btw this is also my first comment in CF xD
 » 3 years ago, # |   0 Can someone tell me what is wrong with my B solution? 17044686
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 You need to check that a[i].size() == 2 before asking values, otherwise your if (a[i][0].score == a[i][1].score)will result in undefined behaviour in C++.
•  » » » 3 years ago, # ^ |   0 Thanks!
 » 3 years ago, # |   +5 Before and After system test
 » 3 years ago, # |   +24 thanks dude! 17057269
•  » » 3 years ago, # ^ |   +18 No problem buddy :]
•  » » » 3 years ago, # ^ |   +1 Can I ask why?
•  » » 3 years ago, # ^ |   +11 ...why?
 » 3 years ago, # |   0 I had a problem with the 53 test case of the B problem. My output is correct, and the author of the problem didn't estipulate any order of the names of the selected member of the team...I got wrong answer, and the checker message was "wrong answer Jury solution is better than the participant [region=143]" ... I just don't understand the reason that i've received WA...
•  » » 3 years ago, # ^ |   0 Before checking [1] == [2] you must ensure that there is at least 3 participant, otherwise equality checking result would be undefined
 » 3 years ago, # |   0 Can anyone explain this solution to E. for me? 17042676 by AlphaGoI think I get that the array fa represents the "root" of each node's connected component. What are tot and TOT?
•  » » 3 years ago, # ^ |   0 tot: vetexes count TOT: edges count if TOT==tot, there is a circle
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 Thank you! Do you know what purpose this line serves? tot[u] = TOT[u] = 0Edit: I just tried running the submission, exactly copied, but with that line removed. It still passed all tests. So it looks like that line is unnecessary.
 » 3 years ago, # |   0 As the tutorial said, we can make a boolean array in problem c; but i failed to do it at c++, because array size of 1e9 was too great, can anyone tell me how to achieve that, thank you
•  » » 3 years ago, # ^ |   0 Using sets. Learn STL as soon as possible. Because it's very useful and easy.
•  » » 3 years ago, # ^ |   0 The editorial also specified to maintain a boolean array of max 2*10**5 and from the input numbers mark only those that are less then 2*10**5.
•  » » » 3 years ago, # ^ |   0 i just don't know how to maintain that boolean array, can you make it using c++ code, thank you
 » 6 months ago, # |   0 659F-62 - Polycarp and Hay I dont know why my code is getting wrong solution on 11th test case.can someone help me. Thanks.(https://codeforces.com/contest/659/submission/49156796)[submission:49156796]