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

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

Всем привет!

Недавний тестовый раунд прошел хорошо. Ожидается, что теперь все будет работать быстрее. В подготовке задач сегодняшнего раунда принимали участие: Михаил Мирзаянов, Николай Кузнецов, Иван Фефер и Мария Белова.

Удачи!

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

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ну наконец то появился этот пост. Долго я его караулил )
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Странно, KirillB находится и в 100 комнате, и в 102. Но задачи сдаёт только в 100й.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Баг :( Забавный.. Во время раунда уже не поправить, но потом исправим.
14 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
почему на 1 тесте в задаче D нельзя получить ответ
3
3 2
2 1
3 2

Он так же приводит к правильной расстановке
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что за странный вердикт :
Неправильный ответ на взлом 1
?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это значит, что твое решение прошло все претесты, но не прошло 1-й тест на котором взломали предыдущее твое решение.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ты должен пройти тест, которым тебя взломали.

    Читаем правила до контеста.

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

А почему я не вижу «вкладку» Взломы? Раньше вроде была.

Может конечно из-за того, что я вне конкурса, но всё равно странно.

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

И вот в который раз.... Открываю код для взлома, вчитываюсь, закрываю и... понимаю, что не моню чей это код. :(

Реквестирую подпись автора сверху.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А если я перепослал решение, которое у меня взломали, то оно проверяется на этом взломе?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В задаче D на первом тесте может и быть такой ответ?

2 3

1 2

2 3

14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Неплохой контест получился)
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Великолепный раунд!
Спасибо составителям и Всем, кто принял участие в создании и подготовке!
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
какой 4 претест в B?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Был баг ,  когда было системное тестирование , некоторые задачи отображалось "в очереди", а некоторые "претесты пройдены".
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я не думаю, что это баг, возможно это сигнализировало о том что задача следующая в очереди, т.е. закончит теститься посылка другого участника-начнется твоя, или как-то так. Во всяком случае, если это и баг, смысла исправлять его не вижу.
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
И правда быстро. Может конечно сегодня тестов*посылок было меньше, но всё равно быстро. :)
14 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Похоже, проклятье КФ на этот раунд меня покинуло:) Чтож, проверим дальше, тенденция ли это или случайность:)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а рейтинги когда поменяются?
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Увеличение производительности сайта заметно - сегодня систесты завершились всего за 14 минут!=)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
2nd one is a little bit confusing.. Especially "If those rules don't indicate the size of the cut are clearly, then the way with which the cut part possesses the largest area is chosen."
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Was the site running extremely slowly or was it just my connection as both have been having their ups and down recently :P
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно, а есть ли кроме меня умельцы, которые получили WA на D на финальных тестах?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня почему-то последний тест не пройден... Был бы виден последний тест полностью, можно было бы хоть понять, что не так.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хотелось бы узнать, как решается последняя задача
  • 14 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится
    Первое, что надо было заметить - n <= 10. Это значит, что решение экспоненцеальное, и можно перебирать какие-нибудь подмножества. Так и сделаем.

    Давайте посчитаем динамику по подмножествам: d[m][subm] - количество способов сделать связанное дерево из подграфа m с тупиковыми вершинами subm. Ответ будет суммой по d[2n-1][x], где кол-во единичных бит в x = k.
    Как пересчитывать: для пустого множества и множества из двух вершин (либо 0, либо 1) - очевидно. Теперь для большего: переберём i из subm - какой-нибудь тупик. Отрежем его от дерева по некоторому ребру в b. Получаем дерево на меньшем множестве вершин и с либо уменьшенным на 1 множеством тупиков, либо с изменённым i на некоторое b. Добавляем к текущему ответу уже посчитанную динамику. В конце надо разделить на k.
    В принципе, наверное, всё равно, какой тупик отрезать.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      То что решение экспоненциальное можно понять также из того факта, что при k=2 нас просят найти сколько гамильтоновых путей в графе, а это уже NP.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        это #P :)
        • 14 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          Я так и знал, что меня опять прижмут за фривольное использование буквосочетания NP :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I have a little question about a challenge case in problem A of today's contest. In my room one coder wrote a subroutine where he checked for every address whether it matches with the "input" string. In order to do that, he run a for loop which checked character by character whether the "input" string matches with any of the addresses. His for loop runs like this:

for ( int i = 0 ; i < input.size() ; i ++ ) {
if(input[i]!=current_address[i]) break;
}

Now my question, shouldn't there be a runtime error when the size of the input is bigger than the current_address, given all the other characters are equal?

I challenged it and it failed. Can anyone explain why?
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    what data type of input && current_address?
    As I know a[big_int] will return 0 if it is string

    upd:
    I tried this code in g++:
    string a("abcde");
    cout<<(int)a[17];

    It prints 0
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Wouldn't there be an exception?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        No any exceptions,errors.
        Just 0
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          You are wrong, as far as my tests tell.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Can you show me code you are tried?
            And.. language?
            • 14 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
              No problem. I used C++ and string. (as I suppose this is what is used in the solution shown above, though I am not sure).

              So I tried the following:

              int main()
              {
                  string str = "codeforces";
                  cout << str[11] << endl;
                  return 0;
              }

              It banged, crashed, exploded. Still, I agree that if current_address is char[], then the code will not crash and everything will go smoothly, exactly because of the '\0' character you spoke of.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                do you use MS Visual C++?
                I tried this code:
                #include <string>
                #include <iostream>
                using namespace std;
                int main()
                {
                    string str = "codeforces";
                    cout << str[12] << endl;
                    return 0;
                }
                it runs successful on my computer(g++) and in tab "Run" on codeforces (g++) but crashed in MS C++
              • 14 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится
                But '\0' is at str[10], not at str[11]. isnt it?
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  You are correct, now as I changed the index it really runs smoothly. Cool I did not know that.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Can you point to this solution?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Hm, if it is char[],first symbol after End of String will 0 too
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Вы наверное пошутили, когда так распределили задачи по сложности?!
В ACM системе это не играет роли. Но здесь! Задачи С и D в сумме легче, чем задача B. Задача A легче задач C и D. Как результат я сдал более сложные A, B и косячнул с размером массива в D. Да, ошибка уровня дебила, но как результат почти все, оказались выше меня! Потому что задачи C и D это вообще детсад какой-то. Это очень сильно напомнило Воронежскую олимпиаду прошлых лет, где за более сложные задачи дается меньше баллов, чем за простые.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Плохо конечно, что за лучшие задачи дают больше, но уж от этого никак не зависят твои ошибки с размером массива..

    Да и посмотреть какую задачу решать можно по монитору(т.е по кол-ву сдавших)
    • 14 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится
      Ты вообще понял мысль или нет?! Ты сначала прочитай внимательно, а потом отвечай. Какая разница в каком порядке решать? Баллов все равно будет в разы меньше. Задача D приносит НАСТОЛЬКО больше баллов, что в сумме A и B ничего не решают. А тут каждая из задач (A или B) по сложности превосходила D. Мне кажется, что надо делать все задачи равными по количеству баллов и убирать упорядоченность по сложности (это понятие субъективное, а оказывает существенное влияние на расположение участников в итоговой таблице).
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Не согласен, что A - сложная задача.
        Особенно для любителей Java, обладающих методов startsWith(), определяющим, является ли строка префиксом данной или нет.

        Согласен, что B сложнее, чем C, и чем D, так что распределение баллов действительно неадекватное.

        Но в целом все задачи, кроме последней, были слишком легкими, о чем говорит трехзначное количество решивших по каждой из них.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          Абсолютно согласен. Решать надо было все четыре задачи. 
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А как решать D?
        • 14 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          перебираем по очереди a-шки.
          Ищем для нее ближайшую равную ей b и свопаем ее до нужно места, потом переходим к следующей a.

          UPD: большинство решений что я смотрел были предельно понятны, так что имеет смысл посмотреть просто чье-нибудь прошедшее решение
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Кстати кто-нибудь чекер смотрел??? Авторы поугарали, отсвопали 300 равных чисел по 100500 раз:)
        • 14 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          Похоже на сортировку методом выбора.
          http://ru.wikipedia.org/wiki/Сортировка_выбором
          Только выбираем не минимальный элемент, а необходимый.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        На Топ Кодере задачи имеют разные баллы и все довольны. Иногда 900 бывает проще, чем 500. В чем противоречие? Общий принцип один - решай больше задач, получишь больше очков. Не умеешь безбажно сдавать халявы - значит не спеши. Или тренируйся спешить без багов. Вероятность завалить халяву есть у всех, но чем кодер лучше, тем она меньше.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          По идее раз задача - халява, то за нее должны давать меньше баллов, чем за не халяву. Тут же было наоборот.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            ну ошиблись тут с баллами (видимо авторы разные - не согласовали) не отменять же из-за этого разбалловку
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              слова об ошибках с баллами и что задача А сложнее задачи Б, подразумевают наличие критерия сравнения сложности задач... я пологаю такого критерия нет...
              • 14 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
                раз есть баллы значит должен быть критерий
                на тк кстати тоже подставы с этим бывали, так как присутствует субъективность оценки

                разумеется оценка должна быть примерной, с которой согласно большинство
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Я имел в виду, что оценка сложности (баллов по задаче) - это субьективное мнение авторов... Они вправе решать как считают верным...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не парься особо, я, например, аж 2 раза накосячил, как ребенок :)
    Один раз - площадь в int-ах в B, второй раз - не поставил break из цикла после обмена в D.

    На самом деле, конечно, порядок задач по сложности: A,C,D,B или даже C,A,D,B...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Чтобы не ошибаться с размером везде пишу вектора, даже для деревьев. Тоже ошибся с распределением задач, все посдавали С на 8-20 минуте, я ее запинал на 32. Насчет А ты не прав, минуты за 3 набил и еще 4 минуты искал где еррор:). D сдал на 52, и хорошо еще что решения некоторых задач у моих соперников оказались палеными, потому что меня по баллам обгоняли. Но-это хороший урок. Не всегда надо читать те задачи которые "дешевле", в который раз на эти грабли наступаю:) 
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      > Чтобы не ошибаться с размером везде пишу вектора, даже для деревьев.

      Извини, но по-моему это немножко быдлостиль.

      Когда-нибудь по времени не успеешь с таким подходом. Владеть надо обоими.

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Неужели vector <vector <int> > v(n) намного длиннее написать, чем int v[1111][1111]???
        Зато так гарантированно не ошибешься - все ошибки с выходом за границу массива/вектора ловятся сразу. Так что насчет быдлостиля я не согласен.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Чо-то глупость какую-то ты сказал.
          Я вообще-то про время выполнения, а не про написания.

          Например на полуфинале 2009 не зашел vector < vector < string >> с TL, но зашел char[MAXN][MAXM][MAXLEN];
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Я тут читал бложек и наткнулся на интересную фразу "Причём на второе место мы переместились только после того, как я вытребовал на форуме снятия у нас двух лишних попыток по задаче 11 из-за ещё одного из глюков. Суровый Паша Хаустов, лидер команды ТПУ, по поводу этого (вернее, не совсем этого) до сих пор рвёт и мечет – всем любителям троллесрача можно рекомендовать почитать."
    Кажись, ничего с тех пор не изменилось.

    P. S. Никого не хотел обидеть, просто фраза объясняет ситуацию :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
so, those who are not in div2, were not allowed to open any solution? or it was a problem here? I just wanted to see some people's code (no intention was for hacking :P) but it didn't allow me to do so...
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    you can see and hack solution in your own room( This room consist of users from your division only)
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
+83   and blue  :D , All effect of "rng"  thanx rng_58.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Ребят, кто задачу Е решил? Как вообще она решается? Была идея на meetinthemiddle для путей, но понял что идея палевная:)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Перебором,наверное. Мой дошёл до 11 теста,но его можно было оптимизировать и оптимизировать :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      поподробнее идею перебора расскажи.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
      За что минусанули человека?:)

      Я решал перебором за O(числа деревьев). Деревьев <= n^(n-2) так что по времени проходит да и память сэкномлена по сравнению с динамикой:). Идея перебора хранить маску посещенных вершин и маску тупиковых, а при переходе пытаться увеличить дерево из первой (по номеру) тупиковой вершины после чего эта вершина перестает быть тупиковой (для алгоритма т.е. она удаляется из подмн-ва тупиковых). Ясно что при такой рекурсии ни одно дерево соответствующее пути(стэку) рекурсии не встретится дважды.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Я не решил, но в конце появилась такая идея.

    Перебираем все возможные подмножества тупиковых вершин.
    Для оставшихся вершин считаем количество остовных деревьев на них. (например по теореме Кирхгофа http://e-maxx.ru/algo/kirchhoff_theorem)
    А также динамикой считаем количество способов выбрать из каждой тупиковой вершины по одному ребру, так чтобы в каждую нетупиковую входило хотябы одно ребро.
    Перемножаем эти два числа и прибавляем к конечному ответу.

    Наверняка есть способ проще ;)

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

      UPD
      а, прошу прощения, дошло))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В чем может быть ошибка алгоритма для задачи E
Перебираем всевозможные комбинации n-1 ребер из всех m ребер, проверяем полученные графы на связность, считаем количество тупиков и если кол-во совпало с k прибавляем к ответу?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Do we get tutorial for this contest?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem B test 7,  the input is 99 100 and the answer is 80 64. But what if the answer is 64 80? My program told me the latter answer and I think it's more reasonable--people would usually like to cut pictures as consistent with the origin ratio as possible, wouldn't they?

  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Read carefully problem statements. Tiebreaker is maximal height. Only statements is source of logic in programming contests.