I've just noticed that no div-1 round today :(.

Why I can't hack pedromnasc solution of A in CF #89 room #38. In his solution he takes max array size only 110. But in answer, the array size is 198. How it gives correct answer????
It must not print more than 110 char.But it does.. HOW????
Here is  pedromnasc's. code. http://mirror.codeforces.com/contest/118/submission/741727

My input string is "CCCCCCCCCCDDDDDDDDDDQQQQQQQQQQZZZZZZZZZZLLLLLLLLLLPPPPPPPPPPbbbbbbbbbbbbbbbbbbbbggggggggggttttttttt"
Which has 99 char.
And his solution is
".c.c.c.c.c.c.c.c.c.c.d.d.d.d.d.d.d.d.d.d.q.q.q.q.q.q.q.q.q.q.z.z.z.z.z.z.z.z.z.z.l.l.l.l.l.l.l.l.l.l.p.p.p.p.p.p.p.p.p.p.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.b.g.g.g.g.g.g.g.g.g.g.t.t.t.t.t.t.t.t.t"
Which is correct. :O How??
It's length is 198, which is grater than his "aux" array size. How it obtain the "EXTRA" char (110 to 198)th char in aux[110]?? :O

I also resubmit my code only for the array size.

My question is.......
Does array size matter in CF compiler ????????

Thanks andreyv ...It was unknown to me.

It gives me a good lesson also..   :)

Задача C какая-то жесть, потратил на нее 40 минут, а когда начал писать E, ее взломали, в итоге ни C, ни E...
Сейчас буду смотреть как это нормально писать надо

Выяснилось, что я перепутал в голове "больше" и "меньше"...

In today's problem C, I wrote my code quickly and believed it to be right, then I submit it with G++, and it returns an "Runtime Error"

Like this:

http://mirror.codeforces.com/contest/118/submission/742856

And after some minutes, I resubmitted exactly the same code, but in MS C++

http://mirror.codeforces.com/contest/118/submission/743301

And I  passed the pretest and finally got Accepted....

Why this strange thing happens?

UPD:  I tried my two problems in "Custum Test", using the test

45 32
293440596342887581257444442930778730382520372

and still RE in G++, and AC in C++, isn't it a bug in G++ 4.6?

I really like the problem set.  Alexander does a great work. Nice description and finally fine problem set with logically good concept.

Разбор задач. Codeforces beta round #89.

Задача A.

Первая задача на реализацию. Надо было пройтись циклом по строке и все согласные буквы скопировать в новую строку. После этого пробежаться по полученной строке и перед каждой буквой вывести ‘.’.

Задача B.

Вторая задача также чисто на реализацию. Ее можно было выполнить следующим образом. Если задано n, то надо было вывести 2 * n + 1 строк для узора. При этом для строки I (0 <= I <= N) – количество пробелов в начале строки будет равно 2 * N – i. Для строки с номером I от N + 1 до 2 * N количество пробелов равно (I - N) * 2.

Таким образом, узор формируется следующим образом: сначала выводим соответствующее количество пробелов для нужной строки, потом соответствующую последовательность цифр. Каждая строка в решении должна заканчивать переводом строки и не содержать лишних пробелов в конце.

Задача С.

Итак, в задаче требуется получить наиболее красивый номер и затратить как можно меньше денег для этого. Разобьем задачу на подзадачи и решим ее для каждой цифры в отдельности. Чтобы затратить наименьшее количество денег и сделать максимальное количество замен следует для каждой цифры С заменять в номере все цифры отличные от нее сначала по модулю 1, затем по модулю 2, затем по модулю 3 и т д по возрастанию модуля, в этом и только в этом случае набранная сумма будет наименьшей. Естественно, если произведено нужное количество замен K, то работу алгоритма стоит прекратить. Однако, чтобы получить лексикографически наименьшую строку K с цифрами С, то надо производить замены следующим образом. Пусть на данном шаге алгоритма мы хотим поменять все цифры, отличные от цифры С по модулю I, то есть в строке все цифры С + I и цифры С – I заменить на цифру С. В таком случае сначала стоит заменять все цифры С + I на С, и замены производить с начала строки. А после поменять все цифры С – I на C, и замены производить с конца строки. В этом случае Петя потратит наименьшее количество денег, и получит лексикографически наименьший номер.

После останется выбрать наилучший ответ из 10 строк. Таким образом, асимптотическая сложность алгоритма равна 10 * 10 * n.   

Задача D.  

Задача решается ленивой динамикой. Пусть z[n1][n2][2] – это количество способов расставить войска в легионе Цезаря. Параметры обозначают следующее, n1 – это пехотинцы, n2 – это всадники, третий параметр обозначает  какие войска ставит Цезарь в начало шеренги. Переходы следующие: если Цезарь хочет поставить n1 оставшихся пехотинцев в шеренгу, то из состоянии z[n1][n2][0] можно перейти в состояние z[n1 – i][n2][1], где I такое что (0 <= I <= min(n1, k1)). Если же Цезарь хочет поставить всадников, то из состояние динамики z[n1][n2][1] переходим в состояние z[n1][n2 – i][0], где 0 <= I <= min(k2, n2).   

Задача E.

Формально задачу можно поставить так. Нам задан неориентированный связный граф, надо ориентировать его дуги таким образом, чтобы получился сильно связный ориентированный граф. Известна следующая теорема (на теоретической базе которой написана задача), что такой граф допускает ориентацию к сильно связному орграфу тогда и только тогда, когда каждое ребро входит в какой либо цикл.

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