Блог пользователя HolkinPV

Автор HolkinPV, 12 лет назад, По-русски

Всем привет)

Сегодня состоится очередной раунд Codeforces #161 для участников Div. 2. Как и всегда, остальные могут поучаствовать в нем вне конкурса.

Задачи для вас подготовили авторы: Павел Холкин (HolkinPV), Николай Кузнецов (NALP) и Геральд Агапов (Gerald). Традиционно хочется поблагодарить Михаила Мирзаянова (MikeMirzayanov) за систему Codeforces и возможность проведения соревнований. Также благодарим Марию Белову (Delinur), которая перевела условия задач. Также выражаем благодарность Артему Рахову (RAD) и Виталию Аксенову (Aksenov239) за помощь в проведении соревнования.

UPD: В раунде будет использована динамическая система оценки задач. Задачи отсортированы, по мнению авторов, по предполагаемому порядку увеличения сложности.

Надеемся, что соревнование окажется удачным для всех участников, успешных взломов и высокого рейтинга)

UPD2: соревнование завершилось) надеемся оно вам понравилось

Поздравляем победителей:

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

UPD3: разбор задач опубликован, его можно найти здесь

  • Проголосовать: нравится
  • +86
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Последняя тренировка перед 1 туром регионального этапа. Всем удачи

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

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

UPD:Thank you.

»
12 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Wish epic failures to everyone! ^.^

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Удачи всем

»
12 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Помоему у многих С — шка на 4 тесте упала.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +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

  • »
    »
    12 лет назад, # ^ |
    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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +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.

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Расскажите, пожалуйста, решение задачи C.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Переберём в лоб первых 4 позиции. Остальные восстанавливаются однозначно. Меня взломали, но я думаю, что если писать более аккуратно, это заходит.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Достаточно первых трех. При чем, первую перебирать не надо, можно ее захардкодить, например — 1. Получается, достаточно перебрать только вторую и третью позиции

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Для n=5 ответ 1 2 3 4 5, для n=6 ответ находим перебором, иначе находим ближайшее к текущему число — для них количество равных чисел, с которыми они соединены, равно двум, и продолжаем поиск из того, что нашли

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      32 test

      нужно проверять что у вершины не более 4 рёбер

      если нарушено то заведомо -1

      при n==6 перебор + отсечение антипод(та единственная вершина с которой не связана текущая) в пути через 2 вершины иначе любой цикл длины 6 через разные вершины замкнут , что не правильно

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Первые три числа в 3-ем претесте E можно узнать?

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem C

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +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).

»
12 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Раунд отличный, задачи интересные!

»
12 лет назад, # |
  Проголосовать: нравится +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.

»
12 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Новая страница статуса с автообновлением рулит.

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thanks for a good contest!

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +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).

  • »
    »
    12 лет назад, # ^ |
    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.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
      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.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +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 :) )

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +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.

»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

persianpars did impossible. congratulation persianpars.

»
12 лет назад, # |
  Проголосовать: нравится +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 !!!!

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice contest!

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В С разобрал 41 тест перед отправкой на листочке, но почему-то в программе его не пофиксил :(

»
12 лет назад, # |
  Проголосовать: нравится 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????

  • »
    »
    12 лет назад, # ^ |
    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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится -43 Проголосовать: не нравится

несмотря на этот комментарий контест рейтинговый?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    1 — Рейтинг уже пересчитали.

    2 — Думаю не все мутили бэктрэкинг. У меня на этот тест выдало 3 4 3 2.

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Editorial is published here

»
12 лет назад, # |
  Проголосовать: нравится 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
»
12 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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