### HolkinPV's blog

By HolkinPV, 7 years ago, translation, ,

Hello everybody)

Today is coming regular Codeforces round #161 for Div.2 participants. Traditionally the others can take part out of the competition.

The problems were prepared by authors: Pavel Kholkin (HolkinPV), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating the problems. Also thanks to Rakhov Artem (RAD) and Vitaly Aksenov (Aksenov239) for their help.

UPD: Today it is decided to use dynamic scoring system. But the problems will be sorted from low difficulty to high by authors' opinion!

We wish everyone good luck, successful hacks and high rating!

UPD2: the contest is over) hope you enoy it

Congratulations to winners:

UPD3: the tutorial is published, you can find it here

• +86

 » 7 years ago, # |   +15 Hey, I believe I just saw a post where blogger and PavelKunyavskiy are the writers of the contest!
•  » » 7 years ago, # ^ |   +18 That was a stupid joke.
•  » » » 7 years ago, # ^ |   0 Strangely enough, it appeared on the front page.
•  » » 7 years ago, # ^ |   +5 me too
•  » » 7 years ago, # ^ |   +8 I don't know anything about it.
 » 7 years ago, # |   -8 What will be the Rating Of problems? You have not mentioned i think you have to mention it in your blog if you are going to prepare the problems for any contest.
 » 7 years ago, # | ← Rev. 3 →   +6 I think is time to have some more information about the score and difficulty distributions :)UPD:Thank you.
 » 7 years ago, # |   +23 Wish epic failures to everyone! ^.^
 » 7 years ago, # | ← Rev. 2 →   0 :/
 » 7 years ago, # |   +5 Can somebody explain how solve problem D in O(N)?
•  » » 7 years ago, # ^ |   +9 It is guaranteed that each node of the graph is connected by the edges with at least k other nodes of the graph.Therefore it's possible to form cycles from any point (I think) So I do a DFS on node 1
•  » » 7 years ago, # ^ | ← Rev. 2 →   +16 Let's go from vertex 1 and build a chain. At each iteration, if we are in vertex v, if exists some vertex u, that is in our chain at distance at least k, then we go to it and end the cycle. Else some vertex u exists such that it hasn't been visited yet, so we go to it. At some moment we'll end the cycle, because it's only finite number of vertices at all.
•  » » 7 years ago, # ^ |   +7 Build up the cycle as a path, until the last vertex of the path is the same as first one. Start with an arbitrary vertex. For the first K+1 vertices of the cycle, use a greedy approach — K times choose one vertex which is not in the path and connected to the last vertex of the path. There will always be one (because at most K-1 vertices apart from itself are in the path, so there must be at least 1 neighbour vertex left). Now, augment this path in the same way, until you can't do it. Then, take the last K vertices of the path; the last of them will have at least one neighbour other than those, but all his neighbours are in the path, so there must be a neighbour X of the last vertex of the path; add it to the end of the path. This way, there's a simple path in the graph, which starts and ends at X, and contains at least K vertices. BTW the time complexity is O(N+M), and it's optimal.
•  » » » 7 years ago, # ^ |   0 Thanks everyone for explain :)
 » 7 years ago, # |   +8 Does the dynamic scoring system take into account unofficial participants from div 1?
•  » » 7 years ago, # ^ |   +5 No.
•  » » 7 years ago, # ^ |   0 Look here: http://codeforces.ru/blog/entry/4172
 » 7 years ago, # |   0 How to solve problem C
•  » » 7 years ago, # ^ |   +7 Case N=5 is clear. Bruteforce N=6. For N > 6, there are vertices a,b,d,e, all connected to vertex 1, and connected in the order in which they appear on the cycle: a-b-1-d-e; among them, only b and d are also connected. So you can find b and d — the only points which have 2 common neighbors with 1. You now have a part of the cycle: b-1-d. If you have a part A-B-C, then you can find the next vertex D on the cycle (A-B-C-D-...), because it's the only common neighbor of B and C other than A. Complexity: O(N).
 » 7 years ago, # |   0 Very fast System Testing :P
 » 7 years ago, # |   +6 well done everyone and what a brilliant problem C. :) can anyone explain any easy to code in C++ :) solution for problem C? I think this question is truly common between all the contestants :) thanks everyone.
 » 7 years ago, # |   +13 Currently most of the fastest solutions to the problem E are written in Java, you don't see it often :D
 » 7 years ago, # |   +1 Thanks for a good contest!
 » 7 years ago, # |   +3 There are some straight-forward backtracking codes for D which are getting ACed. Really curious how this is possible :/
•  » » 7 years ago, # ^ |   +2 One dfs is enough to find a solution for this problem. That's why backtracking needs only one branch to find the answer so it works in O(N + M).
•  » » 7 years ago, # ^ | ← Rev. 3 →   +48 At least one AC solution fails at this test: 7 8 2 1 2 2 3 3 4 4 2 1 5 5 6 6 7 7 5 My guess is than in all tests vertex number 1 is on the needed cycle.
•  » » » 7 years ago, # ^ |   +8 I'm guessing a lot of cases can be made where the backtracking fails. I don't know how they made their testcases :/
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 we could visiting and put time stamp on it, suppose you are visiting node i, it must connect with k nodes, if one of them not visited, continue visit this node, if all the k nodes are visited, now we have the solution, the start position is the one in these k nodes which have the smallest time stamp, the length from it to node i must larger than k.
•  » » » 7 years ago, # ^ |   +13 I've also found a code that fails in the case gen has given above. This case definitely should be added and rejudged to maintain fairness. (no matter how many minus i get :) )
•  » » » 7 years ago, # ^ |   +1 I guess it would be good if you send this testcase with the failing code(which got AC) to Gerald or contest writers.Anyway I suppose test number 18 is something like this. since I saw some of the solutions which used maximal path that were trying to create the cycle with first node of the path(instead of the last). These solutions got WA in test 18. In the testcase answer shown to us there is no "1" in the answer so I suppose in this test first node wasn't actually in the cycle.
 » 7 years ago, # |   +11 First 10 Minutes in the contest i was happy that i solved A and B problems, but i shocked after that :)
 » 7 years ago, # |   +8 persianpars did impossible. congratulation persianpars.
•  » » 7 years ago, # ^ |   +8 thanks i still don't believe that i finished second
 » 7 years ago, # |   +9 ehhh... This is my first time that I think I can solve problem C in contest. Although I fail, but it gives me a good time. thanks !!!!
 » 7 years ago, # |   0 Nice contest!
 » 7 years ago, # |   0 Problem set was really good. I really enjoyed the contest. Best round for me so far.
 » 7 years ago, # | ← Rev. 3 →   0 Yeaaaaahhhh !! This is the first time I solved the E problem — I guess it wasnt that hard :)) -Also it seems that in certain problems (like this one) the title is a hint (good to know :)My time complexity was O(n*m*k) , actually it was O((n-2*k)*(m-2*k)*k). Can it be done faster than this ?
•  » » 7 years ago, # ^ |   +3 I see something strange in your contest stats, it seem that the solution for B is still in queue o.O
•  » » » 7 years ago, # ^ |   0 I know. I got AC and then the status changed. I have no idea what the problem might be ... :-??
•  » » 7 years ago, # ^ |   0 but the limits aren't good for this problem... if k = n / 4 the complexity is n/2*n/2*n/4 = O(n^3) which should not work in 3 sec i dont think there are faster solutions cause all the sources are like this
 » 7 years ago, # |   0 I have solved 1 problem in this round (in the running contest) but my rating got down from 906 to 872 .I have also solved a problem in running contest of Round #156 (Div. 2) but the authority didn't increase my rating . why????
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 Your rating depends on how well other people did in the contest as well. Probably almost everyone did solve at least 1 problem. So that's why your rating did not increase.I think if you want to increase your rating, you should learn a lot of things before taking the next contest.
•  » » 7 years ago, # ^ |   +1 Maybe because you need to solve more than just the first problem to increase the rating :D
 » 7 years ago, # |   +1 Editorial is published here
 » 7 years ago, # |   0 for problem B somebody tell me is this a valid input? if yes what is the correct output for it. 4 3 3 3 3 3 `
•  » » 7 years ago, # ^ |   +2 It's incorrect input because "It is guaranteed that all given squares are distinct."
•  » » » 7 years ago, # ^ |   0 Ok thanks.
 » 6 years ago, # |   -6 I post my solution in Chinese,anyone can view it. here is my blog
 » 6 years ago, # | ← Rev. 2 →   0 Hi,I am a noob and would like some help with understanding why I am getting different result for problem B than what the server throws up (as erroneous output)? This is happening for the 2nd time to my notice. Submission ID: 2961857 at test #7. My gcc gives as output exactly what is stated as the answer. If this is not the place to put these sort of questions, please direct me to the appropriate area.Thanks and Cheers!
•  » » 6 years ago, # ^ |   0 what gcc you using??
•  » » » 6 years ago, # ^ |   0 version 4.6.3
•  » » » » 6 years ago, # ^ |   0 I am also using the same version of gcc but mine get accepted :P
•  » » » » » 6 years ago, # ^ |   0 With the code from my submission? I've seen another submission of mine being rejected like this once before. Could this be a bug? Or am I doing something wrong?
•  » » » » » » 6 years ago, # ^ |   0 not bug!! May be you were doing wrong