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

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

Обсуждение контеста

Задача А. Треугольники

Тематика: Теорема Пифагора, перебор

В данной задаче нужно было написать функцию, проверяющую, что три точки образуют прямоугольный треугольник. Сделать это можно было множеством способов, один из самых простых - теорема Пифагора

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

Чтобы проверить треугольник на почти прямоугольность, нужно было поочередно подвигать каждую точку во все 4 направления и проверить получившийся треугольник в нашей функции. Для быстрого перебора смещения, можно использовать два массива dx={-1,0,1,0} и dy={0,1,0,-1}. Тогда следующий код давал бы нам координаты смещенной точки:

for (int i = 0; i < 4; i ++)
{
int x = dx[i] + px;
int y = dy[i] + py;

}

Задача B. Платформы

Тематика: Симуляция

Рисунок к задаче:

В данной задачи нужно было определить координату падения кузнечика. Для этого просто будем хранить положение кузнечика в данный момент.

Для того, чтобы программа не работала слишком долго, нужно "продвигать кузнечика" по платформе за О(1) (не в цикле). Кузнечик сделает j = (righti-x)/d прыжков по i-ой, платформе, где x - координата кузнечика (он уже стоит на платформе) а righti - правая координата платформы. Поэтому кузнечка сразу можно передвинуть на j*d право.

Задача C. Полоска

Тематика: Перебор

Для решения данной задачи нужно было хранить две суммы S1 - сумма чисел слева от разреза (изначально равна 0) и S2 - сумма чисел справа от разреза (изначально равна сумме всех чисел на полоске). В цикле двигаем место разреза слева направо, изменяя значения сумм, и, при необходимости, увеличиваем ответ

Задача D. Продавец Вася

Тематика: Жадный алгоритм, длинная арифметика

В задаче D потребуется длинная арифметика (сложение), так как число 22000 не вместится в int64.

Нам дано условие того, что продавец для каждого размера флешки встретится не более одного раза. Так как 2> 2x-1 + 2x-2 + ... 20, то прибыль от флешки с самым большим объемом будет больше чем если бы мы продали все остальные флешки. Поэтому в первую очередь нужно попытаться продать самую большую флешку, потом флешку поменьше и т.д. Таким образом, нужно пытаться продать флешки по убыванию их стоимости

Задача E. Флаг 2

Тематика: Динамическое программирование

В задаче про флаг необходимо воспользоваться методом динамического программирования. Мы будем считать функцию DP(level, A, B) (где A и B - номера цветов, от 0 до 25), которая возвращает минимальное число перекрасок, нужное чтобы перекрасить первые level полосок, причем последняя полоска будет иметь вид ABABAB...

Для пересчета данной функции сначала посчитаем, сколько перекрасок нужно, чтобы привести полоску с номером level к виду ABABAB... (пусть это будет число D). Заметим, что полоску можно покрасить таким образом, если первый цвет предыдущей полоски не был "A", а второй цвет не был "B" (условие того, что смежные клетки не должны быть одного цвета) или же это должна быть первая полоска. Поэтому DP(level, A, B) = min(DP(level-1, i, j)) + D , i = 0..25, j = 0..25, i != j, i != B, j != A.

Оценим время работы программы: O(N*26*26*(M+26*26)), эта константа не превышает 4*108


Спасибо за внимание! Решения не претендуют на оптимальность

Разбор задач Codeforces Beta Round 18 (Див. 2)
  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

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

Задача D. Жадность еще более жадная :) Из возможных вариантов продажи флешки нужно выбирать самый поздний, потому как все win'ы после нее и все win'ы от текущего до ближайшего снизу sell'a станут недействительными.

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

Елки-палки! Я пропустил в задаче D строчку насчет того, что продавец для каждого размера флешки встретится не более одного раза.

Сидел, пытался придумать ДП, которое бы проходило по памяти и времени - в итоге ничего не придумал.


Да и еще вопрос. Какое время работы O выполняется за 1 секунду на данном сервере? 

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Можно было решить D и пропустив строчку ;) одна из динамик такая : подсчитаем для каждого win первый sell пускай это будет go(p) (p-день когда выйграл) встречающийся после него(линейный проход по массиву с конца) теперь будем считать такую штуку F(p) - сколько мы можем максимум заработать прожив [0..p] дней база F(0)=0 переходы F(i+1)=max(F(i+1),F(i)) если день когда мы выйграли флешку на 2^val F(go(i))=max(F(go(i)),F(i)+2^val)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Елки-палки! Я пропустил в задаче D строчку насчет того, что продавец для каждого размера флешки встретится не более одного раза.

Сидел, пытался придумать ДП, которое бы проходило по памяти и времени - в итоге ничего не придумал.


Да и еще вопрос. Какое время работы O выполняется за 1 секунду на данном сервере? 

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

    Почему спросил про время.

    Просто у меня идея по задаче Е была точно такая же. Только я побоялся ее писать, т.к. подумал что она не пройдет по времени. За N*M*26 ничего не придумал.

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня она сначала не прошла по времени, но потом я сменил динамическую память на статическую и все получилось
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Написал DP, только хранил н евсю матрицу а только текущий столбец и предыдущий, что сэкономило память. DP нерекурсивное. 0,6 сек. 44 мб памяти.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Там одного массива хватит на 5000 элементов для динамики.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да уж, общая бяда)))
    А я уж думал-там какую-то зверскую динамику нужно делать...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In problem B you can also make the first m steps, and if after them the grasshopper didn't fall, it means that he'll fall only after all n platforms
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я бы сказал, что в задаче E константа не превышает скорее 4*108.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Имеется в виду константа стоящая под знаком О()

    Откуда взята 4*108? Никогда не используйте данное число (2*108 операций за 1 секунду), так как тут имеются в виду простейшие операции +-, еще не учитывается кеширование и работа с памятью, а также мощность сервера. 

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      500*26*26*(500+26*26) = 397 488 000
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Совсем сплоховал я - это все влияние сессии и бессонных ночей :(
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Нет, это как раз я сплоховал, потому что посчитал правильно ;) И не поверил, что такое может зайти.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Оно кстати заходит из-за того, что на серваке все хорошо в кеш помещается, я думаю
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Задача E. что хитрого в 7-ом тесте ? или я дурак или лыжи не едут,

кто может найти баг?

http://www.everfall.com/paste/id.php?iw0dwgcnfx7r

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Solution of problem E is not fast enough to pass it .I've tried to solve it by this alg. but still got TLE.
Anyone has a faster alg ?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It was mentioned that it passes in C++, but not Java.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you use Java for this problem, "dumb" solution (with constraint 26^4 for DP step) will get TLE. I wrote more complicated solution, where we count minimal value of recolorings in previous line, with which we can go to specified coloring of current line). This way we can get smaller constraint, cause we can sort values, and check only two of them.

    If you want, you can check my solution (submission 70276), where I've implemented this algorithm.

    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Actually, dumb solution passes with pretty easy optimisation for java - for each step we will count number of recolorings needed for given color to be on odd position and same for even. This leads O(nm * 26^2 + n * 26^4) "dumb" solution to be O(nm * 26 + n * 26^4) which passes. See my solution for implimentation
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      why so complex?
      I solved it easily . I save position had minimum value in previous step , it's POS1 , POS2 , DP[level,POS1,POS2] is minimum . In the next step , DP(level, A, B) = DP(level-1, POS1, POS2) + D if (POS1<>A) and (POS2 <> B)
      Else DP(level, A, B) = min(DP(level-1, i, j)) + D , i = 0..25, j = 0..25,
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I determine all possible checkerings of the the the previous row, and then sort them by non-decreasing cost. Then, for every checkering in the next row, just find the one with lowest cost that is compatible from the row above. This ends up being about O(n^2 log n) where n is ~650 = 26*25. This is less than 4,000,000.

    After doing a few rounds of this competition though, I'm tired of solutions working in C and not Java :( Slower languages should be given more time (even like, 25% more, though it should probably be closer to 50%), or the time limit should just be larger. The ACM-ICPC does this.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Could you help me with WA on test 25 problem D?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
think you!
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    That reminds me of:
    -SOS! We are sinking!
    -What are you thinking about?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хм, интересно, задача А простая и логика была правильная, а 31 тест WA... а в D не подумал насчет длинной арифметики:)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    2^2000 что тут еще не понятного про длинную арифметику???
    Ну если 31 тест то это наверняка мелкий косяк; возможно, этот тест на проверку почти квадратности и ты с одной стороной все правильно прибавляешь-отнимаешь, а с другой-нет 
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    там нужно проверять, что бы площадь была > 0
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Problem D: problem statement says that
"A customer came to Bob and asked to sell him a 2x MB memory stick. If Bob had such a stick, he sold it and got 2x berllars. "
I am unable to understand this.. suppose for example
5
win 10
win 5
sell 5
win 1
sell 10
in this bob should sell 2^5 to 1st customer because he have memory of that size..
or  he will not sell to that customer and keep 2^10 memory to sell 2nd customer.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    He sold 2^5 to the 1st customer, but now he wants to know what was the optimal way to sell memory sticks, and for that he should have kept 2^10.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      thank you for explaining ....
      i completely misunderstood during contest...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задача D.
Логику перепроверил несколько раз (учитываю занятость всего промежутка), но так и не понял в чем дело: WA Test 10.
Буду очень признателен за содержимое теста или за информацию о том, в чем там подвох.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Problem D : wrong ans  Help ..
Is there any way to know the input because i have got WA so many times...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Problem D : wrong ans  Help ..
someone please look at my code (71593 ) and tell me error i have tried lot to find out.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче А в условии говорится: "Гарантируется, что треугольник невырожденный, т. е. его площадь не равна нулю". Я и не проверял на вырожденность треугольник и получил WA на 31-ом тесте. Как добавил проверку, все прошло.
Посмотрел в таблице - у многих была ошибка на этом тесте.
Может, я не прав и этот тест не про вырожденность?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Дело в том, что когда мы сдвигаем какую-либо точку треугольника на один в какую-нибудь сторону треугольник может становиться вырожденным. Отсюда и WA#31.