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

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

Хотите выиграть футболу? Или узнать как придумывать задачи для соревнований по программированию? А как насчет порешать 7 задач за два с половиной часа?

Если ответ хотя бы на один вопрос из перечисленных выше -- да, тогда Codeforces Round #270 непременно для вас. Раунд был разработан мной в Калифорнии, и приготовлен в системе Polygon (оригинал: designed by me in California, assembled in polygon). Спасибо MikeMirzayanov за прекрасную систему и Gerald за помощь в организации и тестирование раунда. Раунд стартует в обычное время в воскресенье, не упустите возможность посоревноваться!

Организаторы Marathon24 решили сделать подарок лучшим участникам раунда! Лучшие 25 участников получат специальные футболки от Marathon24! Большое им спасибо!


Эта картинка всего лишь для привлечения вашего внимание. Настоящие футболки будут иметь специальный дизайн от Marathon24!

Существует несколько статей, которые призваны научить, как стать автором задач для соревнований по программированию. Например, Problemsetter's Memoir и Way of Problemsetter. Но все они детально рассматривают только лишь процесс подготовки задач. Возможно, вы не знаете как начать готовить контесты по той причине, что у вас нет идей для задач.

В последние три года я подготовил очень много задач. Например, два Codeforces раунда (#190 и #228), также я подготовил ровно 100 задач для Topcoder. Поэтому я решил написать небольшой учебник, чтобы поделиться своими знаниями по придумыванию задач с общественностью... Стоп, как насчет привести контест, в условиях задач которого будут содержаться советы по придумыванию задач. Так я пришел к идее: в каждой задаче контеста будет описываться определенный способ придумать новую задачу, затем в качестве примера в условии будет описан процесс придумывания новой задачи этим способом; эту новую задачу вам и предстоит решить!

Обратите внимание, этот раунд будет немного специфическим: все участники (и Div1, и Div2) будут соревноваться в одном и том же контесте, а контест будет состоять из 7 задач! Продолжительность контеста увеличена до двух с половиной часов.

В конце я хочу немного рассказать о себе (как это сделал marat.snowbear в предыдущем анонсе). Меня зовут Gaoyuan Chen, и родом я из Китая. Я жил в Beijing в течение 23 лет (до этого августа), а затем поступил в университет южной Калифорнии в Лос Анджелесе, чтобы научиться разработке игр. Как разработчик игр я постарался сделать раунд как можно более интересным (конечно, в раунде есть задача про известную игру). Когда я переехал в штаты, я стал использовать Facebook, так что если вы хотите узнать меня лучше или пообщаться со мной в чате, заходите на мою страницу: https://www.facebook.com/cgy4ever.

Остальная информация, например, разбалловка задач (возможно, последняя задача будет иметь стоимость 3500!) будет опубликована позднее.

Желаю всем удачи и удовольствия от решения задач!

Update1 : Разбалловка: 500 — 1000 — 1500 — 2000 — 3000 — 3000 — 3500

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

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

These T-shirts look a bit generic :D

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

    It is just an image to attract your attention. Real tshirts will be designed specially for Marathon24!

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

Thanks everyone who downvoted this comment . I broke a record and became last one in contribituon list . This is a big achievement in my eyes. Start upvoting now !

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

The age of long round descriptions has started

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

Its really nice and interesting to know about the problem setters.

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

So are the top-25 of both rounds getting t-shirts?

UPD: sorry I misread, both divisions are competing in one contest

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

Oh yes, this will be very useful for me. Maybe I will learn how to write a non-math problem (!!)

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

Is this a rated event?

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

    Yes. Why not?

    This is not the first rated round for both division. (e.g. Good Bye 2013 was rated for both div, but the duration is 2:00 instead of 2:30)

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

      Just because I saw both division round for the first time. :)

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

      You introduced your self in your blog. But, Something was question to me for a long time. Why is your username cgy4ever? What does cgy means and why forever? :-)

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

        His name is Gaoyuan Chen; in China, the family name goes first, so Chen Gaoyuan (CGY).

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

you are mine one of all time favourite coder , you always write code simple and understandable :) . last couple of rounds was not good for me i hope this time my rating will increase :D . it always great to compete with both division :)

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

My favourite problem setter !! I have tried to mimic/ learn problem writing by looking at his problems. Your problems are really creative and provide a lot to learn. A big thank to you cgy4ever from heart :)

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

"then I went to University of Southern California in Los Angeles to learn Game Design and Game Development."

That sounds awesome :D

Is there any game you've designed?

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

    That's a Yo Gi Oh Problem setted by him Link , maybe he was a part of the team who designed it ? =D

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

      Oh, no, Yo-Gi-Oh is not designed by me. :)

      That is indeed a great game, I played it (and watched the anime, at least first season) when I was in primary school.

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

      That's impossible timewise, the franchise is from early years of this century.

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

    Oh, so you know I just start my way to become a game designer, so don't expect some famous games designed by me at this time.

    We have a game design course this semester, and we are designing non-digital games every week. (We have not only CS student but also students from School of Cinematic Arts, and most of them don't know how to program, so we design games that do not require programming)

    That is a fun course, these pictures shows how other people are playing games that my team designed in first few weeks (it is called playtest: they play our game and give us some feedback, then we use these feedback to improve our design, and repeat this process again and again):

    http://puu.sh/bPARt/49974bf0b6.jpg | http://puu.sh/bPASe/91b97133b2.JPG

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

      I'm sure that if you do the same thing for gameplays as you do for contest problem ideas, you are almost guaranteed to discover a few game-changing ideas eventually. Good luck with that!

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

Great format: 7 broblems — more place for solving ideas and more interesting standings!

At least its my thought.

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

This round will be on my 17th birthday :) I hope this will be a great round for me and for all.

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

I do hope you provide sample implementations for the really hard problems. Its always a pleasure to read your code cgy4ever !! :D

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

I've a feeling like Codeforces is becoming more than a problem solving and programming site , I'm feeling lucky to be in this great community with brilliant minds

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

Problem setter is very interesting of facebook chat. :D

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

Just curious, do you have any special reason behind making this contest combined for both divisions?

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

Another Chinese Round arriving!

Enjoy the T-shirts:)

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

What does "cgy" in your handle mean?

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

An exciting announcement :) Wish this round success !

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

Surely the best way of creating new problems — misreading other problems. I created a lot problems that way :D.
For example: http://www.artofproblemsolving.com/Forum/viewtopic.phpp=2498536&sid=add5e05df3e05f2371cd0bee14294831#p2498536 — I misunderstood phrase "rounding down to the closest integer", I somehow ignored "down" and focused on choosing the closest integer, so 5,2 should be rounded to 5, but 5,7 should be rounded to 6. It turned out it has a really cute solution and later it that problem was posed in the most popular polish mathematical periodical "Delta" :D. Can you find the solution :)?

Lame way of creating new problems: "What can be done by using centroid decomposition?" :P.

Another fun way of creating new problems is to get inspiration from real-life situations. For example when being annoyed at people getting on the plane when they block the aisle taking care of their luggage and causing 50 people to wait. It immediately comes to mind that given time of blocking aisle when finding one's place for all people, one should firstly find an optimal arrangement, so that the summed time of waiting is minimized!

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

    Two easy ways:

    1. change one word
    2. swap input and output

    (see the problems E, I, J from our last gym contest)

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

    I once created around 4 problems (for a physics competition) by naming them by quotes from Fish Fillets and creating problems based on them. Of course, it's easier to make physics problems because you just take an IRL scenario and make a simplified model if it's unsolvable :D

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

sorry

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

“all contestants from Div1 and Div2 will compete in one contest”, does it mean a difficult way for the div2 members to get the T-shirt ?

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

    Yeah, for me too.(I always jump from div1 to div2, then back) :D

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

    I don't know how exactly the rating is calculated in codeforces contests. But from the limited number of contests I did till now, what I came to know is that my rating would increase/decrease depending on whether I got a better/worse rank than the previous contest. Since this time, Div 2 contestants will be doing the contest with Div 1 contestants, the ranking of Div 2 contestants will most probably not be better than last time. Does this mean that we (Div 2) are going to get a drop in the rating?

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

      No. The update will be adjusted to that unusual contest (I mean, formula for updating ratings covers all cases in a relatively fair way, any special treatment is needed).

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

    as difficult as for div.1

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

Жалко что с отбором Минским на ВКОШП пересекается.:(

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

ACM-ICPC rules?

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

Is this a rated contest ?

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

worse настал твой час получить самое большое увеличение рейтинга. Ну или можешь и дальше в минус уходить, в принципе, и то, и то — интересно.

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

    Ты ещё не понимал, что так оно и случится :) 469 место

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

      А может Lo_R_D — это мой основной аккаунт, и я просто решил поднять себе вклад, как вам такой вариант? ;)

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

        Да-да, определённо я — это ты. У меня перед этим раундом возникло желание по-взламывать кого-нибудь, чтобы уйти в минус и вылететь из div1, так как последнее время, ожидая раунд для div2, я засыпал, потому что не было достаточной мотивации для участия.

        А еще была идея попросить Мишу добавить кнопочку "Сбросить рейтинг на 1500" для первого дивизиона, уверен, Гена и Петя бы обрадовались такой кнопочке.

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

It was designed by me in California, Assembled in polygon

Are you mimicking Apple? haha

https://www.apple.com/designed-by-apple/

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

Could be 5k registrants! Fingers Crossed

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

5000+ registration and all of them are official . This is great :D

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

delayed :(

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

Will this round rated??

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

The contest was delayed because this guy didn't registered at time

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

5419
Sorry TopCoder It's The Age Of CodeForces

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

Хотел зарегистрироваться => нажал кнопку => предложило сначала зайти на сайт => зашел => забыл снова нажать на регистрацию => я не участвую. Жизнь — боль.

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

C. Уроки дизайна задач: недетеминированность

А где же первая "Р"?..

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

мне интересно на сколько поднимется рейтинг worse, он сейчас на 500+ месте

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

worse solved the first 4 problems! I wonder if he is going to hack everyone again!

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

Ставлю, что worse дадут 1000+ рейтинга

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

worse solved first 4 problems!
I'm going to kill myself :D

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

    and didn't do even one unsuccessful hack! :D

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

      Oh my god, I forgot about unsuccessful hacks, what a shame... Now my rainting will increase, it wasn't in my plans, I hate myself :(

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

        You should solved all 7 problems in contest,and make many many unsuccessful challenge until your score's absolute value equals to the score when you solved 7 problems.

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

        Because you are the one in my friend list, when it came to 2 hours after starting, I was so surprised that you hadn't done any hack! And I doubted that you write the code which can pass pretest and FST. After system test, you surprised me again. In the end, I doubted you either forgot to hack (maybe you forgot it is the "worse" account) or want to make a "V" rating (decreasing and increasing). You can make another achievement that become IGM from white rating (rating below zero)~~ BTW. When I finished the problem C, I clicked the friends' rank and notice your rank is in front of mine... At that time, I felt I am worse than "worse" as well as the "worst"...

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

        to be honest what ever you did for fun or anything make you as a celebrity :D today anyone from codeforces community at least know about two handle tourist and worse :D

        Btw i believe oneday you will be a red coder :) i would like to ask you a personal question how old are you ?

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

          It's a secret. I'll tell you when I become a red coder ;)

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

          "i believe oneday you will be a red coder" — done! ;)

          Thanks for your belief in me!

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

Я усвоил уроки по дизайну задач, но смог пока придумать только математическую задачу по мотивам задачи D: верно ли утверждение, что для любого дерева с нечетным количеством вершин, сумма расстояний между каждыми двумя вершинами будет равна сумме всех рёбер, помноженных на некоторые чётные числа? То есть сумма( Sij, i = 1..n, j = 1..n ) / 2 = сумма( Ai * Ri, i = 1..n-1 ), где Sij — расстояние между i и j вершиной, Ri — вес i ребра, Ai — некоторые чётные числа.

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

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

Первое ощущение — ОНИ ВСЕ СПИСЫВАЮТ ДРУГ У ДРУГА ))

Да, и еще остается время подумать о том, какую все-таки фигню написал сам.

UPD как решать D ?

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

    На Д у меня идея была такая: Что то типо Дейкстры. Из первой вершины идем в самую ближнюю. Потом из 2ух вершин в самую близкую и так далее. В результате у нас получилось дерево. И сверяем расстояние от каждой вершины до другой. Не хватило минуты что бы сдать это. Так что возможно я что то не до понял.

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

      Вы придумали алгоритм Прима для нахождения MST :)

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

        Ой да... Это же Прима :) Что то со мной не то :) Ну хоть я это быстро придумал

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

      Блин, была и такая идея. Но мне почему то очень уж хотелось пытаться строить дерево каким-то dfs-ным алгоритмом. А потом проверять через lca (которое не умею писать). Оказалось кто-то строил дейкстрой, в разборе — крускал. И также в разборе сказано, что проверить успешность построения можно не только lca, но и вообще за квадрат (это пока не понятно).

      UPD Нет, в разборе сказано проверять, запустив N dfs или bfs, не поверил сперва.

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

Are there maxtests in pretests? Will all those solutions pass?

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

    How do you "check" ? by doing all pair shortest paths specialized for a tree ?

    EDIT: sorry comment was meant for your MST post for problem D !

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

How is problem D supposed to be solved?

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

    I found MST and then check if its correct answer.

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

      What algorithm did you use to find MST ?

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

        I used Prim's algo, but I believe Kruskal's algo will do too.

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

          Can you please tell me what do you exactly mean by "check if its correct answer." after finding the MST?

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

            Check that all pairwise distances are correct. It could be done in plenty of ways, I used dfs from each vertex.

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

      How did you find MST ? How did you derived edges from the distance matrix ?

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

    There are many ways. For example, if you pick vertices i, j, then you can recover the path between them: k is on this path iff D[i][j] = D[i][k] + D[j][k]; sorting by D[i][k] gives their order on the path. This way, if you pick i as the root and try all j, k, you have all supposed edges and are left with checking their treety.

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

Okay, I'm probably going to hang myself, but what was the idea for B ? I just didn't get it...

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

    I use this: try to send people to top floor first and use any spare capacity for the floors below. continue same downwards

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

    the idea is that you have to move to the highest floor ... so it makes sense to make a greedy approach : pick the highest k people (Fi) and transport them and come back and do the same thing again ...

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

    Okay, now I know why I didn't get it... I just didn't realize that 1st floor is really 1st, i. e. floors are not 0-based! And it was written in the statement like bazillion times and I was just wondering how they got the answers to the samples... goodbye cruel world :D

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

Я понимаю, что, чтоб писать такое как мое решение на задачу D, нужно быть конченым извращенцем, но почему Мин Каркас + LCA не правильно?

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

Омг, написал в B динамику d[человек][группа][его место в группе], заблочил задачу, посмотрел другие решения и понял, какой я идиот :(

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

    По C написал динамику dp[pos][prev_choice]

    UPD failed systest, add 2 lines of code, AC. +1 reason to think about greedy twice before writing dp (at least, it may help to write dp properly).

    UPD2 я опять в ауте, опять перепутал spoken languages

    UPD3 блин, все

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

    Я, конечно, написал динаму по одному параметру, но тоже огорчился, когда стал смотреть чужие решения. Тем не менее, в одном чужом решении нашел багу — помог себе и человеку.

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

    Что было в тех простых решениях?

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

      Сортируем массив по невозрастанию, и каждый k-тый плюсуем. умножаем на 2

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

Are there any rules which forbid using inline assembler in C/C++ code? With it, problem G becomes super-easy...

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

    I might get a lot of downvotes for this, but I don't see which assembler magic you can use to make the brute-force approach viable, (if thats what you mean by super-easy...)

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

      Compute bit count via SSE3. (I'd like to note that even without assembler magic, __builtin_popcount results in ~7.9s for the worst case; but SSE3 bitcount results in <3s).

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

        Good job ilyakor!

        I have tested builtin_pop_count() and made sure it will fail. But it turns out many people uses cnt[x<<16] + cnt[x>>16] and passed.

        I think I should learn more knowledge about low level computer science, like assembler.

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

It was difficult to hack in this round :(

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

Wonder how long System Tests are going to take with so many people and 7 problems...

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

worse'll increase +inf i think

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

Can anyone please tell how to hack a code with code generator .

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

    If your test case is too large, for example it has over 100 inputs, you can write a code to generate your test case, then codeforces compile your code and give the output to the selected code for hack.

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

    I tried to write max_tests with code generator, but did not success. Write 105 integers from 1 to 105 by hands would take to me more than 2,5 hours.

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

How to solve B?

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

worse is going to jump pretty high, i guess :)

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

I am more interested to see rating change of worse than mine :)

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

How to solve C? I submitted a solution which passed pretests but I am afraid that it will fail systests.

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

    Greedy. Take the minimum of 1st string according to given permutations.

    set flag=0

    Then go to all other permutations in given order and take minimum of them which is greater than the first string and make it as the current string If none of the names now has string greater than current string then break the loop and answer is NO so set a flag=1 else make current string as lower of the two strings of a permutation and do next iteration

    if(flag) ans=NO

    else answer is YES

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

Я в D отсортировал ребра (если считать элементы матрицы потенциальными ребрами) по весу, каждую вершину поместил в систему непересекающихся множеств.

Дальше, проходил по всем ребрам. Если текущее соединяет вершины из разных множеств, объединял множества, и добавлял ребро в список ребер дерева. Иначе ничего не делал.

Потенциальные ребра с весом 0 выкидывал на момент чтения.

Дальше, проверил, что граф связный, через n bfs-ов нашел расстояния между кратчайшими вершинами. (Между двумя вершинами дерева есть только 1 путь, поэтому кратчайшее расстояние можно искать bfs-ом)

Получил TL 10 (http://codeforces.com/contest/472/submission/8011182 ). Немного разогнал bfs, но снова TL10. (http://codeforces.com/contest/472/submission/8014663 )

На моем компьютере около 0.9 секунд занимает считывание и примерно секунду сортировка. bfs за 0.3

Кто-нибудь использовал ту же идею?

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

    Алгоритм правильный, но очень много входных данных (20002), поэтому используйте ios_base::sync_with_stdio(false);

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

      Я использовал scanf.

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

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

      Похоже, что измерение астрономического времени вместо процессорного создает очень большую погрешность

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

        Запуск был в дебаге или релизе?

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

          В dev-cpp). Думаю, что это в релизе, т.к. если запускать с возможностью отладки, то работает 56 секунд.

          Код с подсчетом времени: http://codepad.org/e5PYsTBV Генератор теста: http://codepad.org/iDGPCoK0

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

          Проблема оказалась не в зацикливании. Просто я хранил веса ребер в long long вместо int-а, и это замедляло их сортировку на пол секунды

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

he is lucky :P
submission: 7999344

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

That's feeling, when you know that your n^3 solution won't pass system testing, but you steel can not stop hoping :|

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

тем временем пошёл уже второй час систетов:)

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

    Верный знак быстрого обновления рейтингов :)

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

i tried hacking 8002822 with n = 17, but the code (correctly) returned 8, 9 as output. can anybody explain how?

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

    I don't know why...It's strange because 8>=n/2 and he have i<n/2.That's black magic :))

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

      it's even more puzzling because i successfully hacked 7998356 with the same input n = 17.

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

        When the round started I was a bit excited to be in the same room with you, since I've noticed you're active and known in the community and also I participated in #258.

        But then i got disappointed when you hacked me ~10 minutes before the end, when my solution was locked (all because of a missing '=' sign).

        Nice find though. :)

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

    Well, he reads from not unitialized variable and it's UB(may work in any way), probably it's optimized in that way that a and i are effectively the same variable, because in any correct case(when there's no UB) a and i are equal

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

    compile this code with clang++ and g++, got two random numbers 8015726

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

D problem was very pleasant for me. After a hour of thinking (and that's what I like) I discovered how to solve it, but sadly I wasn't able to implement a correct solution. Thanks for round!

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

Во время контеста придумал решение по D, которое работает за n^3 с отсечениями. Понял, что долго, и решил не писать его. После контеста написал — зашло, lol, с максимальным временем 1668 мс.

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

    Если кому интересно, решение носит вот такую идею:

    1. По первой строке матрицы располагаем вершины в точках на целочисленной координатной прямой. То есть, если первая строка 0 1 1 5, то первая вершина в точке 0, вторая в 1, третья в 1, четвёртая в 5.

    2. По первой строке сортируем по возрастанию все вершины.

    3. Идём по отсортированным вершинам и смотрим их расстояние до других вершин, где мы еще не были. Это расстояние может быть равно значениям двух видов: а) разности положения на координатной прямой, б) или же нам необходимо пройти все точки слева от этих двух (то есть точки, в которых мы уже были), и тогда расстояние между вершинами должно быть равно (положение первой вершины на прямой) - (положение некоторой вершины слева) + (положение второй вершины на прямой) - (положение той же некоторой вершины слева).

    4. Если получить какое-либо расстояние между двумя точками не получается — ответ No. Так же отдельно проверяем матрицу на симметричность, равенство диагонали нулю, и неравенству элементов вне диагонали нулю. Если всё хорошо — ответ Yes.

    Решение

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

      у меня было что-то похожее, только работало за квадрат.

      1. сортируем вершины по первой или любой другой строке.

      2. рассматриваем i-ю вершину. Ищем максимальное j<i, для которого d[0][j]+d[j][i]==d[0][i], и проводим ребро i-j.

      3. проверяем, чтобы граф был связным и все расстояния корректными (я сделал n dfs-ов)

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

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

    Кстати, интересует решение G. Расскажите кто-нибудь, пожалуйста. Я зациклился на идее с sqrt-декомпозицией но дальше, чем время работы примерно в , которое моему скиллу писания на Java не очень понравилось, я не продвинулся. Или так и надо было?

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

      Я не поленился и посчитал, и для n = 2000 вышло вообще 2666666000000. Может где-то ошибся в расчетах, но вообще по идеи должно быть так:

      n * ( ( n — 1 ) * 1 + ( n — 2 ) * 2 + ... + 1 * ( n — 1 ) ).

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

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

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

          Код

          Для самого печального теста вышло: 2 484 943 712. Это без учета сортировки.

          Может где-то переборщил, да и компилятор возможно оптимизирует некоторые места. Но решение таки заТЛилось из-за дополнительных подсчетов глобальной переменной.

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

            Ну тогда это что-то новенькое, видел как циклы по 10^9 залетали за секунду, это удивлять уже перестало. Но тут как бы посложнее, чем пара циклов. К тому же, если и правда дело в оптимизациях — на векторах может еще быстрее заработать (их он различает по расположению в памяти, в отличие от указателей на массивы, может перестанет копировать лишний раз где-нибудь). Но это уже совсем наркомания :D

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

        Ты уж прости, но как-то так себе отсечения, если при n = 2000 O(n3) выливается в 2666666000000 :)

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

      Ну.. Я умею это делать за N * 512( * 8) + Q * (512 + N / 512)

      8017008

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

Petr won this round with a nice margin!

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

delete

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

Can anybody tell me why this solution of mine Timed out. But this got accepted. The first one used scanf to read inputs. The second used cin with sync_with_stdio(false). I assumed both of them are comparable in the time it takes.

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

One of the best rounds I've ever participated. Congrats!

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

    My rank of contest is

    R = 2^A + Q

    where

    A is a count of my accepted solutions

    Q is a quality of problems

    didn't you noticed smth like this? :D

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

An identical problem to B was used a few weeks ago in a URI Online Judge contest. Link

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

    I have access to the identical problem in Polygon, it's too easy to be unique

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

      Even being an easy problem, it's cool to solve. It was a good choice.

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

I really enjoyed the problems, the mixed divisions was a great idea, as the problems were approachable for both divisions users. Thanks for the great contest.

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

Problem D is one of the most hard problems that I ever sent on contests (if do not take into account that I have copypasted code for DSU and Dijkstra from emaxx:)) ). Thanks for interesting problem D and interesting stories about problem creating:)

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

Отличный контест. Я уже готов было сдаться на третьей задаче, но всё-таки удалось решить ещё 2. Это мой первый контест, когда удалось выйти за 3 решённых верно задачи :) Сложность подобрана просто отлично!

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

    Время по D: 1980 мс. Тебе очень повезло)))

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

      Странное время на самом деле, учитывая, что куба там нет :)

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

        Константа решает. Вот одно и то же решение, но в одном — multiset, а в другом — priority_queue: 8018809 8018805

        P.S. Я к тому, что и n*n*logn может не зайти)

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

      Прошерстив тут комменты, понял, что видимо надо было добавить строчку:

      ios_base::sync_with_stdio(false);
      

      UPD: сейчас перепослал задачу с этой строчкой, получил Время: 389 мс :) В 5 раз быстрее.

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

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

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

    А на счет сложности задач я с тобой не соглашусь.

    Задача С была уж слишком простой. Возможно, что её решило на 500 человек меньше, чем B, только потому, что они психологически думали, что не решат её. Уверен, если поменять местами B и С — количество решений по С изменилось бы и догнало B. Её усложняет только условие. Я так вообще не понял сначала, что дано в массиве p, и поэтому писал неправильный код, зачем-то sort() использовал. Я даже сейчас не смогу объяснить, что я думал, ибо это такой бред, скорее всего.

    Задачу Е явно недооценили по сложности. Тут уже можно судить по количеству человек, которые её решили. Поменять её местами с F и давать 3500 баллов за неё — было бы неплохо. Да и вообще, если автор хотел сделать обычный раунд, только общий для 1 и 2 дивизиона, то это слишком сложная C div1, обычно её решают хотя бы 100 человек.

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

When ratings will be updated?

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

@admins Please can anyone tell the approx time it would take for rating update ? If it is >= 30 mins I will go to sleep :p

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

Actually, the contest was not balanced. It doesn't deserve +537, too bad that I had voted it before it started. Three easy straightforward problems that almost everyone solved, one problem that requires to think a bit, and three very complicated ones. Many people were doing nothing after they had solved D. Problem E should have been replaced.

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

    C should have been harder too . A , B , C were very easy but the jump from C to D was large for low-skilled people like me . So most of the people were able to solve all A,B,C and the ranking was solely determined by speed .

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

      Not only by speed!
      Don't forget about hacks!

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

        Oh, of course! Can you imagine how I enjoyed almost 2-hour searching for that s1.compareTo(s2) <= 1 in problem C?

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

      It was pretty much a div1+div2 round, but with 2xD instead of C+D. That's why 3 easy problems — div2 A,B,C.

      I would've removed G and put an easier problem after D.

      Alternatively, there's a nice hack that shouldn't remove the main point from F and makes the code much less tricky: providing additional 64 registers whose values at the end don't matter.

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

    Yes you are right. I found E is hard to implement few days ago, but I don't have another task to replace at that moment. Maybe we should swap E and F and don't allow x[i]^=x[i] in F (then it will be much easier: we can get 2 same bases).

    I tried to made first 2 tasks as easy as possible. (There are 7 tasks, so if you only solve 1 you will kind of feel sad, right.)

    For C and D, I think the difficulty is fine.

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

      What about my trick of using additional 64 (or any other power of 2 that doesn't give away much from the solution) registers? You can simply copy the base to them and get rid of a troublesome chunk of code.

      That is, at least my solution would be much easier :D

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

        Yes, I was thought about add a constraints like n >= 100 (so it will give you 32 registers after Gaussian elimination) , but it will be a bit strange.

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

          That constraint probably wouldn't do the trick I have in mind.

          The point is that when you have the base copied into separate registers and in reduced form (dunno if that's the right term, the one where pivot 1s are unique on their columns), constructing a vector from them (in a separate variable) is extremely easy. So when you have the idea, there's just textbook GEM and that left.

          It does look a bit strange, but it can always be wrapped in a surrealistic story :D and would most likely increase the number of successful solutions.

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

            I don't understand your reply. Since we are dealing with vectors of length <=32, rank of that matrix was <=32 and n>=100 will imply that after reducing whole matrix you will have at least n-rank>=n-32>=68>=32>=rank free registers where you can copy base and do what you have described. In the end you get rid of that copied base. Either you didn't realize what I wrote or I don't understand why that constraint wouldn't do the trick.

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

              Because these vectors will have to be edited eventually, and that'll mean you don't necessarily have a base in reduced form at some point. Think how easy it is to construct a vector from such a base.

              You don't "get rid" of the copied base, you still need to convert its vectors to desired ones (in y).

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

                1) Reduce Xs to base
                2) Reduce Ys to base (and put those operations in the end in reversed order)
                3) Copy base of X to registers with indices n-rank_x+1, ..., n
                4) Erase base of X from registers with indices 1, ..., rank_x
                5) Create Ys base in registers with indices 1, ..., rank_y using that copied base of X
                6) Erase copied base of X

                What is troublesome here? You don't need here any no longer needed vectors from base of X to newly created vectors from base of Y

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

                  Okay, with real separate registers:

                  1. reduce X to base
                  2. copy base to registers
                  3. xor each vector of Y with all necessary vectors of the base

                  You don't actually need a lot of ideas this way — no need to care about x[i]^x[i], no need to put GEM of Y in reverse order, you don't need swaps at all... I don't know if it wouldn't make the problem too easy, because there's almost no difficulty in implementation.

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

                  Hm, okay, that is a difference, but I think that this difference between what I proposed and what I proposed is 5 times smaller than between what I proposed and between actual solution xd.

                  It is true that my way demands doing operations on Y and to that we need idea of reversing which wasn't obvious for me that we can do this, but the most important thing is that we don't need to erase vectors from base X while deriving vectors from Y, what was really painful for me — we can use whole base of X all the time.

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

                  difference between what I proposed and what I proposed

                  Undoubtedly :D

                  Since I expressed the vectors of Y in the base of X, moving from one base to another became just like moving from the canonical base to another. And that's quite trivial.

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

                  OK, so you got base X and want to create base Y. You create first vector from base Y — name it y1. You have to put it somewhere, e.g. in a place of first vector from base X — name it x1. But if you needed x1 to be able to derive other vector from base Y you will have to reuse y1! And that will be OK only in case when y1 included x1 — in opposite case we are already screwed! So we have to care about what we are replacing also. How are you dealing with that problem?

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

                  Imagine it in matrix form: you start with an identity matrix (base X) and want to create a different matrix (base Y expressed in base X) by standard operations "xor i-th row by j-th". The matrix is in (this is the term) reduced row echelon form, because GEM. It should be pretty obvious by now.

                  Also, if x[i]^x[i] is not permitted, then you still need to get to reduced row echelon form with the base of Y, by sorting rows — or state that it's impossible.

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

      I think it would be the best choice to forbid x[i]^=x[i], make it worth 2500 pts instead of 3000 pts and swap E and F. Main ideas will still be included and we won't need anymore pretty ugly piece of code and have much more AC what won't cause such a big jump of difficulty between ABCD and EFG.

      It is true that we will lose not that obvious part also demanding some thinking, but sometimes it is better to give up on significant issue, because task will become less enjoyable and won't gain interest of number of people which it deserve. I learnt that once when I proposed really nice and pretty hard problem for Polish OI, but I included a bit of geometry in it and people were afraid of that even though that geometry part was pretty easy. It ended with 0 ACs, nobody even knew how to solve it, because people were omitting this task. You can see this task here: http://main.edu.pl/en/archive/oi/21/lam (though it doesn't have english version, maybe translators can do the trick).

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

        Depends on the implementation — for me, that "ugly piece of code" is 3 lines when expressing Y in the base of X.

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

          When we will forbid x[i]^=x[i], reduced bases of X and Y will have to be exactly the same. That will make whole problem much easier. I somehow don't believe that it caused a 3lined difference in your code. In my code 8018580, I wouldn't longer need that last long for loop (that starting with "for (int i = 1; i <= st_y — 1; i++) {") which caused me much more trouble than everything else here.

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

            Codes are public, so it's not really a question of believing :D

            8018626, lines (originally 3):

            for(int i =0; i < m; i++) {
            	for(int j =0; j < i; j++) if(M[j][i]) 
            		ans.push_back(make_pair(B[j],B[i]));
            	if(!M[i][i]) ans.push_back(make_pair(B[i],B[i]));}
            

            If that operation was not permitted, I could've omitted only these 3 lines.

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

              Sorry to say that, but ugh, your solution looks pretty complicated and completely impossible to read, because of incredibly ugly indentation. First for loop after comment "//base" looks really ridiculous, because of places where "}" are put inside it. Is that an effect of some changes in your code while uploading it? I won't believe that it can be your standard coding style.

              If we will forbid x[i] ^= x[i] problem will be like:
              Reduce X
              Reduce Y
              Check if they are exactly the same and if so then print already generated result.

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

                Some parts of it are unnecessary, but that's unrelated to the x[i]^x[i] problem.

                Yes, that's my standard writing style — do you think CF would remove selected indents on upload in my code only? I can't read the style with 1 } on each line and not indented the same way as the loop it completes, so I understand that others can't read mine — but what do I care in a contest?

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

То чувство, когда ждешь обновления рейтинга worse больше чем своего

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

Дайте нам рейтинг!

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

А что, если нам не обновляют рейтинг, потому что worse сломал систему?

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

i think worse today will cause unexpected behavior for code-forces rating system. :-D
btw he was in my room.

[http://codeforces.com/contest/472/room/131]

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

Why was the time limit of D so tight? Even n^2logn solutions got TLE.

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

Похоже все как и я не ожидали, что у worse будет там мало плюсов к рейтингу за этот контест.

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

you are very good and smart!good boy,so cute~sorry my enlish is bad,hope you can understand.I don't want tell you I lost my sleep and very boring and don't known what I say,why me is so foolish ..TAT...hhhhhhhhhh,good luck and good night:D

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

Talking about records... (which I mentioned here http://codeforces.com/blog/entry/13997#comment-189548). I thought that I may have just experienced the biggest drop of rating in whole Codeforces history (-132), but it turned out that tourist got such hopeless place — 21st and got -135 to rating :P. In regular Div1 contest, not joint with Div2, it is impossible to fall below -110 even if tourist would get last place :P.

Frankly saying, I prefer regular round than those joint ones.
Additional easy A and B cause that they are worth 500 and 1000 and other tasks are each worth additional 1000 and in that case having standard D (here F) accepted in second hour is worth less than standard B (here D) accepted pretty quickly. That is obviously bad feature.

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

worse only got +319...

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

In problem D, I don't know why the first one is wrong and second one correct.

d[u][v] = d[u][LCA] + d[LCA][v] --> WA

d[u][v] = d[u][root] + d[v][root] - 2 * d[LCA][root] --> AC

Oh lala :'(

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

Anybody help figure out why my submission 8015497 of Problem D is wrong at test 9? Thx.

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

    Included it in the announcement.

    btw, congratulations for become master again!

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

      Thanks! :) And, certainly, thanks for the great round and interesting announcement!

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

Because of really good pretests, short (and quite boring) describtion of hacks can be found here.

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

жалко Arterm-а, он занял 26 место...

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

Comment Deleted

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

Я предлагаю все соревнования Codeforces делать так: не делить всех на 2 дивизиона, а предлагать либо 7 задач за 2,5 часа, или 5 — за 2 часа. Первый тип пусть будут сложные соревнавания, а вторые — легкие соревнования. MikeMirzayanov что вы думаете?

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

    Зачем раз за разом tourist'у решать div2A?

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

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

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

Не подскажете почему задача D не прошла по ТЛЕ 10 тест на компиляторе MS C++, а на GNU C++ 4.7 получила АС ?

Решал: MST+DSU и DFS из каждой вершины для проверки расстояний.

Собственно вопрос даже не в том "почему", а скорее, всегда ли GNU будет быстрее MS ?

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

    Потому что ios::sync_with_stdio(false); в MSVC++ ничего не делает, потоки всё равно остаются синхронизированными и медленными.

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

      Спасибо, теперь понятно.

      Действительно отправил на MS с scanf\printf прошла, хотя немного медленнее.

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

I had a problem during the contest.My id "techboy" had been shown twice in the list which leads to same id.I solved three problems with 1 WA and 1 AC in A,1 AC in B and 1 AC in C. But it was showing that one id has got 1 WA in A and 1 AC in B while another one got 1 AC in A and 1 AC in C. So in the end i got double negative rating and also was far below in the ranklist than the position I should be in.I need help as soon as possible :(

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

I think cgy4ever in this competition put his name beside the names of all time big competitors... Just like in sample tests for problem C. :)

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

В первом предложении ошибка: Хотите выиграть футболу