Зеркало ACM-ICPC NEERC Southern Subregional Programming Contest 2011 (Саратовского ЧФ)

13 лет назад, # ^ |

Переведи, будет русский текст.

→ Ответить

CherryTree

13 лет назад, # |

Расскажите, пожалуйста, как решать H?

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

Утверждение 1. Ответ - все делители некоторого числа. Более менее должно быть очевидно.

Утверждение 2. Ответ - делители числа gcd(|a_i - a_j|) по всем i,j где a_i коеффициент на который умножается i-ая буква. Это так, потому что существуют два числа с такой разностью.

Утверждение 3. Ответ все делители gcd(gcd(|a_i - a_j|), b) - где b - произвольное значение этой строки.

Это получает какой-то большой тл. Лечится тем, что заменим поиск делителей на разложение на простые и очевидный переборчик. Почему это быстрее не знаю.

→ Ответить

Xazker

13 лет назад, # ^ |

Сделаем 10 000 итераций, генерируя случайное число из букв. Находим их НОД и раскладываем на множители способом выше.

→ Ответить

KADR

13 лет назад, # ^ |

У меня прошло вообще тупое решение: берем случайное число из букв, так чтобы первые 2 цифры были 11 или 10, затем раскладываем на множители, перебирая простые до корня, а потом просто проверяем, подходит ли каждый делитель. Чтобы узнать, подходит ли делитель, можно взять 500 рандомных чисел, которые подходят под шаблон и сделать проверку только для них.

Единственная оптимизация: если какое-то число подошло, то его делители я уже не проверяю, т.к. они точно подходят.

→ Ответить

Xazker

13 лет назад, # ^ |

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

→ Ответить

13 лет назад, # ^ |

Ну, в принципе, понятно, почему быстрее - во-первых, всегда быстрее, когда у ответа более двух делителей, а здесь у ответа обычно много мелких делителей. Мы получили ТЛ 89 и немного времени не хватило сделать разложение на простые и переборчик.

→ Ответить

13 лет назад, # ^ |

← Rev. 5 →

-21

Легко свести эту задачу к нахождению наибольшего общего делителя, или gcd

Первое решение - взять несколько рандомных чисел, подходящих под шаблон, и взять их gcd. Это работает, несколько команд так и сдали

Второе решение - если у нас в шаблоне меньше чем 10 различных букв, покажем на примере что нужно сделать:

Пусть допустим aaababaa

Если взять сначала a=1, b=3; а затем a=2, b=3, то получим разность получившихся двух чисел 11101011. То же самое проделаем для буквы b, получим 00010100, возьмем gcd у этих двух чисел и получим ответ.

Если же у нас есть все 10 букв в слове, то утверждается, что существует только три варианта. А именно -слово длиной 10 букв(abcdefghij-для него ответ 9), и что-то наподобие слова aaaabcdefghij-для него ответ 3(то есть четыре буквы одного типа, всех остальных по одному). Покажем, что для остальных слов из 10 букв ответ 1. Возьмем произвольное слово, не подходящее по первым двум критериям. У этого слова есть такая замена, которая не делится на три. И у него так же существуют такие две позиции, которые являются соседними, и буквы в этих позициях встречаются в слове только один раз(по принципу Дирихле). Возьмем и поставим в эти позиции 1 и 2 поочередно, а остальные позиции менять не будем. Тогда разность между двумя числами будет 9*10^k. Но не на 3, ни на 9 это число не делится, ну и понятно, почему шаблон не делится на 2 и на 5, поэтому доказано.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

-19

Короче, задолбался исправлять отдельные слова, что непонятно-спрашивайте.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Если я не ошибаюсь (не сдавал), то следующее верно:
Рассмотрим все числа, которые получаются заменой одной буквы на 1, а остальных на 0.
Если различных букв 10, то вычтем из всех минимальное из них, а само минимальное помножим на 45
GCD == GCD полученного набора [Он из не более, чем 10 чисел. Вся вычислительная сложность в разложении на множители]

→ Ответить

Al.Cash

13 лет назад, # ^ |

Вот решение, которое очевидно находит делитель нужного числа. Что он максимальный доказать не смог, но тесты прошло.

Для каждой буквы алфавита находим коэффициент, на который она домножится в результате (сумма степеней десятки по всем ее вхождениям в строку). Ответ - gcd этих коэфициентов.

+ несколько особых случаев:

1) 10 разных букв -> 9

2) 10 разных букв + еще 3 вхождения одной из них -> 3

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

-8

Доказательство именно этого факта чуть выше. Или же вот здесь в комментариях

→ Ответить

Ivan.Kuskov

13 лет назад, # ^ |

Подскажите, какие могут быть ключевые различия в компиляторах GCC/VSC++? Сдал эту задачу с черти-какого раза, все баг искал(ВА2). Поменял компилятор - ТЛ89, убрал костыли "от багов" - АС. Использовал только стринги и вектора из STL, выводил через %lld.

→ Ответить

13 лет назад, # ^ |

%lld это может быть печально

→ Ответить

Vaness

13 лет назад, # ^ |

Студия вроде адекватно выводит и с %lld.

→ Ответить

13 лет назад, # ^ |

Какая?

→ Ответить

Vaness

13 лет назад, # ^ |

← Rev. 2 →

Microsoft Visual C++ 2010 Express. Хотя да, может 2005я плохо относится к lld.

→ Ответить

Ivan.Kuskov

13 лет назад, # ^ |

← Rev. 2 →

Путем проб и ошибок нашел. Если одновременно пользоваться cin и printf/scanf, то студия нормально хавает(VS 8 c++), а gcc - нет. Что конкретно там творится - не знаю, но после того как переписал полностью на потоковый ввод/вывод прошло под gcc. Так что, либо синхронизируйте потоки, либо вообще не смешивайте.

→ Ответить

Malinovsky239

13 лет назад, # |

Как решать G?
Я писал bfs по состояниям (состояние = клетка + битмаска, задающая, съедена ли та или иная чёрная фигура).

TL 91 :(

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

Именно так и сдавалась спокойно. Может быть вы долго проверяли можно ли пойти куда-то?

→ Ответить

Malinovsky239

13 лет назад, # ^ |

Пока писал сообщение содержания "Я делал так, а как же ускорить?" понял, что в каждом положении проверяю не 8 ближайших клеток, а все клетки доски на то, можно ли в них пойти. Печально (

→ Ответить

PavelKunyavskiy

13 лет назад, # |

← Rev. 2 →

yeputons, демон, как ты умудрился сдать в 5:00?

→ Ответить

yeputons

13 лет назад, # ^ |

+15

Колдуем потихоньку :)
Думаю, виновато округление времени

→ Ответить

13 лет назад, # ^ |

Вот если бы сдал на 5:01 - это было бы колдуем :) Где-то для пятичасового контеста были прецеденты.
^{_{(кажется, проверялка ставила время фактической проверки вместо времени посылки).}}

→ Ответить

ZorN	13 лет назад, # \| 0 Подскажите, пожалуйста, есть ли добивание в этом контесте? → Ответить

13 лет назад, # ^ |

-7

заказываешь виртуально

→ Ответить

L.I.S.

13 лет назад, # |

← Rev. 2 →

Какая у вас сложность? У меня со сложностью (2 ^ 14) * (14) * ((15) * (15) + 14) операций проходит.

(Не в ту ветку, ответ на вопрос Malinovsky239)

→ Ответить

13 лет назад, # |

Can someone explain how to approach C ?

→ Ответить

13 лет назад, # ^ |

+14

ans = 0;
for seg1 in vertical segments
for seg2 in vertical segments (index of seg2 > index of seg1)
{
curCnt = 0;
for seg3 in horizontal segments
if seg3 intersects seg1 && seg3 intersects seg2
curCnt++;
ans += curCnt*(curCnt-1)/2;
}
print ans

→ Ответить

bytybai

13 лет назад, # |

интересно, как же решается задача А?))

→ Ответить

Erop

13 лет назад, # ^ |

Переберем все варианты хода для первого работодателя и проверим может ли он выиграть из этой вершины.

Второй выигрывает, если он может нанять двух крутых программистов раньше первого. Обозначим кратчайшее расстояние между этими программистами за u, а расстояние от первого работодателя до них как x и y соответственно. Второй может их нанять в двух случаях:

Если u + 1 < x + y. Т.к. в этом случае второй игрок может выбрать вершину на кратчайшем пути между этими программистами и в зависимости от хода первого игрока, приближаться к соответствующему программисту. В силу неравенства второй игрок наймет обоих программистов раньше первого.
Если не существует 2 вершин v1 и v2, таких что они обе лежат на каком то кратчайшем пути между программистами, расстояние до вершины выбранной первым игроком до v1 и v2 равно 1 и расстояния от v1 и v2 до программистов совпадают. Если они существуют, то несложно построить выигрышную стратегию для первого игрока.

Предподсчитаем кратчайшие расстояния от всех трех программистов, тогда хода первого игрока мы может быстро определить x, y, u.

→ Ответить

Erop	13 лет назад, # \| 0 Не подскажете как решается E? → Ответить

Ripatti

13 лет назад, # ^ |

Во первых, найдем центр дерева. Центр - это середина какого либо из диаметров. Если он на ребре - запомним вариант ответа, когда мы стягиваем это ребро, а потом разбивьем это ребро на 2 куска с очень большой стоимостью.

Итак, центр дерева в вершине. Выкидываем из дерева все ребра, что не входят в диаметр и подвешиваем на центр. Полученное дерево мы назвали "веник":) ибо все пути от центра до листьев одинаковые. Дальше вполне себе очевидная динамика на венике - наименьшее количество денег, которое надо потратить чтобы на любом пути от вершины до листьев было хотя бы одно удаляемое ребро. Пусть мы все посчитали, ответом будет сумма дп по детям корня минус максимум по детям корня. Дальше остается только построить ответ (не забыв при этом про случай когда центр был на ребре).

→ Ответить

13 лет назад, # ^ |

← Rev. 3 →

Решение с разбора.

Решается динамикой по поддеревьям.

Найдем центры дерева. Их либо 1, либо 2 штуки.

Пусть центр один. Пусть из него идут несколько ребер, и в направлении K из них длиннейший путь из центра до некоторого листа максимален. Тогда для уменьшения диаметра нужно уменьшить длиннейший путь в K-1 направлениях. Подвесим дерево за центр, и запустим динамику, которая считает стоимость уменьшения максимального пути до листа в поддереве вершины. Пересчитывается думаю понятно как.

Если центра два, появляется еще немножко колдовства, например нужно учесть, что диаметр можно уменьшить, выпилив ребро между центрами.

UPD: охщи, слоупочина, ну пусть два разбора будет.

→ Ответить

stostap

13 лет назад, # ^ |

А где есть разбор?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Нигде наверно. Михаил Мирзаянов вживую проводил.

→ Ответить

R_R_

13 лет назад, # |

Can anyone explain the tricks in problem H?

I tried the following approach: For each character, constructs a number with digits 0 & 1. The i-th digit is 1 if the i-th character of input string = current character

e.g. aabbaa --> number 110011 and 1100

Result = divisors of GCD(all generated number, and one possible number created by mapping the input string to a valid number)

I found a special case when all 10 digits appear and input string's length = 10. In this case, output should be 1 3 9

Did I miss any cases, or is my algorithm wrong?

Thank you for reading this :)

→ Ответить

Ripatti

13 лет назад, # ^ |

for testcase aaaabcdefghij answer is 1 3
in the all rest you are right

→ Ответить

R_R_	13 лет назад, # ^ \| +1 Thanks a lot :) I was doing that problem for hours and couldn't think of that case :( → Ответить

13 лет назад, # ^ |

← Rev. 3 →

If the number of different letter =10, there are only three cases. First is abcdefghij. gcd is 9.

Second case is aaaabcdefghij, gcd is 3, and other similar variants of this string.

In all other cases answer is 1. Let prove it. There is 2 neighboring position, where the letters in this position occur in this world only once (Dirichle principle for string no more than 14 symbols). Let put to this position 1 and 2 alternately and other position let assign random numbers. Then the different between this two numbers is 9*10^k. And it is clear that the string not divisible by 2, 5, 3.

→ Ответить

Kornacker

13 лет назад, # ^ |

← Rev. 4 →

How can you know that brute-force is too slow for this problem?

I only see 10! different possibilities, and at each possibilitie you just calculate the gcd with the previous gcd. Is the gcd operation (euclidian's way) to slow for this strategy?

→ Ответить

13 лет назад, # ^ |

brute is really slow, don't forget that there is 100 test cases in this problem.

→ Ответить

R_R_	13 лет назад, # ^ \| 0 I also got accepted using brute force algorithm :) Just break after finding around 10^5 numbers. The calculated GCD should be good enough → Ответить

havaliza

13 лет назад, # ^ |

← Rev. 2 →

+10

I got AC by just checking 10 random numbers! 10^5 is so much!

→ Ответить

13 лет назад, # |

Thanks for explaining, I was thinking of O(n^4) .
And how to approach the Berland Chess problem, constraints says solution will be exponential, but looks too complex for me, please elaborate.

→ Ответить

R_R_	13 лет назад, # ^ \| 0 I used dynamic programming. f(i,j,S) = minimum move if the king is in cell (i,j) and need to capture all opponent's pieces in set S. The number of states is quite big. I moved to only opponent's pieces' location to minimize the number of state. → Ответить

13 лет назад, # ^ |

Can you tell what exactly will S contain? And if possible give link to your solution.

→ Ответить

R_R_	13 лет назад, # ^ \| +1 S is a bitmask, i-th bit = 1 if we need to capture the i-th opponent's piece, and i-th bit = 0 if we already captured the i-th opponent's piece I don't have my code now. I have a bad habbit: deleting my code after got accepted =) → Ответить

13 лет назад, # ^ |

Okay, now to move from one state to another, we need to check whether the *king* can move to that state or not, how did you check that? , I will need O(15*15) for that, is there any simpler way to check whether next state is reachble or not ?

[nice habbit btw. :) ]

→ Ответить

R_R_	13 лет назад, # ^ \| 0 I pre-calculated that, but it was to simplify my dp function. I think it wasn't necessary in terms of complexity since the number of states is quite small. I even used O(N*N) to calculate the distance to every cell at each state (i,j,S). → Ответить

13 лет назад, # ^ |

dp will have (2**15)*15*15 states right?
I guess you are telling it will be lesser, but how?

→ Ответить

R_R_	13 лет назад, # ^ \| +1 Number of states = 2^15 * 15 since I only moved to opponent's pieces' location. It was small enough :) → Ответить

Eugene

13 лет назад, # |

Кто-нибудь пофиксите баг с Mono на sgu. См. форум.

→ Ответить

bytybai

13 лет назад, # |

Подскажите пожалуйста, я решаю задачу D, мой код http://pastebin.com/WMZX1gxJ поучаю WA on 20. решала так: искала количество кубиков, которые умещают в своей сумме число n, потом в зависимости от того, четное их число или нет, смотрела можно ли набрать именно n.не могу понять в чем ошибка(

→ Ответить

Scalar

13 лет назад, # ^ |

На каждой боковушке у нас будет по 14 точек. Поэтому общая сумма для k кубиков будет 14*k+a+b, где a,b - числа на крайних кубиках. Поскольку 2<=a+b<=12, мы можем набрать сумму n только если n != (0,1,-1) mod 14, и для набора понадобится n/14 кубиков. Ну и разумеется, нужно рассмотреть крайние случаи: если n<30, то мы можем набрать требуемую сумму только если n=21.

→ Ответить

13 лет назад, # ^ |

Вот решение без частных случаев:

Пусть ответ равен K. Сумма чисел на всех кубиках (с учетом внутренних стен) - 21*K. Теперь на K-2 кубиках (если они есть) вычитаем сумму на противоположных гранях - 7*(K-2). И еще осталось вычесть сумму на внутренних гранях первого и последнего кубиков, которая может лежать в диапазоне 2 ... 12. Итого ответ к задаче без всяких частных случаев можно выписать следующей формулой:

min K s.t.

21*K - (K>2 ? 7*(K-2) : 0) - (K>1 ? 12 : 0) <= N <= 21*K - (K>2 ? 7*(K-2) : 0) - (K>1 ? 2 : 0)

→ Ответить

Scalar

13 лет назад, # ^ |

← Rev. 2 →

C частными случаями получается короче :)

(n<30 && n!=21 || (n%14<2 || n%14==13) ? -1 : n/14);

PS: Ого, копирование из студии сохраняет форматирование :)

→ Ответить

13 лет назад, # ^ |

Согласен. Но в этом решении думать надо =)

→ Ответить

Egor	13 лет назад, # \| +6 А есть какие-то шансы в будущем поменять Solution на Main? Или все контесты с sgu.ru постепенно переедут на Codeforces? → Ответить

jaric

13 лет назад, # |

Помогите пожалуйста решить задачу B.

Пробовал решить перебором без дополнительной сортировки (ТЛ 28) и сортируя банки по деньгам (ТЛ 73) с эвристиками. И подскажите временную сложность задачи?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Идея - динамическое программирование. Сложность - O(N). Для каждого банка B ищете самый правый банк A левее банка B, который еще можно ограбить. Теперь, если вы грабите банк B, то можете вместе с ним грабить любой банк левее A и включая A. Додумайте сами.

Если еще нужны подсказки - пишите.

→ Ответить

13 лет назад, # ^ |

Частичные максимумы == динамическое программирование? I LOL'D.

→ Ответить

13 лет назад, # ^ |

Никакого лола не вижу. Можно считать, что начинаете решать задачу с одной точки, потом добавляете по одной точке и решаете задачу для расширенного множества. Вот термин "частичные максимумы" вижу впервые.

→ Ответить

13 лет назад, # ^ |

Кажется, логично, что если частичные суммы - частичные суммы, то частичные максимумы - то же самое, только для максимума ;)

→ Ответить

jaric

13 лет назад, # ^ |

Спасибо, работает! =)

→ Ответить

babak

13 лет назад, # |

what's the idea for multiswap problem?

→ Ответить

Scalar

13 лет назад, # ^ |

For any array number of steps does not exceed 2.

→ Ответить

13 лет назад, # ^ |

← Rev. 4 →

Magic.

It's proofable that any array can be sorted in no more than 2 multiswap operations.
If array is sorted, answer is 0.

Now, let's suppose that all numbers in array are distinct. So, we can consider this array as some permutation. Have a look at graph representation of this permutation.

Answer is 1 if this graph contains cycles only with length no more than 2 (we can swap elements of this cycles and sort array this way).

If there is at least one cycle of length more than 2, answer is 2. You can notice that swapping two elements of some cycle, divides this cycle into two cycles. This way by one multiswap operation you can divide any cycle into cycles of length no more than 2. goto previous paragraph.

If not all numbers in array are distinct, we can enumerate all identical numbers as consecutive distinct numbers, and apply algorithm above, so we can still sort array in no more than 2 operations. But not any enumeration will form permutation which requires minimal possible amount of operations for sorting. So, I don't know, what exactly should we do if not all numbers are distinct.

→ Ответить

13 лет назад, # ^ |

← Rev. 3 →

Exactly - try to use greedy matching for sorting in one step, if this fails and two steps are required, you can assume that this is a permutation and use the solution above.

→ Ответить

BoBaH6eToH

13 лет назад, # |

Подскажите, пожалуйста, алгоритм на задачу С.
Надо ли было в явном виде искать точки пересечения?

→ Ответить

13 лет назад, # ^ |

Нет, достаточно проверить пересечение. Читаем.

→ Ответить

f.nasim

13 лет назад, # |

In problem B I am getting WA on case 8. In i-th index of an array m[] I am storing the maximum amount found in bank i and all banks after i. Then for each bank I am doing a binary search to find the next suitable bank after current and taking the maximum. Code is here. Please help.

→ Ответить