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

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

Добрый вечер!

Скоро у многих начинается сессия, а у кого-то она уже в самом разгаре. Хочу пожелать всем отличных оценок и побольше халяв!

Раунд помогали готовить: Николай Кузнецов, Геральд Агапов, Иван Фефер.

Удачи!

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


UPD: 

Рейтинги будут обновлены позднее
  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всем удачи!)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Из каких символов состоит ввод в задаче B?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    a и b - обычные числа (т. е. из цифр 0-9, без лидирующих нулей).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче D можно перекрашивать одну и ту же клетку несколько раз?
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Задачи были интересные. Спасибо!
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Good Problems, but i have found that sentences in the question were not clear.

eg.Problem C He thinks that it does "not do to arrange" the book.
eg Problem B It was not written whether the numbers are Integer?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче D. там финальных ответа два: либо раскраска начинается с черной, либо с белой. И для каждых двух этих ответов смотрим разницу с нашим стрингом: c каким ответом разница меньше то и будет ответ...Это решение правильно?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да. У меня такое решение только что прошло.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если считать разницей просто количество отличий, то нет.
    Два теста:
    4
    1100

    4
    0011
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Оба теста можно привести к 0101 или 1010. В обоих случаях количество различающихся позиций - 2 и ответ очевидно тоже 2.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Почему нет? Разница в обоих случаях будет 2. Правильный ответ: выбрать пару 1-2 и получить 0100, выбрать 3-4 и получить 0101
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Да, это правильно.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как доказать решение задачи C?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    i=1 очевидно всегда будет делителем расстановки, а все остальные можно сделать не делителем, если на j-ое место поставить j+1-ый том, т.к. GCD(j, j + 1) = 1. Первый том поставить на оставшуюся последнюю позицию.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Какое именно решение? я выводил 2, 3, ..., n, 1. Числа k и k + 1 всегда взаимно просты, ну и 1, разумеется, взаимно просто с n.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если n четное то ответ на i->i+1, i+1->i
    Если n нечетное то ответ 1->1 2->3 3->2 а дальше как в случае с четным
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Выводил n, 1, 2, 3... Решение и доказательство, по сути, аналогично описанному выше в данной ветке.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что за тест 20 в задаче B?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I didn't get the meaning of Problem C.What problem does it want us to solve?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    it just asked to minimize   number of toms that is relatively prime to its position
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за задачи!

Эх, жаль не рейтинговый для меня тур, да и вместо попыток взлома я пошел ужинать...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В этом то и плохая сторона участие вне конкурса, хотя когда дают пять задач на два часа времени для взлома не остается...

    Кстати а на рейтинге видно что неофициально участвовал ?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В первоначальном тексте задачи  B  была опечатка, которую потом исправили (результат сложения при основании  9 ). Но сообщение о поправке, по крайней мере мне, не пришло.
В вопросах его тоже не было. Обидно, потому что задачи как открыла после старта, так больше длительное время не обновляла.
 С такой проблемой столкнулась только я?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По сути дела я не смотрел на детали. Я задачу понял примерно. Решил не писать сумму по основанию вручную, посчитал на Java (эх ленивый же я).

    Но иногда можно и пролететь(со мной такое часто на Topcoder)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, действительно была такая опечатка (для основания 9), но мы ее сразу исправили, как только узнали о ней. Приносим свои извинения.
    А вообще если сталкиваетесь с подобной опечаткой, и она мешает Вам решить задачу, лучше сразу задавайте вопрос жюри.

14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Aha, a good contest with nice problems!
Problem C is not so easy to understand, but really interesting.The answer looks very easy,but hard to get.
Problem D confused me.I can't pass it till now. But also a good problem.
Problem E is really nice, I got a O(N4) dp after long thinking.


  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I wonder whether problem E can be solved using BFS....

    if we have some string s1 we try to get shorter s2 by reverse operation described in problem. To avoid repetition we use memoization.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    can  u share me ur code for prob E plz... i don hav any idea abt this
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Hey can you explain how u approached the problem E. I used kinda brute-force but got TLE on test case 8.
    I dont need the code; just the approach would be quite helpful.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      For example:
      ababa
      aba
      2
      c->ba
      c->cc
      The answer is :
      ac => 
      [a][baba]
      [a][ba]
      So, we can use dp[i][j]: the shortest common ancestor of a[1]...a[i] and b[1]...b[j].
      dp["a"]["a"] = 1
      dp["ababa"]["aba"] = dp["a"]["a"] + 1
      If we know, "baba" & "ba" can generate by the same letter "c" , we can obtain the answer.

      To get that, we also use a dp.
      bool dp2[string][char]: can a string generate by the letter char.
      But it cost O(N5) in time.
      So we can compress it into an int.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какой был тест 19 в задаче B?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Тест был таким:

    Ввод
    1 466
    Ответ
    3

    З.Ы. Я думаю многие, как и я, не знали, но тесты можно увидеть под своим исходным кодом, кликнув на номер посылки в разделе "Мои посылки"

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
I used greedy algorithm for D and got AC (?!). How did you solve it?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I used a DP with states (position, color of position-1)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    We have only two possible anwers in the end:. one which starts with black and another starts with white.
    (sort of chess coloring)

    So we calculate the difference between our target string and our given string. (we choose minimal)
    it's easy to see there always exist way of reduction of our string to the target function
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
there seems no case for the answer -1
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is answer for C unique?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What a pity!I have thought of the easy solution,but I can't figure out when the answer will be -1.So I want to judge it by DFS,but if failed
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Разбор задач будет?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is  test21 for Problem B, i am getting WA?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
what is test case 8 for problem D ??
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
i didnt get it , where to see the test case?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Go to "My submissions" and click the id of your submission (in the "#" column, the first one). You can do it with others solved submissions too.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    For problem B
    -------------------My failed test case----
    Test: #21, time: 10 ms., memory: 1316 KB, exit code: 0, checker exit code: 0, verdict: WRONG_ANSWER
    Input
    1 999
    Output
    3
    Answer
    4
    Checker Log
    wrong answer 1st numbers differ - expected: '4', found: '3'

    ------------------------------
    When i run the program on my system i get Anser as 4 not 3
    here is my program (i have removed the header files)

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anyone give a glimpse of the solution for problem E?
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Видимо, намного позднее)
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Why the ratings aren't updated???
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
как скоро обновят рейтинг? И интересно почему задержка в чём там проблемы?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
почему в задаче D в тесте 10 1000101001 нужно выдавать 3 а ни 2? (8й тест в системе)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Корректная последовательность преобразований выглядит так

    1000101001
    1010101001
    1010101011
    1010101010

    Сделано 3 действия. Сделать за 2 у вас не получится.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Can anyone tell me why this output is 3:
10
1000101001
output
2
Answer
3

1000101001->1010101001->1010101010 =>2?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It's because Petya can recolor two cells with one color only, you had recolored 01 -> 10 at a last step
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      well i don't use spesial algorithm for solve this problem. Just using simple logic but I'm hard to understand it. . . and me got accepted. . . what a miracle. . .
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        There is actually a simple logic to do this question,

        Finally the strip has to be like 1010.... or 0101.....

        So basically you compare the input with both the two forms of the string and see the difference. Lets say the nth block doesnt match, then that means (n-1)th block has to be the same color as nth block and thus in one step you can paint it the right color.

        Eg,

        Input: 1101011
        compare this with 1010101... we know the second position doesnt match, that means we simply take the 1st and the 2nd blocks and paint them the right way.

        If two blocks don't match in a row that means they are of the opposite colors and you can't take them together and paint it... thus needing two steps... and similarly for 3 unmatching blocks you will take 3 steps etc. So basically you count the differences from both the types of final outputs and whichever one is smaller, you output that.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          aaaaa. . . that's what I mean. . . Actualy i'm not understand about BFS or another algorithm. . . Can you help me . . . I solve all problem with simple algorithm without know what algorithm i use to. . .
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    In the second step,
    10101010[01] -> 10101010[10]
    This cannot be done as [01] are not of the same color.
    You would have to do it in this order,
    1010101001 -> 1010101011 -> 1010101010
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Напишите пожалуйста 10 тест к задаче D.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    вообще-то тест на котором у вас ошибка вы можете увидеть клинкнув на ID своей посылки и пролистав немного вниз
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Thanks all.Does anyone use BFS for prob E.My BFS for E : from S1 we create all the shortest ancestor of S1 by BFS ,the same with S2, then we compare all the ancestor of S1 and S2(using binary search) to find the result.