1

Тема: TopCoder SRM 442

В субботу, в 20-00 по Москве состоится очередной SRM 442.

Будем надеяться, что в этот раз нашествия китайцев не будет и удастся нормально зарегистрироваться на матч smile

2

Re: TopCoder SRM 442

Разборчик что ли здесь провести.

250 Underprimes
Надо было по данному отрезку http://e-maxx.ru/gladtex/gladtex.php?tex=[A;B] посчитать количество чисел в нём, имеющих в своей факторизации такое количество простых сомножителей, что оно само является простым. Т.к. http://e-maxx.ru/gladtex/gladtex.php?tex=B%3C=100000, то надо было просто для каждого числа из отрезка факторизовать его за корень.

550 BedroomFloor
Была дана бесконечная схема замощения:
http://www.topcoder.com/contest/problem/BedroomFloor/floortiles.png
Т.е. в каждом квадратике 5x5 поочерёдно то горизонтальные, то вертикальные плитки.
Из этого бесконечного поля вырезался некоторый кусок http://e-maxx.ru/gladtex/gladtex.php?tex=((x1;y1),(x2;y2)), где координаты до миллиона. На рисунке пример такого куска выделен красным. Т.е. этот кусок содержит в себе куски плиток разных размеров, от 1 до 5. Требуется посчитать наименьшее количество плиток (1x5), из которых можно сложить этот кусок (можно разламывать каждую плитку на несколько кусочков).

Решение. Пусть мы каким-то образом посчитали количество плиток каждого размера c[ i], 1<=i<=5. Тогда нужно посчитать количество плиток размера 5, из которых можно набрать данные. Очевидно, решаем жадно: все c[5] сразу добавляются в ответ, потом все c[4] тоже добавляются, но при этом каждый раз остаётся по куску размера 1, поэтому c[1] тоже уменьшаем на c[4]. Аналогично, каждая c[3] добавляет +1 к ответу, но от каждой остаётся по куску длины 2, и если остались какие-то плитки c[2], то тратим эти куски на них, иначе тратим на плитки размера c[1]. Итак, в конце остаются плитки c[1] и c[2], опять же, сначала тратим все случаи вида 2+2+1 и 2+2+0, потом 2+1+1, и остаившиеся 1+1+1+1+1:

  long long ans = 0; 

  ans += s[5]; 
  s[5] = 0; 

  ans += s[4]; 
  s[1] -= min (s[1], s[4]); 
  s[4] = 0; 

  ans += s[3]; 
  long long add = min (s[3], s[2]); 
  s[3] -= add,  s[2] -= add; 
  add = min (s[3], (s[1] + 1) / 2); 
  s[3] -= add,  s[1] -= add*2; 
  s[3] = 0; 
  if (s[1] < 0)  s[1] = 0; 
   
  add = min (s[2] / 2, s[1]); 
  s[2] -= add*2,  s[1] -= add; 
  ans += add; 
   
  if (s[2] > 0 && s[1] == 0) 
    ans += (s[2] + 1) / 2; 
  else if (s[2] == 1 && s[1] > 0) { 
    ans++; 
    s[2] = 0; 
    s[1] -= min (s[1], 3ll); 
  } 
   
  ans += (s[1] + 4) / 5;

Т.е. эта часть решения сравнительно простая, а сложной, как ни странно, оказывается первая часть - подсчёт количества плиток каждого размера в нашем куске. Размеры куска очень большие, просто перебирать по одной плитке нельзя. Я делал так - перебирал столбец (т.е. вертикальную полосу ширины 5) и в ней наш кусок тоже будет представлять какую-то полосу, и для этой полосы за O(1) разбором разных случаев считал эти количества плиток.

950 NowhereLand
Задача фактически была следующей: был задан граф с <=50 вершинами, некоторые его вершины уже были покрашены, а некоторые запрещены к покраске. Нужно было дополнительно покрасить некоторые вершины так, чтобы минимизировать количество ребер, один конец которых покрашен - а другой нет.

Не знаю, какое затмение на меня нашло - это же в чистейшем виде задача о минимальном разрезе, решается с помощью максимального потока (т.к. в данной задаче требовалась только числовая величина мин. разреза, то надо было просто найти максимальный поток, его величина совпадает с стоимостью минимального разреза). Для этого в граф вводится исток и сток, исток соединяется с покрашенными вершинами рёбрами с бесконечной пропускной способностью, а все запрещенные вершины - со стоком.