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

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

Пока все мировое сообщество спортивных программистов затаив дыхание ждет новостей о времени и месте проведения финала, мы решили не затягивать с раундом и в поезде по дороге из Петрозаводска в Саратов придумали задачи. В купе присутствовали – Михаил Мирзаянов, Артем Рахов, Максим Иванов. Задачи перевела Мария Белова.

Удачи!

Артем Рахов и команда Codeforces

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

14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Надеюсь раунд будет интересным :)
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Всем удачи!!!
14 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Ахаха. :D Ну правильно! Что делать в двухдневной дороге? Молодцы!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А если я забыл зарегистрироваться? Все, пролетел? или еще как-нибудь можно успеть зарегистрироваться?
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится
    К сожалению, всё.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Там перед раундом идет распределение по комнатам. Так, как новых участников распихивать по комнатам весьма затруднительно, регистрацию приходится закрывать за несколько минут до начала контеста.

    Хотя с другой стороны ничего не мешает добавить штук 20 фиктивных пользователей, распихать их по комнатам и раздавать людям, которые регистрируются позже.
  • 14 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    - коммент не туда -
14 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

19 * MrM    2454

410 00:45

820 00:45

1224 00:46  

20 * roxion1377   2244

374 01:03

748 01:03

1122 01:03

о_О научите меня так быстро программы писать.

че-то тут не чисто :D

п.с. это в комнате, которой я нахожусь))

http://codeforces.me/contest/59/room/104#

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
хмм :D 
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задачи доставили!
Давно не получал столько удовольствия от решения задач.
Спасибо авторам! Видать поездка хорошо прошла. :-)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, в тот момент, когда в положении написано "Ожидается системное тестирование", контест полностью исчезает со страницы "Соревнования"
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что за странный вердикт такой "Неизвестный вердикт:OTHER" ?? После этой попытки взлома ни плюса, ни минуса не появилось, пришлось повторять попытку.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Unknown verdict'ы и Ошибки тестирования - это результаты технических сбоев на одном из проверяющих серверов. В настоящий момент все уже исправлено.

14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
--- Копия ---
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Неизвестный вердикт:OTHER???
Нажал Взломать, через секунд 2 табличка с информацией окончание раунда. И Неизвестный вердикт:OTHER =) Как понимать? Я то нажал взломать до конца раунда
14 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
The page of this round is  just now became invisible?

EDIT: now available.
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Есть небольшой вопрос по 3-ей задаче. Вернее, по взлому моего решения этой задачи.

Тест взломщика:

5
???a????????????

Мой вывод:

bcdaeeeeeeeeadcb

Вывод тестурующей системы:

aaaabcdeedcbaaaa

Вердит взлома - успешный взлом. Чем мой вывод на этот тест не соответствует условию задачи?

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    надо было вывести лексикографически наименьший
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нужно лексикограф. минимальное решение
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ответ должен быть лексикографически наименьший.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    он не есть лексикографически наименьшим.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    лексикографически наименьший нужно выводить. 

    UPD: сорри я не видел ответов.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ответ должен быть лексикографически минимальным.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Ого, сразу 6 ответов! :D
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    Лексикографически наименьшим ответ твой должен быть
  • 14 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Интересно, какой из ответов на этот вопрос лексикографический минимальный?
    • 14 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      отсортировал:
      1. Нужно лексикограф. минимальное решение
      2. Ответ должен быть лексикографически минимальным.
      3. Ответ должен быть лексикографически наименьший.
      4. лексикографически наименьший нужно выводить.
      5. надо было вывести лексикографически наименьший
      6. он не есть лексикографически наименьшим.

      • 14 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится
        Эх, надо было с большой буквы написать =_=
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Вот оно что значит по правилам писать, так бы первое место занял=)
          • 14 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Как это нередко бывает, от первого места отделяет всего один байт.
            • 14 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится
              Да но достаточно редко, когда один байт откидывает с первого места в самый конец.

              P.S. АААААААААААААААААААААААААААААА!!! Надо было лексикографически минимальную строку!
14 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
Хотелось бы узнать решение (а лучше пояснение к задаче)  D. 
  • 14 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится
    Моё решение (верное).

    Искомый парень лучший в своей команде?

    Нет?
    Выводим 1 2 3 ... k-1 k+1 ... 3*n

    Да?
    Список людей в полученных командах:
    [Предыдущие] [ Наша команда: Искомый + Сокомандник1 + Сокомандник2 ] [Последующие]

    Q = MAX( Сокомандник1, Сокомандник2 )

    Для каждого из [Предыдущие] если он меньше Q, то кидаем в СПИСОК-1 иначе в СПИСОК-2

    Сокомандник1 и Сокомандник2 кидаем в СПИСОК-1

    Все [Последующие] кидаем в СПИСОК-2

    Сортируем списки, выводим сначала 1, потом 2.

    Почему кидаем именно так?
    Проверим тест
    3
    4 5 9 1 2 3 7 8 6
    4 5 9 1 2 3 7 8 6
    1

    правильный ответ
    2 3 4 5 6 7 8 9

    но у некоторых мог получиться
    2 3 4 5 9 6 7 8
  • 14 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    Решение которое прошло.

    1. Если он не капитан (в списке позже любого из сокомандников) выводим отсортированный список всех кроме него.

    2. Он капитан. Берем два списка и сливаем.

    Список 1. [его сокомандники отсортированные]+[люди, которые остались после момента выбора им команды, отсотированные]

    Список 2. [люди, которых выбрали до него, отсортированные]

    Замечание 1. + значит что списки просто склеиваем

    Замечание 2. Сливаем списки даже не смотря на то что первый не обязательно отсортирован. 

    Замечание 3. А работает это потому что у нас есть только одно ограничение. Те, которых он выбрал должны идти в списке перед теми, кто на тот момент был доступен. Все остальные идут в любом порядке.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как Е решать?
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится
    я решал так
    построим граф, в котором вершины - ребра начального, ребро между вершинами (a,b) и (b,c) если тройка (a,b,c) не является плохой.
    потом просто запускаем по графу бфс.

    UPD
    это решение прошло тесты.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Написал С, взломали из-за рантайма, собственно вопрос. может ли быть RunTime в таком коде? (Язык : Delphi 7)
var a : array['a'..'z'] of integer;
ch : char;
begin
ch := '?';
inc(a[ch]);
end.

У меня ошибку не выдаёт, но упасть, по-идее, только тут могло
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Конечно, упадёт.
    Проверку на границы массивов в Delphi еще никто не отменял. Возможно, на сервере есть {R + }, аувас{R-}
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
а что такое Ошибка тестирования?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    У меня тоже ошибка тестирования на двух задачах.
    Такой вердикт раньше получала только, когда во время дорешки сервер отрубался.
    Во время контеста такое со мной впервые.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    и у меня(    все ОК)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    у меня тоже было, но теперь перетестили и все ок
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Why are there so many judgement fails?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Гигантски странно!!!!!! В положении по задаче С у меня уже стоит минус, мол финальное тестирование не пройдено, а в статусе до сих пор скачет этот мячик и говорит, что пока еще проверяет!!!!
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Финальное тестирование не пройдено, и это правда, как ни крути.
    а -1 означает что была до этого неудачная попытка
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Нет, ты не понял. Вердикт по этой задаче у меня "в очереди", а в ранклисте уже пишет "финальное тестирование не пройдено"

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я понял. Оно "ещё" не пройдено.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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


          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ура, перетест всех ошибок судейства показал accepted. Большое спаибо
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вроде у меня было что-то похожее, это нормально, задача ещё не упала
14 лет назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится
Странно, написано, что пройдено уже 100%, а куча решений не проверено

UPD: видимо округление
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    система перепроверяет отправки у которых была ошибка тестирования
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
281538

my code is correct and is giving correct output on my system....can the moderator please let me know...what is the prob ??
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You can see the test cases for every question now. Go to your submissions and click on the submission code. Scroll down and you can see the test cases.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You can view the reason of fail looking to the tests of your submission.
    You can found tests and the results below your code.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      the case for which they are giving runtime error is giving the correct output on my system.....
14 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
Спасибо команде Codeforces за прекрасный контест!

P.S. эх до желтого немного не хватило(
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Спасибо за контест. Я наконец-то посинел)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо большое организаторам! С большим удовольствием порешал сегодняшние задачи!
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Действительно захватывающий контест. Такие контесты могут придумать только действительно талантливые люди. Большое, гигантское вам спасибо за этот контест
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Wow, good problems as always!

Could anyone tell me how to solve the problem E? Thanks.
My BFS timed out, because it is O(NMlogK).

  • 14 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    Let build new graph where nodes are edges of current graph and edge between (a,b) and (b,c) exists if (a,b,c) is not bad triple. Finally just run BFS in new graph.

    I used hash-table for checking bad triples and my solution has O(NM) time.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Similar python solution, but with set instead of hash-table also got AC, although it is O(n * m* log(k))

      Upd: python set also uses hash-table, so it is exactly same solution...
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      What is about the case when you have input date as 
      4 3 0
      1 2
      2 3
      3 4

      If we constructed a graph in you way we would have obtained the answer -1, because  the ways with only odd length from the given graph will be considered.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        No, we will have path (1,2)->(2,3)->(3,4) in new graph what is path 1->2->3->4 in old graph.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Hi Ripatti:
      Could you tell me your problem-solving process? I cannot solve thie problem, even if using a lot of time. Maybe I need to do more practice, what is the effective?
      Thanks a lot!
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Solving process... I just read problem and sometimes solution emerges from subconscious. Else I must to little analyze problem for to see a solution.
        Practice - yes. The more I solve the faster I find solution. But reading of algo books is good idea too.
        For fast solving hard problems you must solving more and more problems a lot of time. I solve nonstandard problems from primary schools. And now I cannot solve some hard problems whatever.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Hi cgy4ever,
    Please explain ur solution to Problem B : Fortune Telling.
    I like ur solution to this problem.
    • 14 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
      There is much simpler solution.

      #include <iostream>
      using namespace std;
      int n,k,r,m=100;
      int main()
      {
         cin
      >>n;
         while(n--)

         
      {
            cin
      >>k;
           
      if(k&1)
               m
      =min(m,k);
            r
      +=k;
         
      }
         
      if(r&1)
            cout
      <<r;
         
      else if(m&1)
            cout
      <<r-m;
         
      else
            cout
      <<0;
      }
      Explanation:
      1) The Result must be odd.
      2) If Sum is odd - return it
      3) Else if there was an odd element, find the least (m) of them and subtract from Sum - this is the answer
      4) Else if there are no odd elements at all, Marina doesn't love Sasha. :-( Return 0.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что-то уже час ночи и я совершенно потерян. Не могу понять что не так в моем исходнике по D. Может кто глянет? http://www.everfall.com/paste/id.php?bchdku9gxd8i
  • 14 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    while (aa < a.size()) c.PB(a[aa++]);

    Сдается мне там должен быть не c а res.

    А вообще весь хост можно упростить если не заводить отдельно b, а сгружать их всех в а, отсортировать а и с и последовательно вывести.

    Не так понял код =(

  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Практически не смотрел на код. Но код прошел после небольшого изменения:
    int R(int a, int b, int c)
    {
           
    int p = N3*N;
    :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо! А я моск сломал вчера. Зря я не юзал INF
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Hey there,
I have a question, does contribution affect one's rating? (I know that this is kinda irrelevant to this blog entry, but I dunno how to ask questions, the site doesn't have something like "[email protected]" or "Contact Us", sorry anywayz)
Thanks in advance
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Contribution and rating are independent of each other. Rating is a measure of one's success during the coding rounds. Contribution is a measure of one's positive influence on a community. Contribution doesn't affect rating.
    Btw, you might want to use google search to track codeforces information in a more comfortable way