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

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

Добрый день.

Сегодня пройдёт ещё один раунд по правилам codeforces. Автором сегодняшнего контеста являюсь я. Раунд помогали готовить Артём Рахов и Мария Белова. Большое спасибо им и всем борцам фронта codeforces!

Желаю всем удачи и весёлых хаков!

P.S:  В связи с проблемами работы сервера раунд признан нерейтинговым. Приносим извинения всем участникам. Подробности в теме по этой ссылке.

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

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

Этот контест только для первого дивизиона?

В чём смысл такого контеста?

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

    Если честно, я точно не знаю=)

    Вполне возможно он для обоих дивизионов. Надо будет спросить Артёма. Извиняюсь за своё незнание...

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

    почему только для 1 ?
    в списке зарегистрированых много людей с 2-див, вывод: етот контест для всех :)

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

      Думаю вы правы.

      Сейчас заредактирую пост, пока толпа недовольных с факелами не собралась=)

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Please don't to hard for the problem. . . I'm newbie on this. . . ^_^
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
If the problems are easy, the process of problem solving pleasure does not deliver.
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Народу под тысячу зарегистрировалось ... как бы чего непредвиденного не произошло... ))
Может, на всякий случай, задачи в pdf  выложить?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    все равно самая большая нагрузка будет в самом начале и в самом конце. И я думаю, нагрузка на сервер с задачами в pdf будет не меньше.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      Меньше конечно, особенно если он сторонний :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        я помню в каком-то из раундов ссылка мне никак не помогла, потому что по ней я тоже долго не мог скачать условия. Хотя, конечно, если бы не выложили, может быть сервер лежал бы намного дольше.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Произошло). Но так часто бывает.
13 лет назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится
sorry to say that but if the server isn't strong enough just limit a registration number : )
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Already plused you, but I just gotta say I have the same feeling: codeforces should limit registrants, until it has enough resources to handle more competitors. May be an stress test would be good....
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Why don't you allow to register just before contest ? :( , the site was down for sometime and when its back, registrations closed :-/
13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
It's better to be in tightness, but not in offence
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
the server is not responding.. i m trying to open the problems, but it is saying that competition not started but it has started... WAT TO DO???
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
это сейчас контест отсрочили уже во второй раз?
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Wait 5 minutes, after that again 5 minutes, and so on...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I cant come in into contest room T_T. . . .
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Может быть, коли сервер не справляется с разщовым наплывом, чуть поменять правила: или выкладывать задач за 10-15 мин. до начала отсчета, или штраф начислять начинать не с первой минуты, а с11-ой или м 16-ой. Суть не изменится, зато "низкий старт" ровно в 19:00 будет уже не столь актуален, наименее нервные и наиболее уверенные в себе задерждатся на минутку-другую - глядишь, и сервер выдюжит. 

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I registered for the contest, and when the timer got to 0, it gave me the pop-up to enter the contest. I saw the first problem, wrote a solution, tried to submit, and was told I wasn't registered O.o

Indeed, I don't seem to appear on the registration list, but I must have been registered or that pop-up wouldn't have appeared, right?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    No, spectators see popups too. They can read the problems, but can't submit.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Good to know. I'll double-check that my registration has gone through next time.

      And I see a typo on the Score Table on the problems screen. "Successfull" and "Unsuccessfull" should each have only one "l" at the end.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I'm trying to hack, but I always get "submit already challenged" although I keep seeing the submit! Please clarify this issue.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It is because of server unstable work. Sorry.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Thx for answering Mike. I guess error is maybe due to the fact that my hack case was quite big(100 thousand chars). I was able to hack using the generator feature, instead of pasting directly my hack case. Maybe this information can help.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
During the contest you can't see it.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
For some reason I have two passing submissions for problem B, still I have +1 for that problem in scoring. Is this my mistake? My browser seemed frozen, so I submitted again.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I , too faced a lot of problems from the beginning and during the contest .
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I , too faced a lot of problems from the beginning and during the contest .
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
I think that it would have been better to have postponed the contest on the other day.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Or not rate it
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Yes but this is a waste of the round. I think that in the future if there are such problems it's better to postpone the contest rather than start it with small delay.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
It keeps on crashing! And I am getting compilations errors which are server related problems. Please check...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What does Problem D mean?
I stared at the problem for 1 hour and can't catch the meaning at all.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    We're asked to find such R, that probability of success(i.e. destroying no less then K buildings) will be at least (1000-eps)/1000.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      But how to calculate the probability of success?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        For a fixed R, you can use dp to know the probability.
        Consider a single building: either you destroy it with some probability p, and you still have to destroy k-1 building, or you don´t destroy it(with a probability 1-p) and you still have to destroy k buildings. You can implement it using memoization for an O( n*k ) solution( with R fixed). That's why you see people talking about binary search + dp: you do bsearch over R.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Даа, надо видимо подумать о стабильности:(
13 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится
15 успешных бездумных хаков одним генератором по одной задаче! Вот уж точно, "веселых хаков" =) Респект за B =)
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Обидно что в последнюю минуту сервер сильно лагал и ресабмит за 10-20 секунд до конца сделать не вышло.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Никак не могу понять. Пусть, например, в задаче 'B' в качестве входных данных будет много(100000) букв 'а'. Ответ же 100000 * 100000 неверен. Почему?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    64 битный тип данных нужен.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В этом то и фишка. Мое то решение прошло. А вот мой взлом - нет. Причем в протоколе попытки взлома было написано, что правильный ответ какое-то странное непонятное число.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вот что мне выдал чекер: 1187767296.
        Тест я сгенерил на ноуте. На нем моя программа выдает правильный ответ.
        Скопипастил тест для взлома - получил -50 баллов.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          скорее всего, тест длины 34464 :)
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            А почему так? Вроде бы на моем компе тест именно нужной длинны.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Возможно, что-нибудь где-нибудь обрезалось...
              Или же лаг спровоцировал частичную передачу теста
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Прочитайте условие задачи внимательнее: "Требуется найти количество упорядоченных пар", то есть пары (i, j) и (j, i) - различны
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    нет макс. ответ там будет 10^15, именно на тесте который вы написали
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Эх, растерял весь адреналин, пока ожидал начало контеста с 20-минутной задержкой.
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
cannot view the problems
cannot submit the code
cannot challange others
cannot watch the standing
only i can do ... goto bed at once ...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    This round probably won't be rated.
    • 13 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится
      I hope so. since at the middle of contest , I became unable to submit and hack. I believe my rating may decrease by 200 if this round is rated.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Code Forces is so popular...
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Just wondering why is the duration of next contest 2:30 instead of 2:00?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
:(
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Lowercase Latin letters? It would be better if it is lowercase English alphabets in the statement. It always gets me ! :(
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    What's wrong with that?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      • Its not correct!
      • I don't know if they really mean that it is from 'a' to 'z', or if there are special chars involved.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        I think you can use the whole ASCII code to become the index of an array.
        Just to init an array with length 260 or more.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Yeah, next time i will do that!

          One more thing,
          in problem B, if i use printf("%lld\n",ans) it gives me wrong answer but accepts when i use cout<<ans.
          Why?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Test system based on windows, that's why minGW, not real g++ is used. Use %I64d or 
            cin/cout
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Thanks for clearing that! :)

              With one test case per file cin/cout would be a better option :D.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        I think the point is how to understand the value K and ε
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
ну подстава: сделал в задаче С всё в лонг-лонгах, а векторное произведение возвращаю в интах :)

как так можно? =)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Такие же подставы были на ТС)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    на сборах как-то из-за такого косяка wa на 60-каком-то тесте словили)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а я все в даблах делал и получил "Ошибка представления данных на тесте 29"((
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    У меня в С везде int. АС
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
My solution to B was hacked. However when I run the same program on my computer with the hack as the input, it gives the right answer! Could this be because of a system error?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I have had a similar problem, aren't you using %lld when printing and submitting it with compiler GNU C++? If so, try %I64d
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I use GNU C compiler....
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      The great problem was that "%lld" did not work properly on the server (GCC). I was not aware of this problem (on my computer it works well). This difference caused a lot of hacks in B. Sorry for that...

      Though even is "%lld" worked properly the number of int64 hacks would be huge=(

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Additional Info: The hack was extremely large, length ~ 10^5;
    I used a long long for storing the answer which was of the order of 10^10.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Maybe you have an 64-bit processor and your int is 64-bit? (The server's int is 32-bit.)
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Спасибо, Степан, за контест. Задачи интересные.
Не знаю, как я так умудрился накосячить, чтобы 3 последние задачи попадали. Дебил, наверное. С моим везением мне никогда не стать красным.
Огрооооооомное спасибо серверу за то, что я сидел и ждал кучу времени перед тем, как отправить задачу, а потом еще столько же, чтобы прочитать следующую. Ограничивайте вы уже количество участников на контест.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    вот это я понимаю - родственная душа!

    дай в други тебя добавлю, ибо у самого последние три не пойми почему свалились
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Есть ли возможность просмотра тестов?

Интересует 23 тест задачи E.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Меня тоже)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Тесты, где вы упали, можно смотреть:
      соревнование-мои поптыки-кликнуть по номеру попытки-прокрутить вниз
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Блин, точно, спасибо. Это макстест. Неточно извлекал квадратный корень. Поправил точность, зашло.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    да, а ещё тест 7 задачи D

    потому что уж очень непонятно, где собака порылась

    в E у меня есть квадратное тупое решение, и оно выдаёт такие же ответы, как и более быстрое до "500 500" включительно
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Количество просьб "дайте тест" что-то не собирается уменьшаться :))))
      • 13 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится
        Ну неплохо бы сообщить народу как-то подробнее, вроде даже на главной пост не появлялся.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          опять меня опередили =/

          в общем и целом, ниже я несу ту же мысль :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        и правильно, FAQ же по CF нету - откуда я знаю как тест посмотреть? :-)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вот здесь сообщается: http://codeforces.com/blog/entry/967. Этот пост был в прямом эфире, но слишком быстро оттуда уехал :(
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Все же его заметили не все по понятным причинам. Может быть попросите администрацию вынести пост на главную?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            я, честно говоря, его даже и не видел =/
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Посмотрев на посылки, думается, что скорее всего нужно было делать ДП, а не брать k наилучших вероятностей.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        а смысл? вероятность успеха - это произведение k вероятностей локальных успехов

        согласись, что при замене множителя на меньший получим худший результат
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          пусть есть два события
          вероятность одного - 2/3, другого - 1/4.

          Какова вероятность, что хотя бы одного событие произойдёт?
          Ответ: 1 - (1/3 * 3/4)
          Доказательство: вероятность того, что оба события не произойдут равна 1/3 * 3/4.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            зачем одно?

            конечно, может я совсем-совсем чего-то не понимаю...

            подзадача: есть n событий, нужно выбрать k из них так, чтобы вероятность успеха всех этих k событий была максимальна

            решение: возьмём наибольшие k вероятностей, их произведение - это вероятность успеха всех k событий

            где я неправ?
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              есть 2 события с вероятностью 1/2
              Вы говорите хотя бы 1 выполнится с веротяностью max(1/2,1/2)=1/2
              на самом деле 1-(1-1/2)(1-1/2)=3/4
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                догадался, почему я вам про Фому, а вы мне...

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

                не пойму правда, как это нужно было так подобрать сэмплы, (которые весьма нетривиальны), чтобы идейно неверное решение их прошло

                спасибо
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                но про максимум я нигде не говорил ;)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  берем произведение наибольшей одной.  это не максимум?)
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    я имел ввиду, что ровно одно событие выполнится, а не хотя бы одно событие выполнится

                    именно в этом моя ошибка :)
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Может пусть первый дивизион будет тока для первого?
  • 13 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится
    тогда взламывать будет так же тяжко, как и в 1-ом диве на топкодере ;-)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      но количество участников это немного сократит!=)*я Кэп=)*
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Это же плохо.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          А когда после каждого турнира во время тестов сервер падает - хорошо? Причем это еще полбеды, сегодня сервер часто не был доступен и во время контеста.
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          Когда сервак висит пол контеста - хуже
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
И еще тест №7 задачи D.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня и у товарища Shtrix времена сдачи всех трех задач совпадают с точностью до минуты. И мы были в одной комнате. Прикольно)

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is the test 7 on problem D.

I use Greedy + Binary Search, but it seems DP + Binary Search.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    and test 10 for problem D please,thanks

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I used the second algorithm, but it failed at the same test.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    Yeah, it's a Binary search with DP.

    The binary search in in the radio.
    The DP is the following:

    let p be the probability of the ith building be destroyed with a certain radio.
    let DP[i][j] be the probability of destroying exactly j buildings taking in consideration the first i's (1-based) buildings
    DP[0][0] = 1.0
    DP[i][j] = DP[i-1][j]*(1-p) + DP[i-1][j-1]*p;

    Then you check the sum of DP[n][0...K-1].

    Unfortunately I did this correct but the limits of my binary search were wrong [0-1010] instead of [0-2000sqrt(2)] and got W.A. during the contest and ACC a few minutes later.
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
For problem B, I was trying to hack with a string like 'aaa...' of length 10^5. However, testcase editor was automatically truncating the string to ~34000 characters without giving any warning. It took me 2 unsuccessful hacks before I found this limitation. I think it is not mentioned anywhere what the default limit of the editor is.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Now you can use test generator,
    but I hope,it will fixed
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Yes, I used generator later. I was not sure how to use it, so I had to re-read the contest rules.

      Another thing for admin's consideration is to put the rules as a separate page instead of a blog post. I have to google every time I want to read the rules.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      How generator works? There are two things. One is file upload other is generate paramitre.Have to I use both ? and how?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Today I used generator for the first time. In my case, I just send my cpp with code that prints to standard output and that was enough.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You can submit a generator.
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Когда обновятся рейтинги? Или контест решили сделать нерейтинговым?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

okay....enough talk of server being busy...

can anyone point me my mistake for Problem B:

#include<vector>
#include<map>
#include<string>
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
map<char,long long > c;
unsigned long long int ans;
long long int j;
string s;
cin>>s;
j=0;
while(s[j]!='\0')
{

// if((s[i]<='z'&& s[i]>='a')||(s[i]>='0' && s[i]<='9'))

c[s[j]]++;

j++;
}
ans=0;
for(map<char,long long int>::iterator i = c.begin();i!=c.end();i++)
{
//printf("%d ",c[i]);
ans+=(*i).second*(*i).second;
}
printf("%llu",ans);
scanf("%*d");
return 0;
}



13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
WTF? I got correct answer of test case #48 of D in my computer, but wrong answer of case #48 in judge? any one help?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
у меня в задаче С на 8 тесте все правильно выводит, а на сервере валится, выводит другое число.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Will this match be rated?
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
Очень странно. В дорешивании мой код на Сшку заходит под компилятор Microsoft Visual C++, но дает wrong тест 4 под GNU. Вместо 8 программа почему-то выводит 2. Локально под GNU C++ 4.5.1 под Linux (2.6.36  ядро) все работает. Что бы это могло быть?

UPD: это не ошибка вывода 64-битных чисел. изменение printf("%lld") на cout или printf("%I64d") дает все тот же wrong тест 4.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Это как так? о_О

http://codeforces.com/contest/50/standings/2
253 Prabhu
задача A

338 / 00:56

00:44:02  Неправильный ответ на претест 2 [претесты]
00:56:30  Полное решение [финальные тесты]
01:30:27  Неправильный ответ на претест 1 [претесты]

UPD: А, торможу... Тогда странно, что синим цветом выделяет.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мб второе решение было верное, а после него неверное и оно не принято на проверку раз неверно уже на претестах?

    хотя смысл сдавать когда есть верное решение? 

    хз)
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Ну причина перепосылки могла быть такой: автор нашел баг и решил отправить более корректное решение (хотя судя по вердикту - это не так :).
      Я просто заметил, что почему-то посылку выделило синим в таблице.

      Видимо проблема в
      <span class="cell-accepted">338</span> (у Prabhu)
      <span class="cell-passed-system-test">336</span> (у пользователя ниже)

      Т.е. неверно определён класс ячейки у тех, кто посылал решения, после посланного верного, которые не прошли претесты.

      UPD: либо тут что-то более хитрое...
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
I got WA on test 21** in the final tests of problem B in the contest. And by changing printf("%lld\n",ret); to printf("%I64d\n",ret); I got accepted in the practice!!!

Anyone please reply if this is fair to get WA in the contest!
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You are not first)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It is impossible to get WA in the contest. The maximum cases must be only in final tests.
    P.S In WinGW you must use %I64d for long long and double instead of long double.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Further more, I got three unsuccessful hacks because I didn't know that my whole test case isn't pasted!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
D была намного проще чем C. Кто поддержит? :)
D как-то больше на див2 тянет (идея видна сразу, просто имплементировать надо корректно).

Кстати как решить C ? 
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Они одинаковые по сложности, С это выпуклая оболочка. Дальше бежим по точкам оболчки и срезаем где можем (т.е. расстояние равно максимум из модулей разностей координат соседних точек)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не уверен, я решил c, не решил D
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    строим прямоугольник и срезаем у него углы.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задачи ужасно лёгкие, но я тупил.
По D использовал 60 итераций бинпоиска, а для AC надо было использовать 62!
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Жадность это плохо (с)
    Что видно по куче хаков по задаче Б и прочем. Все никак не заставлю себя вообще нигде не жадничать)
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Печально,что контест нерейтинговый=( Это наверное мой самый удачный контест.Я даже губу раскатал что пожелтею ан нет=)Неприятно что сервер время от времени лежал.
Хочу сказать отдельное спасибо авторам за контест=)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Looks like there are two different approaches for problem C. Could anyone explain the ideas?   
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    My approach was to change each point p(x,y) into four points p1(x+1, y), p2(x-1, y), p3(x, y+1), p4(x, y-1). Then run convex hull and result is sum i = 0..|CH|-1 max(|CH[i].x-CH[i+1].x|, |CH[i].y-CH[i+1].y|). CH - convex hull.
    Edit: However I saw much simpler and linear time solutions.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Find 4 points: min by x - y, min by x + y, max by x - y, max by x + y. Convex hull is a rhombus, the answer is max(x + y) - min(x + y) + max(x - y) - min(x - y).
    I thought about octagon at the contest and used 8 points.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to solve problem E? The submissions look short.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    I won't write a full algorithm, but here is the idea:

    First of all let's prove, that if the root is not integer, it's unique (that is, it can appear only once):
    Let x = -b + sqrt(d). In case x is also a root of another equation, there exists such u and v, that x = -u + sqrt(v). Then b - u = sqrt(d) - sqrt(v). That means, that difference between two square roots is integer, however one can prove that it is only possible when d and v are full squares, which isn't true (according to our assumption).

    Now if x is not integer, then let's check if it can be root of some equation.
    Since all roots are negative, for given x, we try to find negative y that
    x+y >= -n
    x*y <= m
    Apparently such y can be 1 for odd x and 2 for even x.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I want to say, that I think the problem statement D bomb is not so appropriate. Especially the word nuclear bomb. I think in my personal view that war is not a solution and some bombs, which have the capacity of killing millions of people, should never be used.
Howerver, If you would started the description like.
"Vasja is playing a game. In this game he has to drop..."

It would be much more appropriate.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I must agree, i found the problem statement rather offensive. 
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      How is it offensive? It's a programming contest problem, a fictional story, just like any action movie involving nuclear bombs. Don't take it personal.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

В задаче С по ходу выпуклая оболочка не нужна. Там ответ

( maxx - minx + maxy - miny ) * 2 - ( maxx + maxy - maxs ) - ( mins - minx - miny ) - ( maxx - miny - maxd ) - ( mind - minx + maxy )

Где maxx, maxy, minx, miny - максимальные и минимальные координаты соответственно, а maxs, mins, maxd, mind - максимальные и минимальные сумма и разность координат соответственно. Все максимальные надо потом увеличить на единицу, а минимальные уменьшить.
 

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

    Там еще все сокращается и ответ получается maxs + maxd - mins - mind.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ой, ромбик! и как я не догадался...
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
        я не минусовал, но там вроде как не ромбик)
        в худшем случае можно обойти 8-угольником
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Там всё-таки не ромбик, а прямоугольник со сторонами под 45°. Да и то его нельзя рисовать, потому что у него вершины могут быть в точках с полуцелыми координатами. Но это, конечно, мелочи. Я тоже тупой, Грэхема написал...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я так и делал... но до сокращения не дошёл... наверное, не до того было... здорово! :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Но на контесте я написал вот такую формулу (с abs), чтоб не париться

      2*(ymax-ymin+xmax-xmin+2)-(abs(dmin-xmin+ymax)+abs(dmax-xmax+ymin)+abs(smin-xmin-ymin)+abs(smax-xmax-ymax))

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
204 комента o_O вот это да!