Еще раз приносим извинения участникам за допущенные нами ошибки при подготовке раунда.
887A - Div. 64
Автор: .tx.
Если в строке нет единиц, то ответ "NO", так как оставшееся число должно быть положительным. Иначе найдем самую левую единицу и проверим, что после нее есть хотя бы 6 нулей.
887B - Кубики для Маши
Автор: .tx.
Ответ никогда не превосходит величины 98. Переберем числа от 1 до 99 и найдем первое такое, что его нельзя собрать из кубиков.
887C - Сборка кубика
Автор: .tx.
Возможных вариантов входных данных, на которые ответ "YES", не более 12, не учитывая перестановки цветов. Их все можно было записать в массив.
Альтернативным решением является написание функции поворота заданной грани кубика и последующей проверкой на то, что кубик собран.
887D - Рейтинги и ток-шоу
Автор: .tx.
Посчитаем два массива префиксных сумм на событиях данных во входных данных. Один по значениями (a, b), другой со значениями (c, d). Ответом является момент времени 0 или момент сразу после какого-то из событий данных в задаче. Воспользуемся методом двух указателей. Один указатель будет показывать после какого события V мы хотим устроить ток-шоу, а другой на момент времени сразу после его окончания. Тогда мы можем устроить ток-шоу, если минимум из префиксных сумм на значениях (c, d) от элементов между указателями не меньше, чем разность префиксных сумм на значениях (a, b) и (c, d) от элемента V. Также нужно не забыть проверить, что рейтинг Изабеллы не стал отрицательным раньше проведения ток-шоу.
887E - Маленький брат
Центр искомой окружности лежит на серединном перпендикуляре к отрезку AB, где A, B — точки данные в условии. Если окружность с центром в середине отрезка и радиусом половины длины отрезка подходит, то она будет являться ответом. Иначе переберем по какую сторону будет лежать центр искомой окружности относительно прямой AB. Каждая изначально нарисованная окружность блокирует непрерывный интервал допустимых значений для искомой окружности. Границы этого интервала можно найти бинарным поиском. Теперь необходимо найти минимальное незаблокированное значение для радиуса. Это можно сделать, например, с помощью метода сканирующей прямой.
887F - Модельный ряд
Автор: Denisson.
Для каждого элемента массива ai рассмотрим x элементов справа от него. Если нет ни одного элемента меньше пометим ai как "-1" и назовем "плохим". Если есть ровно один такой элемент, тогда проведем ребро из ai в этот элемент. Иначе свап элементов массива никогда не сделает ai плохим. Если теперь нет ни одного плохого элемента в массива, тогда ответ "YES". Иначе найдем самый левый плохой элемент bad в массиве. X элементов после него не меньше, чем он сам. Все элементы перед ним также не меньше, чем он сам, так как иначе элемент меньше, чем bad, также был бы плохим. Свапать bad с элементом на суффиксе также не имеет смысла, так как на его место встанет элемент еще меньше и позиция останется плохой. Таким образом, свапать bad с другими элемента массива не имеет смысла. Единственный способ удовлетворить всем условиям — свапнуть один из x элементов после bad с другим элементом на оставшемся суффиксе без учета отрезка длины x после bad. Попробуем сделать это явно. Тогда должны выполняться следующие условия. Пусть мы зафиксировали элемент y на оставшемся суффиксе, тогда такое свап может быть ответом, если y < bad. Также на суффиксе после y и на отрезке между y и отрезком длины x после bad не должно быть плохих элементов. Элемент, с которым мы свапаем y, из отрезка длины x после bad должен быть меньше любой ссылки на y. Нужно не забыть проверить, что после свапа для элемента y справа от него найдется элемент меньше него на расстоянии не больше, чем x.
Время: O(n) или O(nlogn).
Нет доступа к кодам.
Поправил
Это нормально? Что кубик рубика решается так. http://codeforces.com/contest/887/submission/32030231
What about English ?
It will be soon
Can Someone Explain Problem B Div 2
Here is longer, but more understandable code. Approach is iterating numbers from 1 to 999 and checking if we have all digits in cubes.
I seem to be misunderstanding something. How can we make 1 in test case 1? The way I understood the problem, we have to pick one digit from each die to form a number. To form 1 we need two 0s and one 1, right? 0s are available only in the 1st and 2nd die, and the third one doesn't have 1. Can someone please help?
Code checking all possible combinations.
Is complexity O ( n! * 20^n ) ?
Can Someone Explain Problem A Div 2
In problem A, its enough to check if there are at least 6 zeroes after the first one. Since you can only delete the numbers, in order to make a positive number divisible by 64 in binary notation, you need to have 6 trailing zeroes at the end, and this is only possible to achieve if you have 6 or more zeroes after the first one.
I have to admit the contribution spike was pretty fun to watch while it lasted
How to solve DIV. 2 F
Accepted solution 32144259:
1) Place 0 (designer) to the end for simplicity.
2) Build min segment tree (MST).
3) Find first error position F on [0; n-k] using MST. Go forward. {n-k is because designer excludes errors for bigger indeces.}
4) Find last error position L on [F+1; n-k] using MST. Go backward. If there is no error, L=F.
5) Intersection of all error scopes is [L+1; F+k]. It is the only segment where one can put a value to fix errors. {It's obvious when all variants are pictured.} If this segment doesn't exist, answer is NO. {In other words, one can't fix all errors using one swap.}
6) Donor segment is [L+k+1; n-1]. There may be values which are (a) less than all errors and (b) can be swapped. If this segment doesn't exist, answer is NO.
7) Check dependencies for every i-th value on [L+1; n-k-1]: if i-th value is bigger than only one j-th value on scope [i+1; i+k], store i to j-th dependency list.
8) For every i-th position on intersection [L+1; F+k] store min in scope [i+1; i+k].
9) For every pair i:j (i on [L+k+1; n-1] and j on [L+1; F+k]) check whether their swap is correct:
a) Fix errors: i-th value is less than F-th (the least error).
b) Don't add error to j-th position: min (from step 8) for j-th position is less than i-th value.
c) Don't add errors to positions dependent on i-th: i-th value has no dependecies (from step 7) or dependencies are not broken when value is moved to j-th position (last dependency index is less than j).
First correct swap gives YES.
on step 9 the complexity is up to n ^ 2 / 4 so how can it pass ?
I can't compose a case where searching for the first correct swap requires checking all i-th values and all j-th values for every i-th value. (Perhaps the authors can't either.) And I can't prove that such case can't exist. (Perhaps the authors can.)
В задаче B в тесте 49
2
0 2 9 8 1 7
6 7 4 3 2 5
мы не можем составить число 10?
Не можем
А почему? У нас ведь и 1, и 0 есть
Потому что они на одном кубике. А мы можем с каждого кубика только одну грань выбрать.
The following is a C++14 Depth-First Search solution for problem 887B - Кубики для Маши.
32040746
I wonder why I'm seeing the word "Knight" in quite a few handles.
Perhaps you'll see one day "The United Knights of Codeforces". :-)
Best wishes
In problem D, how to understand “The answer is either 0 or the moment of time right after an event occured. ”
-- Why? I think that it could be when we need to use "blue" len.
Not obviously for me. Why?
I have understood both cases. It seems to me that there is a mistake in editorial. It says that
It doesn't true.
How can I prove it? We need that:
Then we can get such thing:
Denisson, fix it if I am right.
The following is a C++14 solution for problem 887C - Сборка кубика without rotation.
The solution introduces a face_t C++ structure that holds the colors of the four squares in the face. The data input is stored in a 6-item array of the face_t structure.
Since three bits only are sufficient to store any of the six color numbers, the face_t C++ structure stores the colors of the four squares in four 3-bit width bit-fields.
A one-move solution must satisfy that two opposing faces are ordered, and the colors of the four squares in the other four faces are ordered in pairs such that exactly one more either clockwise or anticlockwise causes all four faces to be ordered.
32108240
Best wishes
What is this? why do you all upvote this? this should not be upvoted! by doing this you have made Denisson's Contribution positive! I am really disappointed in the Codeforces community! shame on you all!
We will look forward good contests from Denisson. Good luck to all.
Shame on you too! double shame on you! people should realize that when they make a contest they should think for one second that their problems should be good and before the contest even read the problem statements and as i have seen they even messed up the Announcements to! they messed up but they could have fixed it faster not 1 hour in to the contest! but to speak the truth i am a little heart broken from what you said, apologize for what you said please.
P.S: how do you know that i haven't made a contest before or i don't have one proposed?
the wording of problem A is a bit weird (in light of tests): it says "if it's possible to remove some digits", and for test case 1000000 you cannot remove anything to keep number positive and divisible by 64 EDIT: i missed that it was clarified later, sorry for the noise
for 887B if input is :- 2 0 2 9 8 1 7 6 7 4 3 2 5 why output is 9? as 1 and 0 is in input
plz help me