Kenny_HORROR's blog

By Kenny_HORROR, 7 years ago, In Russian,

При написании сегодняшнего Codeforces Round #126 и решении задачи A столкнулся с несколько неожиданными поведением. А именно при использовании двумерных массивов размера 2048 x 2048 скорость доступа к данным оказалась на порядок хуже, чем скорость доступа в случае массивов 2048 x 2047 (или 2048 x 2049, или ещё какого-то другого размера) (см. посылки 1829297 и 1830397). Данное поведение оказалось для меня весьма неожиданным (казалось бы наоборот выравнивание данных должно было ускорить доступ). Посему возник вопрос, почему же оно медленее?

Read more »

 
 
 
 
  • Vote: I like it
  • +58
  • Vote: I do not like it

By Kenny_HORROR, 8 years ago, In Russian,

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

Будем отвечать на каждый запрос отдельно. Для ответа на запрос будем делать следующее:

1) Спроецируем все точки на плоскость.

2) Выполним преобразование поворота к плоскости, так чтобы она стала Oxy.

Итого мы получили следующую задачу:

Имеется N точек на плоскости и необходимо найти такой минимальный радиус окружности, чтобы окружности построенные вокруг заданных точек имели общую точку. Пускай мы нашли радиус R и общую точку (x0, y0). Тогда рассмотрим окружность построенную в точке (x0, y0), радуиса R. Заметим, она покрывает N исходных точек. Аналогично рассмотрев некоторое покрытие исходных точек при помощи какой-то окружности, получаем окружности имеющие общую точку. Т.е. задача минимизации R в данной задаче эквивалентна задаче нахождения минимальной покрывающей окружности. Научимся эффективно решать эту задачу в силу того, что очевидный алгоритм решения данной задачи приводит к решению за O(N4M), что очевидно не подходит для данных ограничений.

Рандомизированный алгоритм за O(N).

Не нарушая общности считаем что точек более чем одна. Перемешаем имеющиеся точки случайным образом после чего будем делать слещующее:

1) Выберем две произвольные точки и построим на них окружность как на диаметре. Будем идти по точкам. Если точка лежит внутри окружности, то ничего не меняем. Если же точка лежит вне окружности, то значит среди уже рассмотренных точек она должна быть на покрывающей окружности (в силу того что не лежит внутри покрывающей предыдущие). А тогда переходим к 2.

2) Необходимо найти минимальную покрывающую окружность с одной фиксированной точкой. Для этого перемешаем точки рассмотренные в 1 и поступим аналогично пункту 1. Т.е. вначале построим произвольную на окружность на фиксированной точке и некоторой произвольной из остальных. И будем рассматривать остальные. В итоге мы получим или что мы нашли ответ, или нам надо найти окружность с уже зафиксированными двумя точками. Т.е. переходим к 3.

3)   Необходимо найти минимальную покрывающую окружность с двумя фиксированной точкой. Для этого перемешаем точки рассмотренные в 2 и поступим аналогично пункту 1. Т.е. вначале построим окружность на фиксированных точках и будем рассматривать остальные. В итоге мы получим или что мы нашли ответ, или нам надо найти окружность на каких-то трёх точках. А данную окружность уже можно найти за О(1).

Выполнив все действия указанные выше мы найдем минимальную покрывающую окружность.

Нетрудно показать, что ожидаемая сложность алгортима - O(N). А значит сложность решения   - O(NM).  

Но в силу того что данный алгоритм, не может являтся авторским решением в силу того что не гарантирует решения задачи в указанное время рассмотрим следующий алгоритм.

Детерминированный алгоритм за O(N2).

Для простоты будем считать, что все точки различны. Если точка всего одна, то ответ - очевиден радиус 0 достигается в самой точке.

В противном случае делаем следующее:

1) Выберем произвольную точку C и положим радиус R окружности описанной в данной точке равным бесконечности. Очевидно, что это не оптимальное решение, и можно сделать нашу окружность меньше выбрав радиус равным расстоянием до самой удалённой точки.

2) После выбора такого радуиса у нас возможны следующие две ситуации:

a) На окружности есть хотя бы две точки. Тогда перейдем к шагу 3.
b) На окружности находится ровно одна точка. В таком случае будем двигать центр окружности уменьшая радиус пока на окружности не окажется ровно две точки (а такой момент наступит).

3) Рассмотрим окружность C и точки которые лежат на ней.

a) На ней есть дуга опирающая на угол больше чем π (пусть у неё концевые точки D и E), то окружность можно сделать меньше двигая её центр в направлении середины отрезка DE и уменьшая радиус окружности, пока на этой дуге не появится точка или же мы не получим, окружность у которой DE  - диаметр. Повторим 3) ещё раз.

b) Любая из дуг опирается на угол не больше чем π. А тогда мы нашли ответ в силу того что куда бы мы не двигали центр радиус будет только увеличиваться и т.к. функция радиуса   выпукла.

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

Заметим, что все 1), 2), 3) выполняются за линейное время. При этом нетрудно показать, что итераций 3) будет не больше чем N - 2, а тогда общее время работы - O(N2). Или же для исходной задачи:   O(MN2)  

Read more »

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

By Kenny_HORROR, 8 years ago, In Russian,

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

  1. Обеспечение безопасности сервера (не будем забывать, что недобросовестных пользователей это прямо открытая возможно собрать и запустить вирус/эксплоит прямо на сервере).
  2. Обеспечение достаточной производительности, а также введение некоторых ограничений на  исполняемый код (например ограничения на используемую память для процесса и т.п.)
  3. О других возможных проблемах.

Вот такой вопрос.

PS: Было бы очень интересно услышать мнение и советы тех кто делал что-либо подбное/администрации данного ресурса (при условии что это не является комерческой тайной =) ).

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Kenny_HORROR, 8 years ago, translation, In English,
Div 2. Problem А. Cifera
To solve this task, let's describe what is needed more formally. We should answer whether is number l some positive degree of number k or no. To answer this question we can proceed in 2 ways:
1) Using 64 bit data type, we can find minimal degree h of number k, such that kh ≥ l. If kh = l, then the answer is YES, and number of articles is equal to h - 1. Otherwise, the answer is NO.
2) We will divide l by k, until k divides l and l ≠ 1. If l = 1, then the answer - YES and number of articles is equal to numberOfDivisions - 1, and the answer is NO otherwise.

Div 2. Problem B. PFAST Inc.
We can reformulate the statement more formally.
In this case, we have a undirected graph, and we have to find some maximal clique in it. If we have a look to constraint n ≤ 16, then there can be noticed that we can iterate over all possbile subsets of vertices and find the answer. To do this, one can use bit masks and iterate from 0 to 216, checking current subgraph for being a clique. Also, it's necessary not to forget about sorting the names while printing the answer.

Div 1. Problem A. Grammar Lessons
This task is an example of task that requires accurate realization. 
After reading the statement one can understand that we have to check whether the text from input represents exactly one correct sentence or no. If yes, therefore the text can be either a single word from our language or a following structure:
{zero or non-zero count of adjectives} -> {a single noun} -> {zero or non-zero count of verbs}, and moreover, all these words should have equal gender.
So, to check these facts, one can do the following:
We count number of words. If this number is equal to 1, we check this word for being a valid word from our language. Otherwise, we can get gender of the first word, and iterate through the rest of the words validating existing of only one noun and order of these words. Also, while iterating we check the gender of each word for being equal to the gender of the first word.

Div 1. Problem B. Petr#
 Let's find all occurrences of begin and end. Then we'll map the whole string to number 0. After this we will simply add one symbol per iteration to already seen sub-strings and map new strings to some non-negative integers. One can notice that we will never reach a situation when more then 2000 different strings exist, so we can map them easily. Now, as per we know all the ends and beginnings of strings and different string of equal length are mapped to different numbers ( and equal strings are mapped equally), we can simply count the number of necessary sub-strings of certain length. So, we have time complexity O(N2LogN), since we are making N iterations and each is done in O(NLogN) time. 

Div. 1. Problem C. Double Happiness
In this task one have to find quantity of prime numbers that can be reproduced as sum of two perfect squares. Obviously, that 4k + 3 prime numbers are not suitable as sum of two perfect squares can not be equal to 3 (of course, modulo 4). So, we can prove or use the well-known fact ( also known as Fermat theorem), that every odd 4k + 1 prime number is a sum of two perfect squares. Also, we have not to forget about 2, as 2 = 12 + 12
Now, how can we get this task accepted? Simply using the sieve will exceed memory limit, but we can use block sieve, that works in the same time (), but uses of memory. Also, we can use precalc for intervals of length equal to 100000. Also, Romka used the fact, that using bitset compress memory up to 8 times, and it will enough to suite the ML. Also, it would be nice to count only odd numbers while buliding the sieve.

Div. 1. Problem D. Museum
Let's consider a pair (i, j) as a state - this means that now Petya is in room i, and Vasya is in room j. Therefore, their meeting is state (i, i) for some i. So, it's quite easy to build transition matrix - this means that for each state (i, j) we will know probability of reaching state (x, y) in one step, where 1 ≤ i, j, x, y ≤ n. Also, from meeting state we can reach only the same state.
Let's try to solve such a problem - what is the probability of meeting in the first room? We build system of linear algebraic equations:
, where a(i, j), (x, y) —  probability of transition from state (i,j) to state (x,y). One can notice that p(1, 1) = 1, and p(i, i) = 0 when i ≠ 1, and the answer will be p(a, b).
This system can be easily solved using Gauss method. Similarly we can solve such a problem for every room (considering that we will meet in certain room), but we have complexity O(n7), that will not pass time limit. But, after some observations, we now see that each time we are solving system Ax = b (and the only thing that is changing  —  is vector b). So, we can solve matrix equation Ax = b, where b is a matrix with dimensions n2 * n, and the answer will be in the row that corresponds to state (a, b) . With this approach we have time complexity O(n6), that will pass time limit.

Div. 1. Problem E. Sleeping
Let's consider function F(x) (where x is some moment of time)  —  amount of moments from 0..00:00..00 up to x (and x doesn't switch to next moment ) when n k or more digits will be changed . The answer will be F(h2: m2) - F(h1: m1), also it's necessary not to forget that if h2: m2 < h1: m1, then F(h2: m2) will be enlarged by a day.
Now we will learn how to calculate F(x). To start with, let's count amount of such numbers when hour will remain the same. As hour is not changing, then k or more digits have to be changed in minutes, but in this case we need our number of minutes to be of the following form:
a..a99...9, where a means any digit,and at the end we have k - 1 nines. So k digits are changing every moment that is divisible by 10k - 1.
So, the total amount of such moments (without changing an hour) is , wherehx и mx are numbers of hour and minute in time moment x, and [] is integer part.
Now let's deal with such moments when hour is changing. If this happens, then minute turns from m - 1 to 0, and we have y different digits, where y is amount of non-zero digits of number m - 1. Therefore we have to count for hours ( in similar way) amount of moments, when k - y or more digits will be changed. k - y digits are changing every moment that is divisible by 10max(0, k - y - 1), this means that total amount of such moments is . And the final value of F is .


Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it