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

Автор Edvard, история, 8 лет назад, По-русски

Привет, Codeforces!

13 июня 2016 года в 19:00 MSK состоится очередной тринадцатый учебный раунд Educational Codeforces Round 13 для участников из первого и второго дивизионов. С прошлого раунда прошло почти два месяца. Столь долгий перерыв связан с несколькими обстоятельствами: 1) в конце апреля я координировал обычный CF-раунд; 2) после этого был месяц, когда большая часть сообщества СП (включая меня) была занята подготовкой и участием в ACM ICPC WF; 3) наконец, в начале этого месяца я начал работать в компании AimTech (надеюсь у меня по прежнему будет достаточно времени, чтобы готовить учебные раунды).

<Стоит хоть раз почитать то, что здесь находится, вдруг есть что-то интересное или ошибки может>

О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.

Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день, в течение которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.

Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.

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

</Стоит хоть раз почитать то, что здесь находится, вдруг есть что-то интересное или ошибки может>

Комплект задач был предложен участниками сообщества. Задачу А предложил Әбдірахман Исмаил bash. Задачу B прислал Артур Яворски KingArthur. Задачу C предложил Sheikh Monir skmonir. Задача D одна из большого количества задач присланных Zi Song Yeoh zscoder (и их ещё много осталось). Задача E была предложена и полностью подготовлена Алексеем Дергуновым dalex: её я хотел взять ещё в прошлый раунд, но она оказалась сложноватой для задачи D. Наконец, упрощённую версию задачи F предложил AmirMohammad Dehghan PrinceOfPersia (я её несколько усложнил).

Благодарю их и всех кто присылает задачи! Количество, присланных, но ещё не использованных задач постепенно растёт. Если я нигде ничего не потерял, то я уже ответил всем кто прислал мне задачи более 5-6 дней назад. Прошу с пониманием отнестись в случае, если ваша задача долго не появляется.

Как я уже говорил задачу E подготовил Алексей Дергунов, остальные задачи для вас подготовил я (Эдвард Давтян). Спасибо Татьяне Семёновой Tatiana_S за проверку английских текстов условий. Задачи вычитывали и тестировали пользователи, предложившие их, соответственно Әбдірахман Исмаил bash, Артур Яворски KingArthur, Sheikh Monir skmonir, Zi Song Yeoh zscoder, Алексей Дергунов dalex и AmirMohammad Dehghan PrinceOfPersia. Большое им за это спасибо!

На раунде вам по традиции будет предложено шесть задач. Надеюсь они вам понравятся! В прошлый раз я немного неудачно подобрал комплект и он оказался чересчур сложным. В этот раз я решил исправить это. Задачи будут проще обычного.

Good luck and have fun!

Это, кстати первый летний раунд :-)

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

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

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

Это, кстати первый летний раунд :-)

Но ведь #355 и #356 тоже были в июне?

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

    Я говорил про учебные раунды. Это вообще самый первый летний учебный раунд.

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

Where is Delinur?

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

    They don't need her since Edvard is a native Russian speaker and he also knows English (obviously!) and Tatiana Semyonova has checked English statement.

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

      Usually I'm translating the problems by myself (it helps me to improve my English) and the interpreter (Maria and now Tatyana) just checking the problem statements and making fixes.

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

        Interpreter — это тот, кто устно переводит. В данном случае наверное надо было использовать translator. By нужно убрать перед myself. Дальше у вас со временами все перепутано

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

    Actually, Maria left the project, she asked to convey greetings and best wishes to all people on Codeforces! Tatyana Tatiana_S Semenova agreed to help us with English :-)

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

Couldn't give the previous one....had been waiting for this one for long! Excited! Hoping for a matrix exponentiation problem...I never solved it in a contest!

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

"It's the first summer round"

No here, I'm freezing

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

Читаю анонс к educational только ради нового сообщения в угловых скобках :D

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

UPD2. Здесь по ошибке был вопрос про другой контест.

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

    Это про марафон? Тогда можно прочитать там readme, а если всё ещё не получится — задать более конкретный вопрос. В соответствующем посте или через интерфейс соревнования.

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

      Ох, извиняюсь. Промахнулся постом. Читал про оба контеста и в итоге не к тому написал.

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

I know this if Off topic. But Believe me, my rating was 1905. Any changes in rating system?

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

Is this round being delayed for 10 minutes?

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

Интересно, какие могут быть причины переносить нерейтинговый контест? С разбалловкой не договорились?

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

    Уверен любой человек хоть раз проводивший контест или готовивший задачи на контест знает как минимум 10 причин для переноса контеста. И это никак не зависит с рейтинговостью контеста.

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

      Но, судя по большинству контестов, у авторов как-то получается решать их вовремя, правда?

      Уверен, не у одного меня восьмая серия игры престолов лежала несмотреная. :)

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

        Этот контест можно включить в список большинства потому, что он был готов ещё вчера и оставался без изменений сегодня. Но причины переноса начала могут быть совершенно разными. Я никак не понимаю причём тут рейтинговость контеста: типа нерейтинговый контест пофиг можно бажным выпускать?

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

          Тем не менее, уже второй комментарий эти причины не озвучиваются, а я ведь не готовил контесты, мне не стыдно о них не знать :)

          Я никак не понимаю причём тут рейтинговость контеста: типа нерейтинговый контест пофиг можно бажным выпускать?

          Не в бровь, а в глаз! Нет, конечно, без дебагнутого чекера взломов в F контест и 10 минут бы не продержался, и пусть 2.5к человек подождут :)

          Рейтинговые контесты имеют последствия в виде рейтинга, а нерейтинговые — нет. Можно понять, когда из-за ерунды переносят рейтинговые. А тут получается дилемма: либо вы напрасно перенесли контест и спустили 2.5к * 10 / 60 = 416 человекочасов, либо набажали настолько, что не смогли запустить. Без обид, но ни то, ни другое вам чести не делает :)

          При этом за сам контест большое спасибо.

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

            Во-первых перенос контеста никак со мной не был связан: я сам удивился когда это увидел. Во-вторых если вам пофиг на нерейтинговый контест, то можете не писать последние 10 минут контеста, если его перенесли.

            А причины бывают разные: 1) повис сервер: к моменту начала контеста нагрузка возрастает в кратное число раз; 2) за 20 минут до начала авторы сделали правки и судорожно их проверяют; 3) вследствие правок нужно пересобрать пакеты задач: это может занимать несколько минут; 4) некоторые пользователи могут жаловаться на неработающее что-то; 5) к началу контеста оказалось, что собранные пакеты почему-то не заливаются; 6) надо почистить кеши, перезагрузить инвокеры/сервера, чтобы на контесте неожиданно никакой SSD-ник не переполнился и ничего не упаало и т.д. Я сам регулярный участник контестов и мне тоже не нравится, когда его переносят. Но могу заверить, что единственной целью переноса является качественное проведение контеста и максимум фана для участников.

            P.S.: Что такое "дебагнутый чекер взломов"?

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

              Но я и не говорил, что он лично с Вами связан :)

              P.S. Мб он называется валидатором взломов. То, что бракует взломы, от совсем некорретных до не совсем корректных.

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

Well, I know what is needed to solve F and I also know that I can't code it so I quit, good luck! :D

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

    Can you tell what was the idea behind solving F??

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

    That's why you're purple. I used to had this "well, it's obvious this problem can be solved by persistent 2D segment trees with heavy light decomposition built on linkcut trees, hire monkeys to code it for me" and walk away proudly for coming up with such a 'brilliant' solution, but I discovered that's not the way one should follow. In half of cases it turns out such problem has some nice tricky solution using very simple techniques and in half of cases it turns out solution is in fact what I thought, but still a lot of people have no troubles with implementing it which is a sign that I should definitely improve my coding skills in that area. Treat contests (especially educational rounds) as opportunities to learn not just the place where you solve problems which you already know how to solve.

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

      After becoming red approach changes, right? :p

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

        Looks like he hired monkeys to code it for him, or coded all the stuff like a monkey himself.

        This way he can be smart in the discussion:

        • Yes, think carefully about nice and tricky ideas and maybe you can become red (like me) someday.

        While copy pasting ton of stuff on every problem in 2 minutes, get the whole problemset done in 10 minutes and red color very quickly :P

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

          I didn't want to say "I invent tricky ideas, so I am red", I wanted to say "Stop giving up, that is not the right way to progress" and "Sometimes appropriate way to solution leads through tricky ideas and sometimes it leads through fighting one's weaknesses with coding something, and surely it doesn't lead through being satisfied with coming up with complicated solution". "I am not able to do this, so I won't even try" attitude is the worst way to improve your skills.

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

        What I said here and copying prewritten code are kinda irrelevant. "hire monkeys to code it for me" was the key part. Main point here is that one definitely should not treat coming up with solution as all the logical difficulty and implementation as dirty duty one can omit and be satisfied (as I used to on high school). Another thing is that as long as code is prewritten by me and contest rules allow me to freely copy-paste it then if it helps me getting fast AC I feel the right to be fully satisfied with it — such scenario is rather the exact opposite to scenario of getting no AC at all which we are talking about.

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

          Edit. The reply should be to your upper comment. I got confused by the comments tree :)

          My comment refers to "That's why you're purple".

          Basically it suggests that red coders either find a nice and tricky idea or have such a good coding skills that can implement a complicated idea quite fast. Which means red coder = very smart or skillful and not red = !(smart or skillful) = !smart & !skillful.

          You forgot to add that you also use additional approach. You got such a huge library, because of spending a lot of time on problem solving and practicing/participating in many contests, that you can just copy-paste most of the complicated stuff.

          This changes things a lot as it means red coder = ((1) very smart or (2) skillful) and (3)having a lot of practice and a lot of libraries.

          And in this case not red means !(((1) | (2)) & (3)) so smart and skillful meets that criteria.

          This was example of discrimination by cf color. I don't know why do you think that once you are red, you can treat not red as somehow worse and less talented.

          I think that being high rated in short competitions really means 2 things:

          • you are extremely smart

          or

          • you can afford to spend tons of time on participating in the contests and solve a lot of problems 12 hours per day. This way you can become a really skillful and have enormous library of code, which gives you additional advantage in such type of contests.
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Maybe "That' why you're purple" was oversimplification, because at any point I didn't want to address the actual smartness or abilities to code some particular thing, so I would like to cut out part of the discussion regarding to being smart, having a lot of practice, having developed library etc. which are of course important factors of someone's colour, but they were not what I was going to point at what may have been a reason for a little misuderstanding.

            Only thing I wanted to focus on was the attitude when facing problems. From my own experiences I can say that difference between purple me and red me is surely also a lot of practice, but also very importantly revolutionizing my way of thinking. No matter of someone's current abilities to code and smartness, "I am not able to do this, so I won't even try, good luck" attitude is a place for severe improvements (no matter whether "I am not able to do this" part relates to coming up with solution (which connected with "so I won't even try" never has been my point of view) or coding a solution (which was exactly exactly very often my point of view in past and I am not happy with this, but fortunately it is no longer the case)). My initial comment's main purpose was in fact to be a purely motivational one.

            Btw on a completely irrelevant note, you made it seem like copying prewritten code is essential part of today's competitive programming. In fact (apart from template) I copy some codes from library in approximately one in 20 problems.

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

            My personal red experience is that "whatever you say can be used against you", that is, no matter how careful you are, something you say is going to be perceived as arrogant by someone (hell, some people told me they thought I was arrogant before they had the chance to talk to me!). So I'd say at least a large part of this discrimination you mention can be attributed to the lower-rated contestants themselves.

            That being said, here's a simplified version of Swistakk's statement:

            "Programming contests consist of coding and implementation, so if you want to be a very good contestant you need to practice both, not only one of them".

            Sounds like really good advice to me (and I should follow it more often, my implementation skills are crap)

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

      Could you givgive an example of such a problem (requiring all techniques you mentioned)?

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

what is wrong with my code it is failing on test 5 http://sprunge.us/iFNf? THe code is for problem D.

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

That N = 1 case in E. -_-

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

How to solve problem E?

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

    i think dynamic programming, like hamiltonian cycle but im not sure, i couldnt make it pass test 4

    http://codeforces.com/contest/678/submission/18433012

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

    I tried DP, but its complexity is bad.

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

    You need to find an order which maximizes your probability of winning. This is a standard Bitmask DP.
    My solution : code

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

      What to search for to get this standard dp problem?

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

      Your code is a little messy , so can you tell me the DP states you used?

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

        Lets define DP[mask][prev_winner] as the max probability such that we have covered people in mask and prev_winner is our winner.
        Now we try N * (N — 1) possibilities for first 2 position and try to find the max ans.
        Transition is :
        if prev_winner = 0:
        DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner]) for all i's which we have not seen.
        else:
        DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner] + prob[i][prev_winner] * DP[mask | (1 << i)][i]) for all i's which we have not seen.
        I hope this helps.

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

          Now we try N * (N — 1) possibilities for first 2 position and try to find the max ans.

          I thought we have to consider two disjoint subsets and use their maximum values for the union of these subsets. I can't prove why we only need first two positions. I'm missing something very obvious, possibly.

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

          I don't understand these formulas:

          "DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner]) for all i's which we have not seen."

          It means that in order to cover people in mask you look at all the masks with one more people, you ask what is the probability that 0 will win among all these people and then you calculate the value for the mask with the smaller amount of people. It looks like your final state is dp[0][0]?

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

            Final state for DP is dp[(1 << n) — 1][0]. I add one more person into mask and ask what is the probability that the person I want to win is the winner. And I split the dp based on whether I have seen 0 or not. So above formula is for the case when I have seen 0 (what is the probability that 0 is the winner when I add one more person into mask). Other formula covers the second case as both of them can win.

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

        A simple way is to set dp[mask] = best probability for Ivan to win among people with bit=1 in the mask.

        18433677

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

          How do you prove that only mask is important? I believed that the last winner is also important, but stress-test of your solution says that it isn't.

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

            I choose two fighters to move between dp states, maybe this confuses you.

            So basically for a given mask we can independently get the best probability of Ivan to win. To compute this, we take maximum over all possible choices for next fight (choice of two fighters, possibly including Ivan).

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

              That's a nice solution, but it is very magical for me.

              If you choose the last 2 people it is against the rules, as you can choose only 1 last person.

              So if you are going to choose the last 2 people (i,j):

              • Ivan had to win in the mask without j, so now you multiply that by the probability that i beats j (and we know that i already got beaten by Ivan, so Ivan beats the whole new mask this way).

              or

              • Ivan had to win in the mask without i -> the same logic holds.

              I don't know how do the people come up with such ideas, but is there a way to do this problem more straight forward?

              Like you have the probability dp[mask] that Ivan wins the mask or dp[mask][winner] that winner wins the mask and you are selecting one player in each move?

              Despite being more straight forward, that solution would also reduce the complexity to O(n*2^n).

              Edit — it will reduce the complexity only in case with dp[mask] state.

              Edit2. Now I see that you are not choosing the last fight, as you can't do that. Ivan has to fight the last fight in each mask. You are choosing the best fight among all possible fights within the mask and you take the sum of 2 different outcomes of it. It is more clear now.

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

                Actually now I realized that I forgot that the winner from the last fight has to be chosen. That is, my solution assumes a tournament, where there are multiple fights with elimination in parallel.

                So I solved a different problem and that's why the solution seemed clear for me (and unclear for others).

                It is quite strange that this got AC.. Maybe it could be hacked? Though, intuitively, it would fall on large random tests, which I assume already exist in the set.

                Maybe this works because the strategy from the problem is indeed optimal? :)

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

                  Your solution works because:

                  dp[mask] = maximum probability that Ivan wins the mask.

                  If there is no Ivan in the mask dp[mask] = 0.

                  If there is Ivan in the mask, you choose the best tournament in that fight. You have 2 cases here:

                  a) You choose 2 fighters without Ivan and I explained that case above. That fight would happen in any but last position — my explanation covers that too. But to make it more clear: you don't care at which stage that fight would happen, the point is that the winner of that fight would be defeated by Ivan later.

                  b) You choose Ivan and another fighter — that fight has to happen as the last one.

                  So you evaluate the fight between 0 and i.

                  So your formula will take dp[mask^1]*prob[i][0] and this is 0, because dp[mask^1] = 0

                  • dp[mask^(1<<i)] * prob[0][i] — and this means that Ivan beats the mask without i and beats i in the last fight.

                  Which is exactly what we want.

                  That's why I said that it is a great solution with memory O(2^n) and was very impressed how did you manage to come up with this reasoning during 2 hours. It's interesting to see that you were thinking of something different :P

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

                  this explanation is wrong, lol

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

                  That's what I wrote in case a). In case b) you are adding the new candidate to the mask. The mask is already beaten by Ivan — so it will be the last fight with new candidate.

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

                  Are you sure every sequence can be made into a chain? For instance, what about 3 beats 4, 5 beats 6, 2 beats 3, 2 beats 5?

                  And even if that transformation is possible, the sequence of fights is not determined in advance (because as you said you can change it depending on prior results), so you wouldn't necessarily know what transformation to use.

                  It's very interesting that this solution works, but I think the explanation why is not that simple...

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

                  I'm not sure about a chain, but I can't see what is the problem with my explanation.

                  It is clear that you choose the most profitable battle. If Ivan is engaged, it is the last battle, no matter what was the order of the other battles.

                  If he is not engaged, that battle is not last, as the winner of it got already beaten by Ivan in the state we have calculated. So we can insert it everywhere, but the last position.

                  Your example doesn't include Ivan and for such case the solution immediately outputs 0.

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

                  I was replying to dalex's explanation, not yours, which I only read now. As far as I can see, you don't address the requirement that the winner of the last fight has to be part of the next fight.

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

                  Because we already reached the discussion depth limit — it is hard to say to which answer was the reply.

                  That requirement is addressed in the following way:

                  If Ivan won the last battle, he obviously will be participating in the next one.

                  Below part was edited:

                  I got lost in one case.

                  If you choose the battle between (i,j) and i won that battle. You know that in the dp[mask^(1<<j)] he was defeated at some point (as Ivan won the whole mask^(1<<j)). You insert that battle after the last battle won by i in mask^(1<<j) (which means that after i's victory we invite j to fight with him).

                  If i didn't win anything in mask^(1<<j):

                  a) If he lost in hist first fight, then add battle between i and j on the first position.

                  b) Otherwise there exists k, who defeated i and k had to win at least one battle (as i didn't loose the first fight). Let's say that k defeated r just before defeating i. And let's assume that r also defeated m.

                  Now it is clear that i and j have to fight in the first fight, as i didn't win anything in mask^(1<<j). After (i,j) should fight (i,k) and after that (k,r) but r would be defeated by k and it has also defeated m...

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

                  I constructed a case by ffao, which ruined the explanation about chains: http://ideone.com/QYmfXx... or not? Look what it outputs for mask 31 (after 5 defeats 6).

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

          My solution uses the same idea as yours, but I don't really know why it works! I just code it to see if it solved the problem, but I was skeptical. In my mask I store the participants that are dead, and try all possible pairs, and sum the combinations that result in only Ivan alive. The code turns out to be very simple but I don't know why it works! 18510404

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

      can you tell me what i did wrong here, please?

      http://codeforces.com/contest/678/submission/18433012

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

    I solved it using dp, Let f[s][i] be the probability that the jedi winns if s is the set of siths that are alive, and i the sith that won the last round. We can try over all possible siths j!=i, and over all possible outcomes (of the fight between i and j), of course we should chose the one that maximizes the probability that the jedi winns.

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

      But don't you have to deal with two subsets each time?

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

        Why two subsets? As you can see my recurrence use just one subset. Note that the set of died siths is the complement of the alive siths

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

          two mutually exclusive subsets , with one winner of each subset, fighting in the current round which covers union of both subsets.

          At least this is all I could come up with.

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

      @Alei : I do nt get in ur dp how u are ensuring that 0th index is the last winner. could u pls elaborate how uve done that.. or how is it implicitly taken care of.?

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

      Tnx for providing us with your clear and simple solution. :)

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

in problem E, how the sample gives 0.68??
Stuff that can happen so 1st person win are:
1 win 2, 1 win 3
1 win 3, 1 win 2
2 win 3, 1 win 2
3 win 2, 1 win 3

All this happen with 0.49333 probability.
What am i missing?

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

    Question asks to find the maximum probability which comes from this order 2, 3, 1.
    2 wins, 1 wins : 0.4 * 0.5
    3 wins, 1 wins : 0.6 * 0.8
    Total prob = 0.2 + 0.48 = 0.6

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

      Note that optimal choices can differ depending on the results of the previous battles. So talking about "order" is not correct.

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

PROBLEM C: It is wrong with my code?

#include <bits/stdc++.h>
using namespace std;
int main()
{  
 int n,a,b,p,q;
 cin>>n>>a>>b>>p>>q;
 long long  s=0;
 int na=0,nb=0,nab=0;
 na=n/a;
 nb=n/b;
 long long  z=(a*b)/__gcd(a,b);
 nab=n/z;
 long long  val= p>=q?nab*p:nab*q;
 s=(na-nab)*p+(nb-nab)*q+ val;
 cout<<s<<endl;

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

    z overflows try 1000000000 1000000000 1000000000 1000000000 1000000000

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

      the solution change the data type of the input variables int a long long

      #include <bits/stdc++.h>
      using namespace std;
      int main()
      {  
       long long n,a,b,p,q;
       cin>>n>>a>>b>>p>>q;
       long long  s=0;
       int na=0,nb=0,nab=0;
       na=n/a;
       nb=n/b;
       long long  z=(a*b)/__gcd(a,b);
       nab=n/z;
       long long  val= p>=q?nab*p:nab*q;
       s=(na-nab)*p+(nb-nab)*q+ val;
       cout<<s<<endl;
      
      return 0;
      }
      
      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        You can do: a / __gcd(a, b) * b

        To avoid overflows as the division will be carried out at first

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

    Why do you need __gcd()? What are you trying to achieve with the variable z?

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

      find the number of numbers divisible by two numbers given

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

        Interesting, I haven't thought about that. I've calculated that number with expression n / (a * b).
        It is good that the contest is not rated :)

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

    Probably (na-nab)*p overflows, try (na-nab)*1ll*p (and same with q). Or simply use long long for all vars.

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

Thanks, the problem really was easier than last time. Maybe you had to swap B and C. UPD. Take back a words about the B and C after start of hacking.

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

В задаче В я сдал два решения на ОК. Одно из них было взломано, а другое — нет. При этом, в таблице задача числится нерешённой. Почему?

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

    В результаты идет только последнее принятое решение. Все предшествующие просто игнорятся. Такое правило действует на любом контесте(если я ничего не упустил)

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

I sent two solutions for problem B that got OK. One of them was hacked, the other wasnt. But the table says I havent solved this problem. Why?

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

C was solved by 1500+. now it has become 900+. #HackEffect

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

Can someone tell me why my solution fails for C?


int main(){ long long int a,b,c,d,e; int cnt=0; scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e); long long int res = 0; long long int res1 =0; res= ((a/b)*d) + ( abs((a/b) - ((a/b+a/c)-(a/(b*c))) ) * e); res1= ((a/c)*e) + ( abs((a/c) - ((a/b+a/c)-(a/(b*c))) ) * d); if(res>res1){ printf("%lld",res); } else printf("%lld",res1); }
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

Эм? Авторы, вы серьёзно? Мою С взломали. Я стал думать почему. И вдруг понял, что я идиот. Написал решение без gcd или lcm. Как!? Вы мне скажите, как вы готовили тесты, что моё решение не упало на них. Любой банальный тест даже с совпадающими делителями — всё, конец моей программе.

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

Мне кажется, подсветка этого(18419415) кода немного неправильна.

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

My first hacking attempt and i hacked 15 solutions for problem C

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

How could problem D be solved using matrices?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    a[0][0] = A;
    a[0][1] = B;
    a[1][0] = 0;
    a[1][1] = 1;
    
    this matrix multiplying with  
    [x 1] gives [A*x+b 1] and we can repeat this process..
    
    
    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      why a[1][0]=0 and a[1][1]=1??

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Because of this 0 and 1 we get column vector with Ax+b and 1 from column vector of x and 1.and since Ax+B is our next x we actually have new x ,1 column vector.so this allows us repeating the process.but is actual program we will do the matrix multiplication in log(n) time rather than doing all the multiplications.
        
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Simpler way: you can exponentiate f itself: f^2 = (a*a)*x + a*b+b. Then use fast exponentiation to compute W,R from f^n = W*x+R:

    Python code:

    cur = x
    while n > 0:
        if n & 1:
            cur = (a * cur + b) % MOD
        a, b = a*a % MOD, (a*b + b) % MOD
        n >>= 1
    print cur
    
»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

What is the hack case for D?

My solution is to find value An·x + (1 + A + A2 + A3... + An) * B. To find sum of GP, I use the standard formula with an exception case where A = 1, when GP sum = n. What is wrong with this 18423561

UPD: Mine was hacked due to overflow of GPSUM*b in special case as I forgot to take modulo with n and it overflowed even long long :(

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

I am getting overflow in Java7 at problem C when running this test : 1000000000 1 3 1000000000 999999999 My code: https://ideone.com/kHjrJT

Any idea?

EDIT: Now I see that I was not the only one facing this problem. I changed every variable from int to long and now everything seems to work. God, I hate when this happens. But better here than IRL.

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

    if operands are int, then result is int. So in pieces:

    long nr = a * b;  
    ...  
    sum = sum.add(BigInteger.valueOf(Math.max(p, q) * x));
    

    overflow exists. Two possible solutions:

    1) Make all operands long-type;
    2) Add 1l literal:

    long nr = a * 1l * b;  
    

    1l — is long-type const so during multiplications overflow wouldn't appear.

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

My god, problem C is a pure hacking bloodbath...

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

I want some advice about hacking. Sometimes the contestant doesn't initialize a variable, so it contains a garbage value, which might give WA. What should I do in such cases, is the garbage value machine dependent or is it some fixed value?

This thing happened in last CF round, one solution didn't initialize a variable, and he was taking max of it with another variable. Fortunately for him, the garbage value was some large negative value, so I couldn't hack him. I would have hacked if the garbage value was some large positive value. What to do in such cases?

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

What's the idea for problem F?

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

    I instantly came up with the idea of using a fully dynamic convex hull and then evaluating at certain coordinates. I coded it and debugged it without thinking, only to fail at Test #9. Then I thought a little bit and I realized that when deleting a line, some lines that were removed earlier because they weren't relevant anymore, might become relevant again, so I'm not sure if fully dynamic convex hull is something we can do.

    I still don't know how to solve it.

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

      I think you can solve it without fully dynamic convex hull. Just process queries by blocks (block can have sqrt(n) size, but this is not the best choice). Build convex hull on previous blocks (without deleted pairs in current block of course). Then lookup answer for query in O(sqrt(n) + log(n)). O(n * sqrt(n)) for all.

      I think it is good solution, but I am too lazy to check it today =D

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

    One solution is that: for each line there is an interval it exists. So, build a segment tree each node contain a convex hull. See link. The other one is sqrt decomposition query. Build a convex hull at each block!

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

      Huh, I haven't written a single task using either of those techniques, guess I have to try :)

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

What does "Unexpected verdict" mean for my hacking attempts #236256, 236261, and 236265?

UPD: fixed.

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

i hacked myself in problem D due to this- ans = ((b%mod * n %mod)+x)%mod test case — 1 1000000000 10000000000000000000 1000000000

due to operator preference b%mod * n will take place first thus overflow!

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

    in the test case you mentioned, the value for n is 10^19 which won't fit even in long long. I think you meant to type 10^18.

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

there will be no tutorial for this round?

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

"состоится очередной тринадцатый учебный раунд" Вы уже много тринадцатых раундов организовали?

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

Where is the editorial for fifth question??

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

Будет ли разбор по учебному контесту? По-моему, для учебного контеста это очень важно.

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

When i run c number code on my laptop it answered me 813.But why codeforces answered 625?

include<bits/stdc++.h>

define ll long long

define sf scanf

define pf printf

define end return 0

define d double

define f float

define b break

define c continue

using namespace std; int main() { ios::sync_with_stdio(0),cin.tie(0); ll m,n,o,p,q,a=0; cin>>m>>n>>o>>p>>q; a+=(m/n)*p; a+=(m/o)*q; a-=(m/(n*o))*(min(p,q)); if((n*o)>m) if((m!=1)&&(((m==n)&&(!(m%o)))||((m==o)&&(!(m%n))))) a-=min(p,q); cout<<a<<endl; end; }

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

Когда будет перетестирование на полных тестах? Это уже какая-то нехорошая традиция появляется — откладывать финальные систесты на учебных раундах.