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

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

Всем привет!

Приглашаю вас принять участие в Codeforces Round #253, который начнется в четверг 19 июня в 19:30 MSK. Раунд будет проходить в обоих дивизионах.

Это мой первый раунд Codeforces, и я надеюсь, что вам он очень понравится!

Большое спасибо Gerald за помощь в подготовке раунда. Также хочется поблагодарить MikeMirzayanov за создание удобной платформы для проведения соревнований. Также благодарю тестеров этого раунда: antonkov, Aksenov239, VArtem, subscriber, niyaznigmatul. А еще Delinur за перевод условий на английский.

Не пропустите шанс получить удовольствие от решения интересных задач!

UPD. Распределение баллов по задачам:

Div1: 500-1500-1500-2000-2500

Div2: 500-1000-1500-2500-2500

UPD2. Соревнование завершено, всем спасибо за участие!

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

1) tourist

2) scott_wu

3) stevenkplus

3) gs12117

5) GlebsHP

А также победителей Div2:

1) tafit3

2) thnkndblv

3) MIT3

4) lucaslima

5) liuzhijian

Особенно хочется поздравить tourist, единственного, кто решил все пять задач, а также единственного, кто решил задачу 442E - Гена и второе расстояние!

Разбор задач уже опубликован.

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

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

Early announcement, thanks for this!

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

    Early announcement --> more up-vote!

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

      Comment regarding Early Announcement --> more up-vote!

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

        Comment regarding "Comment regarding Early Announcement --> more up-vote!" --> more up-vote! :D

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

          It's too hard to write something funny. So just down-vote me pls.

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

          Why you down-vote me? Can't we make fun a little? :(

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

            That would have led to an infinite loop :(

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

              Actually my last comment have '37' down-vote. So anyone doesn't say "Comment regarding bla-bla-bla --> more up-vote!" :D

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

            Repeating jokes usually aren't very funny, especially if they're formed by repeating someone else's joke.

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

    is it always necessary every time when the auther makes an early announcement someone writes a comment saying "wow early announcment"

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

Hope we all get good grades

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

    why so many down?

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

      Maybe because programming contests aren't school, so there are no grades? (So it's a completely off-topic/spam comment.)

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

      I think because he used "grades" instead of "ratings". Note that similar comment from the same person with correct word has been accepted AC.

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

          Consider the case when all participating users rank exactly according to their rating before the contest, and all participants were specialists initially. Then, since the participant has not been 'overtaken', his rating should not decrease.

          All constructive ideas, comments and clarifications are welcome.

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

        Well now i think it is because the probability of her hope being fulfilled is 0.000000000. Proving it is a good exercise of mathematical reasoning.

        Please think that whether you wish is theoretically possible. That comment is down voted mainly because it was intended towards just commenting.

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

Hope rating++~~~ Enjoyable contest in Codeforces becomes one of my daily life~

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

    agree. It becomes one of my daily life :)

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

    me too,I really enjoy it,espically when my rating gets higher :)

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

      Me too! I really hope improve myself and get the higher rating :)

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

        me too. Rating up and down here, so enjoyable!

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

          This is the second : tending to infinite loop in this page.

          I dont want that every user comes here and contribute like this.

          So, I hope this will break the flow :

          break;

          This comment does not wish any replies as then the brake will fail.

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

The final exam is approaching.But It is always enjoyable to have a codeforces round.Hope all the participant can enjoy the round.

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

The same day with TopCoder SRM 625.

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

Thanks god there is no worldcup match that time!

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

Too many contests in the days of the exam , I hope there will be that much in the holiday =)

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

Too many contests in the exam days , hope there will be that much in the holiday

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

Expecting the problems to be based on footballers / football :)

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

Hope your first Codeforces Round will success and the problems are diversity and useful for everyone

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

hope everyone get higher rating !

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

    I hope not. It would mean that there's something seriously wrong with the rating system, not to mention it'd be boring.

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

Last Codeforces round before ACM ICPC World Finals! (or not?)

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

    I think it is yes for Div1 , but it is not necessary to stop Div2 contests during the World Finals

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

Waiting for ur problemset !!

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

last few contests users ask why problem writer write "score distribution will announce later"
but here score distribution not mentioned at all he didn't say later or mention it.

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

    I see very little point in writing "scrore distribution will be announced later" because it doesn't give readers any new information :)

    Of course as early as we dicide everything about score distibutioin I'll add the information to the post.

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

      orly? That phrase is at least more informative than this one: "Don't miss a chance to have fun of solving interesting problems!"

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

I am a new member of codeforces.. I wuld like to know regarding the concept of div 1 and div 2 What are they?? and in which of them do I belong ?

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

    Any new contestant by default belongs to Div2. If you do good, and your rating increases over 1700, then you will be promoted to Div1. The rest you will figure out once you start participating regularly.

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

Стремно как-то писать первый див. 1 раунд))

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

Hope I will make it to first division! It's the first time I am so close. Only 31 points...

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

Looking forward to the codeforces round and the WC match after the contest between england and uruguay

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

Can anyone explain what is meant by the score distribution Div1: 500-1500-1500-2000-2500

Div2: 500-1000-1500-2500-2500

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

    There will be 5 problems and maximum points for each individual problem are 500-1500-1500-2000-2500.

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

Had a really great performance Topcoder SRM 625 a few hours ago ... hoping for same (or maybe better) performance in this codeforces round! GL & HF everyone!

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

Please can anyone upvote/downvote my comment ? I want to see what kind of notifications we get when our posts are upvoted or downvoted .

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

I'm a new contestant of codeforces so div 1 or div 2 which appropriate for me... ????

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

Does Div2 B have 1500 or 1000 points?

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

I really don't understand C div 2 problem statement and examples!!!

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

Can someone explain div2 B problem ?!

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

I feel like I just took out my hack interest over the past 2 years... +4 mfw

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

Problem B Div2 was harder than usual! I also think D div2 was easier than C! Because it had more pretest passed submissions!

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

Very Hard Contest O.o , C — no idea, D-I hate statistics homeworks , E — wow what a problem, but no idea :(

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

Правильно ли я понимаю, что в div. 1 C оптимальная стратегия — жадная, нужно лишь её правильно реализовать? Если да, то как, если нет, то как следует решать задачу?

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

    Все мои жадности не прошли стресс с решением за O(n3)(задача о перемножении матриц).

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

      Можно подробнее о перемножении матриц?..

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

        Есть классическая задача. дано n - 1 матриц со сторонами aixai + 1 у i-й матрицы. за какое наименьшее время их можно перемножить. получаеться полный аналог задачи div1C но вместо min(a, b) пишем a * b * c, где c — выкидываемое число.

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

        dp[L][R] — ответ для подотрезка с L до R и крайние числа удалять нельзя.

        Переберем число M (L < M < R), которое удалим последним. Тогда это принесет нам min(a[L], a[R]) + dp[L][M] + dp[M][R]. Выберем максимум по всем M.

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

          Вот и я придумал такое же решение, а как справиться с тем что не умещается по памяти? Ведь (5 * 10 ^ 5) ^ 2 * 4 байт не умещается?

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

      У меня зашла жадность — если есть локальные минимумы, то брать их, иначе брать элемент с максимальной стоимостью (т.е. за который дадут больше всего очков).

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

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

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

          Да, если строгий, то WA10. Спасибо претестам, которые это ловят — иначе я получил бы вместо -105 примерно... -105 :D

          Внезапно оказалось, что это решение вообще за линию и пишется в несколько строчек: 6924410.

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

Гена сдал задачу про себя (E). Причем оказался единственным.

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

How do you solve Div.1 B ? I see lots of people have solved it. I myself submitted something that will definitely get TLE on system testing. The solution eludes me. :/

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

    sort by decreasing values and greedy algorithm

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

      Can you prove this solution?..

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

        The editorial's up, and the solution's there. Key idea of the solution: if a set S has , adding p to it increases the result proportionally to p (so we want to add the largest p).

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

    dp[i][j], i — all taken count, j — last taken

    for (int j = 0; j < n; ++j) {
      d[0][j] = p[j];
      no[0][j] = (1 - p[j]);
    }
    for (int i = 0; i < n; ++i) {
      for (int j = i; j < n; ++j) {
        for (int k = j + 1; k < n; ++k) {
          double x = d[i][j] * (1 - p[k]) + no[i][j] * p[k];
          if (x > d[i + 1][k]) {
            d[i + 1][k] = x;
            no[i + 1][k] = no[i][j] * (1 - p[k]);
          }
        }
      }
    }
    
»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

[ Deleted ]

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

Editorial please...!

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

Скучаю по взломам(((

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

I hope system testing and rating update come quickly

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

Hard contest...please give editorial soon.

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

Интересные, но ОЧЕНЬ сложные задачи. я так ничего и не решил((

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

    Нормальная тема для "я первый раз в Див 1" :-)

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

    С точки зрения сухого рейтинга ты гораздо более в выигрыше, чем те, кто решили одну.

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

Не понимаю, как А div. 2 пустили на контест. Совершенно безыдейная задача.

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

    Вроде как уже долгое время div2 A — безыдейная задача.

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

    Не понимаю, как кацапов вроде тебя пускают на контест?

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

Давайте пока разбора нет, я спрошу про Е (див 1). Можно ли ее решить перебором одной вершины (которую выкидываем), для оставшихся точек строим диаграмму Воронного, по диаграмме находим точку внутри прямоугольника, самую дальнюю от оставшихся?

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

Problem C (div2) is hard to understand.

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

Can anyone give me solution for problem D div2 ?

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

Can anyone give me solution for problem D div 2?

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

the system testing is very quickly! good

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

Сегодня кацапня победила меня, но я еще вернусь и покажу кто на цф-е альфач!!!!

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

Как решать задачи, не зная, как их доказать:

0. Видим, что все сдают, паникуем.
1. Пишем жадное решение.
1.1. Вспоминаем о контестах, когда надо было дополнительно посортить массив, чтоб заработало.
2. Сортируем.
2.1. Упс, не прокатило.
3. Ну тогда сортируем и разворачиваем.
4. ?????
5. PROFIT!

А если серьёзно, как доказать, что такое (6920862) решение всегда даёт правильный ответ?

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

    Читай разбор, там написано:)

    Отличный способ решать задачи=)

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

      Я ещё ради интереса в середине контеста посмотрел в див. 2, а там 200 прошедших претесты D и всего 13 C... Да, это был день полный новых впечатлений.

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

    Впервые, упоминание подобной методики увидел на алголисте:

    В программистском фольклоре можно найти упоминание об "американской методике решения задачи", состоящей в следующем:

    "Если у Вас есть задача, и Вы не знаете, как ее решать, то от сортируйте входные данные — может быть это Вас натолкнет на дельную мысль".

    http://algolist.manual.ru/olimp/poi_sol.php

    С тех пор часто к ней прибегаю =).

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

      Думается мне, что нужно намешать эти методики и выдать свой ТРИЗ с блекджеком и шлюхами)

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

      Напомнило

      Ну ты пока что напиши здесь какой-нибудь бинпоиск, а я за это время попытаюсь придумать нормальное решение...

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

Damn, why TL in D was so strict :/? My O(n log n) failed and I ended up on a 171st place instead of in TOP20 :/. Moreover, I wasn't the only one. There are many failed submissions because of TLE.

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

    Same here. Got TLE for pascal solution 6921143. The same code receives AC in 390 ms on Delphi: 6923185.

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

    Our Java solutions work something like 500ms... I don't think 4xJava solution time limit is strict.

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

      Are you sure? This is ~1/3 of all submitted solutions during contest.

      (Edited picture, thanks nic11)

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

        Maybe

        <img width="100%" src="blablabla">
        
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        You can post the pic in HTML, you can resize there.

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

        You can look at Aksenov239 solution: 6923989, or mine 6923978 with classes and recursion. Both of them work quite fast.

        If you can't see this submissions, you can view it on pastebin: mine and by Aksenov239.

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

          I don't know exact shape of testcases, but solution described in editorial does something like "do something until something" which can be estimated by O(n log n), maybe maxtests where easy cases where your solution worked faster? My solution works offline and takes teta(n log n) time and I'm not using anything which can make constant to significantly grow like set or maps. My space complexity is also O(n log n), but that shouldn't be the case. Is there anything really stupid I'm doing, which was a reason I got TLE http://codeforces.net/contest/442/submission/6917926 ?

          And one more question — what is the point of setting such big constraints? Will anybody get hurt if n<=10^5 instead of 10^6? I guess not.

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

            We have maxtests on which model solution works teta(n log n). Setting smaller limits always increases chances some solutions with wrong complexity pass.

            But I'm really sorry that I forgot to include a maxtest in pretests.

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

              Sometimes, it's impossible to make sure just all solutions with good complexity pass. As was clearly the case here...

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

            I'm glad that swistakk solution got TL. And I will get hurt if coders like swistakk take top20 place.

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

              Lol, that's pretty rude :P. I guess this is my award for whining about TLs while I should be grateful for preparing contest, but you know, receiving TLE in solution with optimal complexity (especially those without any complicated data structures) is always frustrating :P

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

              Would you also get hurt if coders like me get second place on ACM ICPC WF ( ͡° ͜ʖ ͡°)?

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

        I got TLE because I stupidly used heap to maintain 2 maximals and use cout to output.

        I think the TL is fine, but it would be better to add maximal test case in pretest so we will know the code is not optimal enough.

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

      Hm, I got AC after changing vectors to arrays (and 1e6 to 1e6 + 5 :P). I guess what's taking most of the time is doing n resizes to 23 and 23n resizes to 2 :P. I was also really close to exceeding memory limit (230 out of 256MB). Allocating that amount of memory is slower than I wanted it to be.

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

Поразительно похожие посылки у двух участников сразу по двум задачам: по С 6919815 и 6919490, D 6921687 и 6921824.

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

My solution of D div2 failed in test case 5 because i didn't use setprecision :(

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

I feel that to give credit to the right technique for problem B (div1), the constraints should've been such that n <  = 105

P.S.: After sorting the array of probablities, I just used a naive test-all-subarrays algorithm which passed.

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

    Your O(N2) Solution couldn't pass N = 105 ;)

    Anyway , I see the O(N) solution, I think 100 has been chosen nicely by author ... cause nobody have 105 firends who set problem !!!!

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

      Mike Mirzayanov? :D

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

      "Your O(N2) Solution couldn't pass N  = 105 ;)"

      -- This is precisely why I said that the constraints should be increased. I did not find the O(N) technique and was still able to solve it.

      --I don't even feel like replying to what you wrote later on man. I'm out.

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

А когда мне рейтинг добавят, ребят? Ура! Я блакитный!

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

Ого, я до сих пор оранжевый. Когда потерял на А 20 минут, т.к. написал в одном месте > вместо >= и потом вообще не имел идей по В, думал, что пришло время возвращаться домой в фиолетовые.

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

    Красавчик, бро!

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

    А тут ничего так :-) У меня серия — второй контест подряд косячу сортировку массива.

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

    Да ладно, ты-то фиолетовый? Ты ж пишешь статьи о сложных структурах данных.

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

Div1 — B I got wrong answer at test 17.

only for this line : printf("%.10lf\n",1);

Some of you will be amused to see the output

my WA code

my AC code

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

When I passed pretests on Div. 2 B, I thought I was the luckiest guy in the room(I was just playing with the code and it started giving right answers :D). Didn't pass the systest though...

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

Can someone suggest a book to study algorithms please? Which books did you use to learn them? Both Russian and English ones are acceptable ;)

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

Hi, In Div 1 — B I got wrong the case #31, however when I run it locally it works fine and give the correct answer. Does somebody now where may the problem be?

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

    Have no idea why that is a problem, but after doing the following, it worked:

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

      Thanks, I had always though that double and long double were identical in GNU C++!. I find rather surprising the huge difference between the result in one case and in another. Well next time I'll use long double if I can remember it!

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

        You're welcome.

        But have you got any clue to why the output is like that when using "double"?

        And the more weird thing is this. I don't think it's a mere precision problem (not sure): http://ideone.com/31XMxJ

        Anyway, I haven't looked carefully at it yet. Will probably do that on Sat. isA.

        And something that may help explain the reason but haven't tried before is checking the assembly code outputted from the compiler. But of course, don't forget to use the same compiler & compiler flags as theirs. (Sorry if it's a noob note, I'm a little nooby so I assume everyone is like me :D)

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          But have you got any clue to why the output is like that when using "double"?

          More or less I have finally found it. It has something to do with he -O2 flag it seems to handle some comparisons in a different way, I suspect that it doesn't save mx to memory so it uses a value with more precision (long double?), which is lost whne saving to memory. The question is that the order in the priority queue is changed. But now for equal values of the first parameter the queue gives the result in reverse order which is wrong.

          Possibly in your ideone output, when printing the output mx is saved into memory and that affects i's precision. (Well is an hypothesis)

          So it is a bug in my code. That's good I don't want to lose my faith in GCC !! :-)

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

    Yeah can some one tell me what is wrong with his solution?

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

В Div1 вначале во вкладках с условиями сбоку отображалась неправильная разбалловка, потом в какой-то момент она стала правильной (когда мне пришлось обновить вкладку с задачей где-то в середине контеста), вот пруф

Номер раз

И номер два

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

    Более крупно, если нужно: раз, два

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

    так там всегда данные обновляются после обновления страницы

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

      Речь о том, что на первом скриншоте у В макс стоимость 1000.

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

        Ага, а у D -- 2500. Короче, вначале была разбалловка второго дивизиона

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

    В div2 тоже какое-то время разбалловка была неправильной. Помню, что за B и C было написано 1500.

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

Почему это (6916735) правильно?

В частности, вот это:

if(SZ(s)<=k){
    if((l+k)&1) cout<<(l+k)-1<<endl;
    else cout<<(l+k)<<endl;
}else{
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Потому что если длина строки меньше, чем количество символов, которое можно добавить, то в ответ можно включить всю строку + еще сиволы. Ибо именно ты решаешь, какие символы добавить.

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

Div1B / Div2D решается за линейное время http://codeforces.net/contest/443/submission/6928411, мне кажется ограничение N <= 100 слишком маленькое, вполне можно было сделать побольше.

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

I have some understanding problem about div1 D. About the 2 conditions, what I think are:

  1. All the colors of edges connected with the same vertex does not show up more than twice.
  2. If vertex i has an edge colored C, vertex j!=i has an edge colored the same C, then the path between i and j are all colored C.

Am I understand the 2 conditions right? And how does these 2 conditions affect the problem ? Thanks.

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