387A - Георгий и сон
Я опишу достаточно простое решение. Пусть Георгий проснулся в h0 часов и m0 минут, а спал ровно h1 часов и m1 минут. Получим числа hp = h0 - h1 и mp = m0 - m1. Если mp < 0, то прибавим к нему 60 минут, а из hp вычтем единицу. Потом, если окажется что hp < 0, то прибавим к нему 24 часа. Вывести ответ на C++ очень просто следующей строкой:
Сложность решения: O(1) по времени / O(1) по памяти.
printf("%02d:%02d", h[p], m[p]).
Авторское решение: 5850831
387B - Георгий и раунд
Переберем количество требований на сложности, которые мы удовлетворим, остальные задачи мы придумаем и подготовим. Понятно, что если мы решили удовлетворить i требований, то выгодно взять те, что обладают минимальной сложностью. Упростим i самых сложных задач до самых легких требований. Если все прошло успешно, то обновим ответ величиной n - i.
Сложность решения: O(n2) по времени / O(n) по памяти. Отмечу, существует решение и за линейную сложность O(n + m).
Авторское решение: 5850888
387C - Георгий и число
Получим следующее неприводимое представление числа p = a1 + a2 + ... + ak, где + — конкатенация, а числа ai имеют вид x00..000 (некоторая ненулевая цифра, потом нули). Найдем самой большой индекс i, такой, что число a1 + a2 + ... + ai - 1 < ai. Если такого i нет, то i = 1. Тогда ответом на задачу будет число k - i + 1. Сравнения чисел можно производить, используя длину чисел и первые цифры. Попробуйте доказать это, используя единственность неприводимого разложения.
Сложность решения: O(n) по времени / O(n) по памяти.
Авторское решение: 5850919
387D - Георгий и интересный граф
Для решения данной задачи нужно знать что такое максимальное паросочетание.
Переберем центр графа i. Удалим все дуги вида (i, u) и (u, i). Пусть таких дуг cntWithI. Количество остальных дуг обозначим за Other. На остальных дугах и всех вершинах, кроме i, запустим алгоритм поиска максимального паросочетания, если полагать в качестве левой доли степень исхода, а в качестве правой степень захода. Дуга из нашего графа (i, j) будет равна дуге (i, j) — где i в левой доле, а j — в правой. Пусть его размер равен leng. Тогда ответ равен для текущей вершины равен 2n - 1 - cntWithI + Other - leng + (n - 1) - leng. Обновим глобальный ответ. Почему так можно делать? Понятно, что если мы найдем максимальное паросочетание в графе, мы удовлетворим максимально возможное количество требований на степени исхода и захода. Поэтому ребра из максимального паросочетания мы удалять не будем, удалим все кроме максимального паросочетания, и дополним его до полного паросочетания добавив (n - 1) - leng ребер. Следует добавить, что важно требование, что петли разрешены. Без этого разрешения так решать задачу нельзя.
Сложность решения: O(n2m) по времени / O(n + m) по памяти.
387E - Георгий и карточки
Посчитаем массивы pos[i] — позиция числа i перестановке p, и need[i] — нужно ли удалить число i из перестановки p.
Теперь рассмотрим числа a1, a2, ..., an - k — числа, которые нужно удалить. Понятно, что их выгодно удалять в порядке возрастания, это нетрудно доказать.
Теперь будем иди по всем числам от 1 до n. Дополнительно будем поддерживать упорядоченное множество (set <> в с++, TreeSet в Java) — позиции не удаленных чисел, строго меньших текущего. Эти числа, как раз, могут создать <<препятствия>> для позиции текущего числа. Данное множество очень просто поддерживать. Для удобства, можно добавить в данное множество числа - 1 и n. Теперь очень просто узнать размер максимального подотрезка, на котором число будет минимум. Это делается с помощью стандартных функций языка программирования (lower и higher в Java) Теперь осталось воспользоваться деревом Фенвика, чтобы узнать количество еще не удаленных чисел на данном отрезке.
Сложность решения: по времени / O(n) по памяти.
Очень короткая реализация решения на языке Java: 5850986
Can anyone explain the solution of problem C
Well my approach to this question was different , just start from the beginning and take 2 string variables. Let the variables be g and l (for global and local resp.),now g will store the substring starting from the beginning till just before the index from where l started.Now if the next character is '0' then we are bound to include it in the local string otherwise just see that whether g>=l or not , if yes then increase ans by 1 and include l in g (g+=l) and clear l, else make ans=1, g=g+l and clear l. This is because if g<l then obviously the substring in l should occur before g in resultant substring (meaning it will be "lg" instead of "gl"). Finally print the ans........
Hope it helps....
Hello, (sorry for my poor english) My solution traverses the string with 2 pointers and whenever it encounters a string representing a smaller number than what's left then add 1 to the answer. It is not necessary to generate any substrings... Just analyze the representation of strings of equal length. Here's my solution: solutionECMC
I am not generating any substring as such , it was the concept used in my solution, my time complexity is O(n).
У кого — нибудь зашло в Е такое? : для каждого из чисел не входяших во второй массив, бинпоиском будем искать левую и правую границу(отдельно) проверкой минимума с помощью дерева отрезков ? Просто ТЛ8, или я криво пишу, интересно
У дерева отрезков сверху есть довольно внушительная константа, 10 ^ 6 * log^2(10^6) * C(от дерева отрезков) это уже довольно много ~10 ^ 9 операций, что обычно не заходит в 2 секунды.
Можно без бинпоиска — за один подъем и спуск по дереву отрезков можно найти ближайший элемент меньший заданного. 5852493 (см. функцию
left/right(int i))
)Не много не пойму как работает %02d в этом выводе printf("%02d:%02d", h[p], m[p]) подскажите пожалуйста!
0 — ведущие нули, 2 — минимальная длина числа, d — квалификатор для int.
Спасибо, а то обычно использую cin/cout, иногда очень редко scanf/printf и о такой особенности, как ведущие 0 к сожалению не знал...
Ну теперь то я по полной оснащен операциями с ведущими 0, спасибо!)
Вывести ответ на c++ очень просто следующей строкой:
printf("%02d:%02d", h[p], m[p]).
а разве это не в стиле С
А в стиле С++ как раз cout<>
upd почему такой ответ не заходит
cout << "0" << hour << ":" <<"0" << min << endl;
Мне кажется, я сказал вывести на c++, а не в стиле с++.
Ну например на тесте
вывод будет таким:
а так можно
if(hour<10 && min<10) {
cout << "0" << hour << ":" <<"0" << min << endl;
return 0;
} система почему-то пишет,что ответ 00:00,хотя в консоли 00:06
Можно и так, только тогда видимо нужно 4 случая рассмотреть.
Возникли проблемы с DIV2 B. Не могу понять в чем проблема и что я делаю не так...
У меня есть решение проходит только тесты из примеров http://pastebin.com/nf3Axmm0
Суть моего решения в том, что я просто смотрю на массив a и смотрю сколько элементов из него я могу встретить в b, то есть сколько задач у меня уже готово, если для какого то a[i] я не могу найти ни одной подходящей задачи из b то я увеличиваю ответ, потом просто вывожу ответ.
Подскажите пожалуйста, что я делаю не так?
такой тест:
1 1
5
1
ответ: 0
В третьем абзаце описывается возможность понижать элементы первого массива. Соответственно, 5 понижается до 1.
Спасибо, я понял, но скорее ваш тест должен выглядеть так
1 1
1
5
Вот тогда ответ 0, а у вас ответ 1.
да
I don't understand the solution of D . can anyone explain? what to do? why the last part of answer
(n-1)-leng
for?We will add some arcs to create prefect matching in graph
I think the equation came from these :
ans = 2*(n-1); // for adding the (u,i)and(i,u) edges
ans = ans — (cntWithI) ; // they were already given, so we do not need to delete them,
ans = ans+1 ; // the center must have a self loop according to problem description.
ans = ans + Others ; // delete all the extra edges;
ans = ans — leng ; // do not have to delete the matching edges
ans = ans+ (n-1) ; // add n-1 self loops
ans = ans-leng ; // 'leng' number of vertices do not need self loop;
Hope it helps somebody.
Не совсем понятен в задаче D момент с удалением вершины и инцидентных ребёр, с последующим запуском алгоритма Куна.
А именно, почему гарантируется что на подобном графе алгоритм Куна вернёт максимальное паросочетание? Ведь граф может быть отнюдь не двудольным.
Поправьте, пожалуйста, меня.
Нет, почему. В разборе написано, нужно что-то вроде раздвоить вершины: "если полагать в качестве левой доли степень исхода, а в качестве правой степень захода. Дуга из нашего графа (i, j) будет равна дуге (i, j) — где i в левой доле, а j — в правой."
In the problem D, said "The complexity is: O(n2 m) time." But n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ 1000). Can you explain why this complexity wont TLE? thank you.
Yes. First, let's calculate number of operations: it is about 2 * 108. It is not so much. If you have good implementation of Kuhn, it would pass. Also, I know, that number of operation is much lower than 2 * 108.
Test case 4 for Problem D says N = 153, M = 392. But there are only 391 edges in the input file.
http://codeforces.me/contest/387/submission/5868021
Am I misunderstanding something? Thanks.
Testcase is valid.
What does n variable mean in C problem tutorial?
n is the length of the number from the input.
So, for 800101 we have a1 = 800, a2 = 10, a3 = 1, and n = 6. what value has i for this example, 1 or -1?
i equals to -1. I understood, that there is an small mistake: answer is k - i + 1
Sorry for so many questions, but I can't still understand how we count answer answer for 800101. here k equals 3, i equals -1 (as you said), then answer should be k — i + 1 = 3 — (-1) + 1 = 5 when answer here is 3.. What I didn't understand correctly?
Oh, it's my mistake. If there is no such index, index i should be equals to 1, yes.
Okey. Then I understand and I'll think about proof. Thank you! :)
In problem C, the definition of the array need[i] in the description does not match with the code provided. The actual definition of need[i] should be : need[i] — equals to 0 if we should remove number i from permutation p, and 1 if we shouldn't remove i from permutation p. Please correct me if I am wrong.
Yes, description does not match with the code provided. There are only ideas in editorial, so there are can be differences.
Problem C is really a challenge for me!!! Orz!!!
Who cares ?
Sorry, I misunderstood the problem. Now it's much easier.
Who cares ???
Seems you care. :D
For C question, the answer for "945" should be 2, right? Seems like author solution is giving 3. Am I missing something here? Editorial logic seems fine but author's solution seems unclear to me.