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

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

Доброго времени суток.


Авторы задач сегодняшнего раунда – Михаил Мирзаянов и я. Хочу сказать спасибо Дмитрию Левшунову за техническую помощь в организации контеста, а так же Геральду Агапову и Николаю Кузнецову за написание альтернативных решений.


Желаю всем удачи!


UPD: Контест закончился, всем спасибо за участие.

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

14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
И те удачи!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Большого всем рейтинга =)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
i write a code for problem B but when i wanna submit it doesn t going to go accept.....and say "Idleness limit exceeded on test 1"..
what sahould i do????????????????
i run this program correctly
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче С может кто-нибудь пояснить второй пример?
А то условие то вроде понятно... а вот откуда там 12 в выходе не пойму)))
Походу чего-то не заметил)))
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    вес между 1 3 равен 5
    вес между 1 2 равен 1
    вес между 2 3 был равен 8, но теперь равен 6.
    5 + 1 + 6 = 12

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не могли бы вы выложить тест 9 для задачи d?
14 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится
А почему такая задержка во времени изменения рейтинга после контеста?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    а тебя пару минут подождать не устроит?)))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
если можно по "E. Тест" тест 3 выложите, пожааааалуста...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    syvncqmfhautvxudqdhggz
    hrpxzeghsocjpicuixskfuzupytsgjsdiyb
    ybcmnmnbpndbxlxbzhbfnqvwcffvrdhtickyqhupmcehls

14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
FAQ really needs a link from main page. The amount of failed submissions because of %lld %I64d issue is huge.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Any ideas for problem C?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    If query cost is less then current cost then enumerate every pair of verticies and try to update cost betwen
    them like if the shotest path go through according edge. So update cost for any query is O(N^2)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Let (u, v) be a new road with length d.

    First, see if this new road is actually better than the shortest path from u to v. It may not be :)

    Assuming it's an improvement, set a[u][v] = a[v][u] = d. Then, run Floyd-Warshall to update the shortest distances. Normally this would be O(n^3), but because only the distance between u and v changed, it suffices to use only u and v as midpoints, reducing the time to O(n^2). Given 300 roads, the total runtime is 300 * O(n^2) ~= 300^3 which is quite fine.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    The one really mean thing to watch out for is that you need to use a 64-bit integer to hold the output.
14 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Marek, welcome to codeforces
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
никак не мог сдать С, после контеста сменил данные с "инт" на "лонг лонг" и все прошло. Откуда там такие длинние числа ? таж же ответ не превосходит 300*300*1000 или я ошибаюсь ?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    1000 - это длина одной дороги. А кратчайшее расстояние между городами может быть соответственно 300*1000
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      нет, почему же....мы добавляем кождый раз некое ребро, тоисть  мы сумму попарных расстояний не увиличиваем, сначала она не превосходит 9*10^7 и потому ответ тоже инт, где неправильно ?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I got a PE for problem D!!!!  Is there something wrong with the judge? 

  • 14 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    I've got PE on 8 test, and you?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Maybe you don't output line breaks?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        when I correct : if (col = Used[i1]) 
        on : if (col == Used[i1]) 
        I get AC(((
        stupid bug((

        ЗЫ: интересно, какая разница между = и ==?


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

          "=" means assignment, so your expression can be written this way:

          col = Used[i1];

          if (col ){...}

          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            if (col = Used[i1]) { ... }

            col will equal Used[i1]  and thereafter
            expression will true if col not equal zero
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    There are no special cases for PE in this problem. You can get PE if you either output not an integer or output city index that violates range [1, n] or your number of days is negative.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не подскажите, какая идея в задаче С? 
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Рассматривая ребра по очереди (1..k), например, с вершинами v1 и v2 и весом w (если w > d(v1,v2), то матрица не изменится), перебираем все остальные пары вершин p1 и p2. Дальше расстояние между p1 и p2: d(p1,p2) = min(d(p1,p2), d(p1,v1)+d(v2,p2) +w,  d(p1,v2)+d(v1,p2) +w).
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Может кто-нибудь подсказать хинт для задачи E?
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
выложите тест 8(задача D) и тест 3(задача C). спасибо
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тест 8 в задаче D:
    10
    5 9
    8 5
    7 6
    7 9
    3 9
    2 1
    7 2
    3 6
    7 1
    Тест 3 в задаче C:
    3
    0 983 173
    983 0 810
    173 810 0
    3
    3 2 567
    2 3 767
    1 2 763
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задачу "Тест" решить как-то можно с использованием суфф. деревьев? кто, как решал?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    можно использовать КМП (алгоритм Кнута-Морриса-Пратта), можно хэши. я использовал второе
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      КМП - это для двух строк. А третью сюда как можно приплести?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Находим строку минимальной длины, которая содержит в себе S1 и S2
        Потом к имеющейся строке прикручивает S3, если конечно S3 не является подстрокой.
        Вроде так должно работать, не успел этот алгоритм допилить :(
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Использовать кпм для первого и второго и потом еще кмп для второго и третьего (порядок следования слов нужно перебирать). Ну и еще надо учитывать всякие крайние случаи, когда какое-то слово принадлежит другому.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        ну, расскажу сразу решение:
        1. проверяем не являются ли какие строки подстроками других строк. если это так - лишние строки выкидываем, ясно почему так можно сделать
        2. склеиваем особым образом все оставшиеся строки во всевозможных порядках. например, чтобы склеить 3 строки a, b, c (в данном порядке) надо из c выкинуть наибольший префикс, совпадающий с суффиксом b, а затем из b поибольший префикс, совпадающий с суффиксом a и только после этого замерить длину a+b+c (+ - это контатенация). собственно, для нахождения наибольшего префикса (за линейное время, желательно) и нужны КМП или хэши.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Понял. Я думал, что недостаточно рассматривать только первое вхождение. Оказывается достаточно.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Я решал хешированием. Сдал правда на дорешивании
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    обичний кмп. для всех перестановок первих трех строчек делаем такое решение: с помощю кмп сливаем первую и втрою, то што получилось сливаем з третей строкой. слития 2 строк происходит: если 2 входит в 1 (проверяем кмп) то ответ 1 строка иначе ответ 1 строка +(2 строка без первих к символов) где К то што у нас получилось после виполнение КМП(максимальное количество первих символов 2 строки которие совпадают з первой строкой). КМП можна заменить хешами з бинпоиском. Кстати
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      хэши, кстати, без бинпоиска:)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не сильно думал над реализации з хешами. Писал КМП.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          ясно)) но я точно могу сказать - без бинпоиска:) писал хэши.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    во втором дивизионе Укконена не бивает=)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не знаю как точно описать мой алгоритм, но все же попробую:
    - кидаем все слова в бор (тоже самое что суфф.дерево, только добавляем не все суффиксы, а только слова целиком).
    - затем просчитываем переходы на этом дереве, например если стаю в какой-то вершине, то в какую вершину перейду если допишу определенную букву ( алгоритм Ахо-Карасика), это похоже на КМП на дереве, если можно так сказать.
    - для каждого состояния я буду знать какие из данных слов входят в текущий "спуск" ("спуском" можно названть строка от корня до текущей вершины, не знаю как правильно это назвать).
    - очередь по этому дерево и по переходам которые я просчитал, с запоминанием состояния (i,j) - был ли я в i вершине с набором j (набор двоичное представление какие строки я уже собрал какие нет, то есть от 0 до 7 включительно)
    Граф не взвешен поэтому мне надо найти первое состояние когда я пришел в (i, 7).

    З.Ы. наверное очень непонятно, но как есть, заранее извиняюсь за незнание терминологии.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
описался))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is there any way to see test case 8 for problem D? It cries "presentation error" everytime and I've ran out of ideas what to do.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
i also got presentation error in test case 8..
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а когда будет разбор??
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In problem C, I think that road length over 1000. The following code is runtime error on test 4.

const int N = 310;

int main() {
  int n;
  scanf("%d", &n);

  int g[N][N];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      scanf("%d", &g[i][j]);
      assert(g[i][j] <= 1000); // runtime error...
    }
}
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is it also possible to get test case 10? :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    39
    6 13
    15 39
    10 35
    31 28
    4 21
    12 39
    3 7
    3 13
    6 1
    5 14
    36 28
    12 15
    18 38
    30 29
    19 34
    36 16
    20 22
    8 13
    38 32
    26 39
    21 37
    1 7
    15 27
    12 26
    8 3
    6 14
    29 2
    25 23
    32 21
    5 16
    32 25
    6 8
    13 10
    23 30
    34 37
    29 33
    28 14
    36 5
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can somebody tell me the maximum range for integer(int) in gnu c++. I got WA for problem C,but when i submitted using long long it accepts. But the sum could be as maximum 9*10^7. that could be in 32 bit integer!!!!
sorry for my poor english.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    no.
    each edge on the original graph can be at most 1000.
    So, the maximum value of an element in the shortest path matrix is 9*10^7, as you said.
    So, the sum of the elements may be greater than the integer range ( ~[-2^31, 2^31], if I am not mistaken )
    hope it helps.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Maximum value is 3*10^5, but there is about 45000 elemnts
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        my bad!
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        The total number of elements are 45000,that is ok,but you are telling that the maximum value is 3*10^5 for each element..I don't know how,because the given matrix it is not the edges from i to j, it is the shortest distance from i to j and it is within 1-1000,so the sum cannot be more than 4.5*10^7. i am confused :(
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Shortest distance from i to j may be up to 299 * 1000 - for example if graph is path with 300 verticies and each edge costs 1000
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          sorry, i found my mistake, i
          "a given matrix is a matrix of shortest distances for some set of two-way roads with integer lengths from 1 to 1000, such that from each city it is possible to get to any other city using these roads." i misunderstood the last part.  
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
i'm getting WA in testcase 26 in problem E. is there some trick in this testcase?
and if it is a small testcase (post-able) i'd be really grateful if anyone can post it.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    The 26th test:
    The first string consists of 92235 letters. Letter in position 81200 (1-based) is 'z', the others are 't'.
    The second string consists of 68546 letters. Letter in position 40450 (1-based) is 'z', the others are 't'.
    The third string consists of 92026 letters 't'.
    The answer is 120123
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хотелось бы 6-ой тест в Е. :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    возьму чей-нибудь исходник, сгенерь тестов и сравни... генератор можно такой - берем произвольную строку и из неё произвольно вырезаем три подстроки, вот.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    6-ой тест в Е:
    rdtevvmiqmfgvafkdypxjthzhfsbavmhgkavkfonscaokdxoscenpxrc
    ijbvueenzsmgkmkrskjspvfchwkqdglkxnrdtevvmiqmfgvafkdypxjthz
    kqdglkxnrdtevvmiqmfgvafkdypxjthzhfsbavmhgkavkfonscaokdxoscenpxrcivydtkrxjy
    Скорее всего не проверяется случай, когда одна строка содержится в другой.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо! Всё прошло теперь.
      А ошибка была другая — есть функция string press(string a, string b), которая решает задачу для двух строк. Однако я смотрел вариант press(a, press(b, c)), но забыл про press(press(a, b), c)).
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Is the problem E solvable by KMP? I'm getting WA on test 44. But, I don't know if I have some bugs in my program or I'm taking a wrong approach.

Thanks
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно тест 5 задачи A
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно, пожалуйста, 7 тест задачи C.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
You should learn about KMP, if you don't already know it.
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
Using KMP, it's easy to find for 2 given strings the longest suffix of the first one that is a prefix for the second one.
After that you simply try all posible permutations of the 3 strings given in the problem(watching for degenerate cases, when one of the strings is a substring of one of the other two..).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно, пожалуйста тест 2 задачи D.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это 2ой семпл
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо.

      К сожалению, эта информация меня еще больше запутала:

      Дело в том, что на втором сэмпле моя программа возвращает ( у меня дома)

      1

      3 1 1 4

      (Я считаю, что это правильный ответ:

      Разорван цикл 1231, оставшиеся цепочки 123 и 4567 соединины ребром (1-4). В итоге получается цепочка 3214567 из 6 ребер, соединяющих все вершины.)

      Программа выдает неправильный ответ на втором тесте (=втором семпле):

      1. Предложеный ответ (1 \ 3 1 1 4) не является правильным. ( почему?)

      2. Программа возвращает другой ответ

      а) неправильный формат вывода

            (после количества дней и четверок городов ставлю перенос строки. После последнего числа в строке пробела нет.)

      б) программа работает по-другому (??!!)

      3 ...

      Честно говоря хотелось бы разобратся в чем причина. Другие идеи приветствуются.

      Зараннее спасибо.

      vanjonito.

      б) 

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        На тестирующем сервере программа выдает другой ответ:
        1
        3 1 4 4
        Проверил в Visual Studio 2005 - точно так же