Добрый вечер.
Сегодняшний раунд, как и прошлый, опять мой. Этот раунд будет для участников второго дивизиона, однако участники первого дивизиона тоже смогут принять участие вне конкурса.
Раунд мне помогали готовить RAD, Connector, it4.kp, а также MikeMirzayanov. На английский язык условия перевела Delinur.
На этот раз контест будет проходить в старых добрых традициях Codeforces. Никаких нововведений, в меру короткие и понятные условия.
Разбалловка задач стандартная: 500-1000-1500-2000-2500.
Всем удачи!
UPD. Раунд завершен, рейтинги обновлены.
Победители:
1. tsundere
2. jte
3. abacadaea
4. ltaravilse
She isn't a coder (as far as I know), but she is great translator for texts such as statements on CF, so she usually translates contests into English.
А максимум из набора выпуклых вних функций - тоже выпуклая функция. Тернарники летают, как показывает практика.
Глубокий 2 дивизион, привет.
Ответ будет засчитан, если расстояние от данной точки до самой удаленной планеты будет отличаться от результата жюри не более чем на 10 - 6 по абсолютному или относительному значению.
Давайте прикинем. Посчитать расстояние, кроме как корень из суммы квадратов длин проекций вектора на оси мы, вроде, не можем.
Если d имеет погрешность 10 - 6, то d2 должно иметь погрешность 2d, то есть 2 * 10 - 6. Значит, каждый из трёх квадратов чисел, стоящих под корнем в d должно иметь погрешность 2 / 3 * 10 - 6 < 7 * 10 - 7. Каждый из этих трёх квадратов имеет порядок 108, значит нам нужен тип данных, держащий
Стандартный дабл (кроме которого, например, в VC++ ничего нет) гарантированно держит 15 цифр. Не знаю как вы, а я бы побоялся давать задачу с такими узкими рамками.
UPD:
0_o зашла...
UPD:
Так может и пройти, будем ждать систесты.
У нас получилось в результате x2 + y2 + z2 + 2 * e * (x + y + z) + 3 * e2, а вся эта величина - порядка 3 * 108 из-за первых трёх членов. И уже она должна иметь маленькую погрешность порядка 10( - 6).
1
10000 10000 10000
тоже ошибается уже на третьем-четвёртом знаке, походу :-(
It seems inconsistent. If it told be TL with the initial hack message, I would know what to fix straight away... :(
I had an idea, but I'm not quite sure if it works.
Let C be the optimal point, R be the maximum distance from C to any other point in the input and S be the sphere with center at C and radius R. We have 3 cases:
1 - S has 2 points from the input on its surface in which case C is the center of the line connecting these 2 points.
2 - S has 3 points from the input on its surface in which case C is the center of the circle connecting these 3 points.
3 - S has 4 or more points from the input on its surface and we can determine the center easily given 4 points.
Nice contest BTW, but problems A to D are a bit easier than usual I think.
I think the intended solution is Hill climbing
However, I have never seen it used in any kind of algorithm competition before. I would also be grateful if somebody could give me some more examples of problems with solutions like these.
min_z = min. z coordinate in given set of points
max_z = max. z_coordinate in given set of points
Though, it might be inefficient as answer can be real number instead of integer value.
There are quite a few solutions with nested ternary searches accepted, too.
But I doubt this was the expected solution to implement, as it took like more than a century since the smallest enclosing circle problem was posed by Sylvester in 1857 for a linear algorithm to be found ...
edit: never mind. I guess I wanted apply a trick in practice like in here, but it doesn't seem to help.
Here is an approach:
- Isolate a center point. Call it C. Separate it from the others. We search for a minimum sphere that contains C.
- Invert with respect to C. A sphere that contains C is inverted to a plane that does not contain C. A point inside the sphere is inverted to a point on the other side of the plane.
In particular, the minimal enclosing sphere is inverted to a plane that is as far as possible from C, and such that all points are on the other side from C.
- Find the 3d convex hull, in O(N lg(N)), deduce the farthest plane in O(N).
- Invert again, to get the minimum sphere.
Буду внимательно читать условия!!!
Буду внимательно читать условия!!!
Буду внимательно читать условия!!!
Буду внимательно читать условия!!!
Мне понравился этот контест, только надо было его с конца писать))
Вот у меня шаманство с квадродеревом не прошло 2й претест по времени =\
Вообще я пробовал 2 подхода:
1) Бинпоиск по ответу с октадеревом для нахождения точки пересечения: жёстко тормозит даже на тесте из условия.
2) Спуск по дереву с поиском минимума: находим значение нашей функции в центре текущей области. Если он больше текущего минимума как минимум на половину "диаметра" области, то отсекаемся иначе спускаемся во все 8 потомков.
THIS
IS
CODEFORCES!!!!!!!11
10 2 13 100
20 1 3 10
20 1 2 6
ответ 32... а не 30???
10+10+6+6=32
(#1 #1 #2 #2)
With bi of i-th stuffing (and ci of dough) baker can make a bun. So if he has ai grams, he can make at most ai/bi (integer division) buns with i-th stuffing.
I guess the following formulation would have been less prone to misinterpretation : « Lavrenty knows that he possesses ai grams of stuffing i. It takes exaclty ... ».
But part of solving a problem is understanding its statement =)
Берем произвольную стартовую точку. Для нее выбираем самую удаленную планету. Чуть-чуть двигаемся в сторону самой удаленной планеты (например на 0,1 этого расстояния). И так много-много раз. Потом уменьшаем коэффициент, с которым мы продвигаемся в сторону самой удаленной планеты.
И все.
Then, for example, the way from (x, y) to (x+dx, y) is clear if a[x][y] + ... + a[x+dx][y] = 0.
These sums can be precalculated just after reading the matrix and then obtained in O(1) time.
Isn't getting a problem accepted, algorithm dependent and language independent?
but my point is if an algorithm isn't good and takes much time, it should get TLE in both java and c++ , not just java.
otherwise I think it would be good to set Time Limit for java twice long as other languages. like some of other online judges.
BTW, you used Thread, how much faster is it than using a simple class?