Всем привет!
Этот контест был подготовлен в срочном порядке Артемом Раховым и другими участниками сборов в Петрозаводске от Саратовского ГУ. Пришлось оторваться от дорешивания, не пойти на лекцию Виталия Гольдштейна (не сердись, Виталий), но зато раунд подготовлен и мы ждем вас — участников.
Как говорится, "happy hacking"
MikeMirzayanov и команда Codeforces
UPD. Контест закончен, всем спасибо за участие. Победил участник из Китая winmad. Лучший участник вне конкурса: anonymous. Последняя задача контеста поддалась только ему, браво!
Как всегда люди не учитывают, что кто-то живет в другом часовом поясе :о)
using namespace std;
int b[100000];
int main()
{
b[100001] = 1;
cout << b[100001];
}
Почему этот код не получает рантайм при запуске?
А время по уже проверенным видно где-нибудь?
1) талант: без него будешь всегда в середничках или аутсайдерах;
2) знания: чем меньше знаешь алгоритмов, формул, возможностей языка, тем меньше будешь решать задач; обратное вообще говоря неверно; см. также 1, 3 и 4;
3) опыт: знание подводных камней, способов решения стандартных и часто встречающихся проблем;
4) навык тестирования, отладки и внимательного кодирования;
5) увлечённость (?).
Этому учатся либо опытом, либо с хорошими преподователями, либо умными книжками.
Стратегии тут особо нет, известно же что порядок от простого к сложному.
Хотя я плохо геометрию решаю, поэтому бывает пропускаю.
Может помочь пытаться классифицировать задачи "геометрия", "теория чисел", "комбинаторика", "динамическое программирование" и т.д.
Но обычно классифицировать можно только когда начал представлять как решать.
Test: #16, time: 50 ms., memory: 2688 KB, exit code: 0, checker exit code: 2, verdict: WRONG_ANSWER
Input
509149
Output
1
Answer
509149 1
Checker Log
wrong output format Not sorted and uniqued
What's wrong with this answer? It is looks like all is ok (sorted and unique)
Спасибо создателям codeforces.
Классные соревы!!!
UPD: извиняюсь, подумал что задача B.
А попасть сюда можно нажав на x1234 вот тут.
I think u need 1 more revision...
I think u missed a "be" after "last trees" ...
and what is len?
So, for each tree you check which height of the first tree would keep it unchanged.
Choose for the first tree the height that satisfies more trees.
Why the first tree is so special...?
Problem B: try to declare arrays out of main function (global)
Hope it helped.
Hope it helped. :)
Just imagine columnar addition of the resulting numbers (from right to left).
You can use DP on state (carry, 1st number position, 2nd number position, 3d number position) with some modifications to avoid leading-zeros problems.
This DP has cycles, so I've used dijkstra.Dijkstra is used due to DP <=> Graph analogy, i.e. state (0, 3, 2, 3) may have an edge to state (1, 3, 2, 3) and state (1, 3, 2, 3) may have an edge to (0, 3, 2, 3), and so there are possible cycles in my DP. You can either use 'simultanious' calculation of both states here (with some problems in output, caused by non-trivial output on edges like (1,3,2,3) => (0,3,2,3) => (1, 2, 1, 3) ) or use dijkstra to overcome cycle problems.
(CO: lots of DP solutions are similar to shortest-path on DAG)
(0,1,2,1) => (1, -1, 1, 0) => (1, -1, -1, 0) => (0, -1, -1, -1)
It's better to use example 3+99=2 because all numbers should be greater than 0.
Yeah, my statement is correct only in middle of numbers and becomes wrong when one or both numbers are finished and we can get leading zeros for free. But in case of one finished number we still can set or clear carrying flag wasting only 1 digit instead of 2 or (if digits are 9 and 0) use both digits and postpone clearence of flag. So the only case left is when both numbers are finished and we can handle it separetly.
P.S. This problem turns out to be tricky one, so may be your solution with Dijkstra is really less error-prone.
1. Global number of digits has no matter. I've changed them to edge cost.
2. After that, leading zeros problem may be overcame with the next idea:
we need 2 special states - 'all the digits from number are used' and 'a number is finished'
The second means that you can only add '0' digit to the left (on zero cost!)
The first means that you can add any digit on one cost.
My solution just duplicates edges, but you can add an edge from the first state to the second with zero cost and no output on it.
And then, remove any leading zeros from the result (we get them on zero cost).
All this thread is marked as russian, so It is not visible for english users. Так что зря выпендривались =)
goh tu in emtehanu!
Ну, Е, вон, уже в комментариях разобрали, там динамика.
А D это чисто техника.
Дописываем в конец ко всем строкам входного файла разделить
Сортируем все строки
После этого идем по массиву, если строчка еще не взята - берем ее первой в пару, второй в пару берем первую подходящую по длине строку.
На выводе удаляем у второй в паре разделитель.
Проще всего создать 11 сетов: один общий, и 10 для строк конкретной длины (т.к. длина варьируется от 1 до 10).
При этом к строкам действительно можно приписать к конце разделитель, и это будет правильно, т.к. длина каждой строчки ответа должна быть одинакова.
Потом на каждом из n/2 шагов:
1) Удаляем первую строку из общего сета и выводим ее.
2) Удаляем ее из сета с строками нужной длины.
3) Вычисляем, строка какой длины нужна ей в пару.
4) Удаляем из соответствующего сета первую строку и выводим ее, но без разделителя в конце.
5) Удаляем ее из общего сета.
Собственно, это то же самое решение, что и у Анонимуса.
Нужная расстановка имеет вид:
1 2 3 .... 3 2 1, либо большая на константу.
Нам дана расстановка a1, a2, ..., an.
Найдем разницу:
(1-a1) (2-a2) ........ (1-an).
Теперь найдем, каких значений в этом массиве больше - тогда индексы, соответствующие этим значениям, и нужно оставить на своих местах (они соответствуют одной из правильных расстановок, и их наибольшее число). Вот и все.
Еще нужно заметить, что числа в ответе не могут быть неположительными, так что должны быть выполнены неравенства ai >= min(i, n-i+1), i=[1,n]. Поэтому, если это не выполняется на каком-то индексе, можно поставить флажок, что для этого индекса мы ничего смотреть не будем.
Если это не заметить, вы получаете неверный ответ на тесте 1 1 2 1 1 (ответ 3, а не 2), и по совместительству WA5 в тестирующей системе.
Кстати, было бы интереснее, если бы тест 5 не был включен в претесты. Было бы много взломов - а это всегда весело!