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

Автор Untitled, 11 лет назад, перевод, По-русски

Всем привет! :)

Я (Untitled) приглашаю вас к участию в Codeforces Round #178 (Div. 2), который будет проходить сегодня. Я хочу поблагодарить Gerald Delinur MikeMirzayanov за помощь в подготовке этого соревнования. Выражаю свою благодарность пользователю havaliza он тестировал задачи сегодняшнего раунда и делал иллюстрации к задачам.

Главный герой соревнования — Shaasss. Надеюсь, что вам понравится помогать ему! :D

Good luck and have fun! ;)

Это перевод оригинального поста автора с английского языка, комментарии на английском приветствуются.

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

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

За что пост-то заминусовали? Если автор контеста синий, это еще ни о чем не говорит)

P.S. Надеюсь к началу соревнования баг со сдачей задач пофиксят?

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

Good luck all. Author, thanks for contest!

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

Thanks all.

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

Теперь контест от зеленых будем ждать)

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

    В этом есть что-то плохое?

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

    Ну и что? Подумаешь. Может зеленый лучше приготовит контест чем фиолетовый. Главное что бы задачи были интересные)

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

А кто это -- Shaasss?

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

Codeforces comes again!How happy am I!

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

Wish everyone good luck and high ratings! :D

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

Who is Shaass?

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

    He's one the most popular heroes in Iran National Olympiad. I guess he's Shaazzz's brother, who is one the most popular and powerful heroes of Iran too :D.

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

      emmm... No , he's not. he's me and my friends hero

      ps. "Shaazzz" is't a guy... is it??

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

        If you meant "fool" of "Shaass", yes it is. "fool is one the funniest and useful heroes in Mashhad. If you didn't, sorry. It was just a guess :D I know Shaazzz is not a person but a group or country or planet or many things else, but this name commonly use in <Shaazzz.blogfa.com> problems. HF & GL!

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

          shaass is short form of shasgol! :D i think.

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится -27 Проголосовать: не нравится

            hey at all shaass is not a good word & we all know what does it mean. I can't understand why he choosed this,there's many better words than it.

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

        it's a big hero, trust me ;)

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

    It's somehow like "fool" in Persian, but in a funny way.

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

I know that people who are under 1900 rating can not prepare contest.

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

    the quality of the contest cannot depend on the rating of the designer however if you remind MR HolkinPV he producted many constests that in that time his rate was under 1900!

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

i love short post (as well as short problem statement)

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -56 Проголосовать: не нравится

Why do not deleting comments !

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

Thank you ! Our teacher , havaliza didn't came school today, because this contest and we came back home soon.So i have too much energy for this contest!!! :D And one question : what are the scores??? 500-1000-1500-2000-2500 ?

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

В задаче 2 что вводить если это невозможно?

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

    выводи "GANSTA SHEET!"

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

      Ты создал новый профиль, чтобы оставить один комментарий?

      Может, устроить на CF регистрацию как на хабре, то есть с помощью инвайтов?

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

what is the meaning of challenge-other when hack others

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -38 Проголосовать: не нравится

мда...теперь я понял что лучше пусть контесты дают люди рангом фиолетовые и высше!

честно мне контест не очень(

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

    Такое ощущение, что чем меньше у человека рейтинг, тем сложнее в среднем получаются задачи.

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

      Можно подумать если я дам контест будет 5 гробов?)

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится -22 Проголосовать: не нравится

        оу...Я надеюсь мир не докатиться до того что будут давать контесты такие как ты! Ты только А решил на этом контесте о каких гробах идет речь?

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

          Следуя вашей логике это так)

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

          А меня забавляет, как люди участвовавшие в 0-1 соревновании рассуждают о соответствии цветов участников и сложности составленных ими задач...

          P.S. мультоводство обычно наказывается баном на различных ресурсах, где присутствуют рейтинги.

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

    Самый лёгкий контест ведь Эксперт готовил:)))

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

      А можно ссылку на этот "Самый легкий контест"?

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

I think in the contest time, the message/talks option should be disabled. People like me who cannot solve more than (2 or 3) problems in a contest, get message "**How to solve B?**".

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

Задачи D и E вызвали у меня то же чувство, что и I у Сергея Федорова :).

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

    И как решать E? Расскажите этот п...ц :)

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

      Переберем ребро, которое будем выкидывать из графа. Выберем из каждой компоненты вершину с минимальной суммой расстояний до всех остальных. Проведем ребро между этими минимумами и посчитаем суммарную длину путей в полученном графе. При правильной реализации все это будет работать за квадрат. Более подробно объяснить с наскоку не могу — я только знаю идею, но никогда ее не реализовывал.

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

      Зафиксируем удалённое ребро и подвесим два получившихся дерева за любые вершины. Теперь нужно выбрать по вершине в каждой компоненте.
      Заметим, что если мы выбираем вершину в одной компоненте, то вклад в ответ, который дают рёбра в этой компоненте не зависит от второй выбранной вершины.
      Таким образом, надо посчитать для каждого из 2 деревьев минимальную вершину и соединить их.
      Теперь идём dfs-ом по 2м деревьям и для каждой вершины узнаём, что будет если она будет концом соединения. Для этого можно передавать в рекурсию вклад, который дают рёбра "выше" ребёнка, куда мы идём. И для каждой вершины предпросчитать, какой вклад даёт её поддерево. Это что-то в стиле w * sz[v] * (n - sz[v]) .
      Можно порисовать и всё понять.

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

What is the answer on test: 2 2 1 1 UR ? I think answer is -1.

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

Жесть

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

http://codeforces.com/contest/294/submission/3489683
Подскажите, пожалуйста, что не так. Казалось бы там квадрат должен проходить.

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

    Похоже на то, что константа большая. Код можно оптимизировать — например, этот перебор ~~~~~ for (int i = 0; i < n; i++) for (int j = 0; j < sz(g[i]); j++) ~~~~~ требует порядка 2*n времени, что в двое больше чем нужно.

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

I've been strugling with problem B, i made DP solution

based on easy thing: DP[thickness] = left

It is, DP[x] = y stands for: We have thickness x and we have to put y on top of our construction.

You can see my solution coded here: 3488673

Then find smallest x for which x>=DP[x]. But this gave me WA on #4 pretest.

Please explain right solution :)

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

    First fix, the numbers of books with thickness 1 and 2. Then you can find the minimum width of the books at the top greedily.

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

    I also used a DP solution, but since the constraints were so small, I used dp[N][MAX_WIDTH][MAX_WIDTH] array and did a knapsack on it for each value from i = 1 to (MAX_WIDTH — 1). MAX_WIDTH is the sum of width of all the books. If any of the values i were sufficient to satisfy all the constraints I considered that the minimum thickness solution. If not, I needed MAX_WIDTH. Could have used binary search to determine i as well if the constraints were a bit higher but didn't need to in this particular case. Here is my code. 3486021

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

    You can do a greedy brute-force. Divide them into 2 arrays(one for thickness 1 and the other for thickness 2). Sort the arrays by width(biggest first) and than for every number of elements of array1 check every number of elements of array2(checking all combinations). And since they are sorted by width, it works.

    See my solution: 3486814

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

Good contest, thank you. Problems are interesting, I like them.

But it is a bit hard for div2.

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

Shaass... Looks like a kind of a jewish name

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

    It's not a real name in Farsi, it is sort of nickname for fool and stupid person :)

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

Why in third test on C answer is 6720?

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

В задаче С было бы неплохо видеть описание того, что такое "способ". И в случае n==m (все включено) правильным ответом может быть 0 или 1 — в зависимости от автора.

И да, задача А читалась тяжело и долго. А в целом контест неплохой.

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

    Мы всегда можем ничего не сделать одним способом, другого не бывает :)

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

      Хотя да, я забыл, что шагов — 0, способ — 1.

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

    Если все включено ответ 1. Так вроде всегда.

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

What's the solution to C?

I look forward to reading the editorial about D and E.

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

Once again an unrated coder winning.

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

What is logic for Problem-C ..??

  • »
    »
    11 лет назад, # ^ |
    Rev. 7   Проголосовать: нравится +20 Проголосовать: не нравится

    the idea is the following

    lets take an example (* denotes lighted bulb)

    1 2 3 * 4 5 6 7 * 8 9 10

    you can divide this into sub problems. The idea here is to find the number of ways to switch on bulbs on both side of a * and merge the result. One more thing, for any sub problem like * 1 2 .. n *, the answer will be 2^(n-1) (i leave that to you).

    Now, traversing the *s

    1 2 3 * 4 5 6 7 * 8 9 10

    for the first * , there are 3 bulbs And when treated independently, there is only one way to switch them all on. But for 4 5 6 7, the number of ways to switch them on when treated alone is 2^3 = 8. How do we merge this result? Notice that any solution for the sub problem {1 2 3 * 4 5 6 7 *} will be composed of a possible solution of {1 2 3} and a possible solution of {4 5 6 7}. To put it simply, if a solution is (3,2,1) and another (4,5,6,7), the final solution will be a tuple made from these two solutions with their ordering preserved (for two tuples of size n and m, there are C(n+m, n) final solutions). The ans = 1*2^3*C(4+3,3)

    for the second '*'

    we have the number of solution for the previous 7 bulbs, and there is only 1 way to switch on {8 9 10}. Thus

    ans = ans*1*C(7+3, 3)

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

I think it would be better if someone from div.2 (or <=1750) tested it also.

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

А кто такой Шаасс?

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

Thanks for quick change of rating. :-)

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

У кого-то было ВА8 по Е, я без понятия..

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

http://www.codeforces.com/contest/294/submission/3482847

I tried to hack this code for input

1 10 1 1 5

I think this code got RTE but hacking attempt was unsuccessful! why why why???

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

A bug?

In my rating graph, the 2 points before today's contest seems to be swapped!

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

Почему в задаче Б не работает жадность по возрастанию величины w[i]/t[i] ?

Ведь по сути, переставляя одну книгу на верх, мы улучшаем ответ на t[i] за счёт потери w[i]+t[i] свободный длины, то-есть мы платим 1 + w[i]/t[i] за каждую единицу сэкономленной толщины. И тогда, очевидно, чем дешевле мы набираем эти единицы, тем больше мы их сможем набрать. И так как у нас t[i] может быть только 1 или 2, не может быть ситуации, когда нам выгодно взять несколько книг по большей стоимости за единицу толщины, чем одну по меньшей, за исключением самой последней книги, которую мы берём.

Ну и вот собственно такое решение валится на 20м тесте: 3490641 . Мб в моей реализации что-то не так, а не в алгоритме?)

upd. Всё ясно, не хватало лишь проверки последней взятой жадностью книги, так как если её толщина равна 1, то её может быть выгодно заменить на более дорогую с толщиной 2. 3490773

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

    Объяснить не могу, зато могу дать тест:

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

      А как её правильно решать?

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

        Я сдал тупой рюкзак за куб, в чужих исходниках видел выбор i книг с толщиной 1 и минимальной шириной, j книг с толщиной 2 и тоже минимальной шириной, с проверкой допустимости такого выбора.

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

          Можете поподробней про рюкзак? Это была первая мысль, но я её успешно отбросил.

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

            Пусть мы могли расставить первые i книг так, чтобы ширина нижнего слоя была равна ii, ширина верхнего слоя — jj (при подсчете динамики допустим, что jj может быть больше ii). Тогда мы можем поставить текущую книгу вертикально (переход в состояние dp[i + 1][ii + t[i]][jj]), либо положить ее горизонтально (переход в состояние dp[i + 1][ii][jj + w[i]]). Потом, в самом конце, выберем среди всех возможных dp[n][ii][jj] такое, что ii будет минимальным, а jj не будет превосходить ii.

            Короче, лучше почитайте мой код :).

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

      Осознал, спасибо.

      У меня не хватало лишь проверки последней взятой жадностью книги, так как если её толщина равна 1, то её может быть выгодно заменить на более дорогую с толщиной 2.

      Теперь всё ок: 3490773 .

      Спасибо=)

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

for problem D,what does the following sentence mean? "The robot stops painting the first moment the floor is checkered. "

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

Problem D was harder than usual, at least for a div 2 contest.

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

Finally at the end of the contest I must say that you are not "Untitled" but titled to organise a div 1 contest also :)

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

Great contest.Good luck

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

Is the editorial out?

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

Первая идея с сортировкой на B не прошла, как тока собирался сдать новое решение, сеть с интернетом пропали. P.S. новое решение проходит.

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

The problem set seems to be A D D E E... But I enjoyed it!

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

Another time, an unrated user won the contest!

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

Nice contest Thanks ;)

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

Nice contest :) waiting for the editorial eagerly...

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

You don't want to publish tutorial?

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

Hello Everyone, Can anyone explain me the solution of the problem B of this contest. I am completely confused after reading some of the comments here as they suggest to check all the combination of the numbers to get the minimum value, where from the condition given in the problem appears to be very straightforward to sort with widths and collect first few as horizontal and the rest of others as vertical, but there code show that they try to check all the combination but actually they does not check all of the combination actually and got correct answer. As the description of the problem and the comment does not clear here to me, I beg your help to understand me the problem with the code.
Thank you!
This goes said that it check all the combination but actually it does not :(
http://www.codeforces.com/contest/294/submission/3486814
where this is my solution
http://www.codeforces.com/contest/294/submission/3487146

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

    That solution does the following: initially tries to put vertically some books with thickness equal to 1 AND some books with total thickness equal to 2, then tries to put horizontally all the books with thickness equal to 2 and some books with thickness equal to 1, then, finally, tries to put horizontally all the books with thickness equal to 1 and some books with thickness equal to 2.

    An alternative solution with dynamic programming: Dp[i][j][k] — 1 / 0 if you can obtain from the first i books a total thickness of the vertical books equal to j and a total widthness of the horizontal books equal to k. When you want to add a new book, you can put it vertically or horizontally. In the end, you have to find the smallest i with at least one value equal to 1 from Dp[N][i][j], j <= i.

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

    I think this probblem can use One-zero backpack. http://codeforces.com/contest/294/submission/3485742

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

when we can meet shaass again?!?

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

Эм, может я чего-то не понимаю, но, по идее, в блоге должны были появиться результаты? Или где их можно посмотреть?