HolkinPV's blog

Codeforces Round #161 (Div. 2)
By HolkinPV, 12 years ago, translation, In English

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:

1) poao900
2) persianpars
3) Sert
4) valentin.harsan10
5) MeinKraft

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

  • Vote: I like it
  • +86
  • Vote: I do not like it

Comments Comments (45)
| Write comment?
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Hey, I believe I just saw a post where blogger and PavelKunyavskiy are the writers of the contest!

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

I think is time to have some more information about the score and difficulty distributions :)

UPD:Thank you.

→ Reply
»
12 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Wish epic failures to everyone! ^.^

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can somebody explain how solve problem D in O(N)?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Does the dynamic scoring system take into account unofficial participants from div 1?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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).

    → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Currently most of the fastest solutions to the problem E are written in Java, you don't see it often :D

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for a good contest!

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There are some straight-forward backtracking codes for D which are getting ACed. Really curious how this is possible :/

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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).

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +48 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I'm guessing a lot of cases can be made where the backtracking fails. I don't know how they made their testcases :/

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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 :) )

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

First 10 Minutes in the contest i was happy that i solved A and B problems, but i shocked after that :)

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

persianpars did impossible. congratulation persianpars.

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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 !!!!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem set was really good. I really enjoyed the contest. Best round for me so far.

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Yeaaaaahhhh !! This is the first time I solved the E problem — I guess it wasn`t 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 ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I see something strange in your contest stats, it seem that the solution for B is still in queue o.O

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know. I got AC and then the status changed. I have no idea what the problem might be ... :-??

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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????

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Maybe because you need to solve more than just the first problem to increase the rating :D

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial is published here

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
→ Reply
»
12 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I post my solution in Chinese,anyone can view it. here is my blog

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How could such a boring problem such as Problem C be rated 2000? Yuck.

→ Reply