removed1's blog

By removed1, 13 years ago, translation, In English

Continuing this thread (in Russian)

[disclaimer: these measurements are not accurate, they are like measuring RPM of engine during idle run, instead of time of racing car on track.., were not statistically tested, etc.]

I took maslowmw's code, changed size to 500, removed time printing (which doesn't make big difference) and tried it in Topcoder Practice Rooms. Indeed, 2d array in .NET version used at Topcoder, is slower than array-of-array (I think it should change in future, if not already: latest MS.NET version is 4.0). I got interested and tried several other variants. Here are the results, and make conclusions yourselves.

[i][j]: 1.328s
[i,j]: 1.516s
[i*size+j]: 0.875s

int [][]: 0.266s
int **: 0.791s
[i*size+j]: 0.286s % where size = const int
[i*size+j]: 0.695s % where size = input parameter
vector<vector<int>> : 0.478s % where size = const int
vector<vector<int>> : 0.608s % where size = input parameter

[i][j]: 1.927s
[i*size+j]: 1.306s

P.S.? After I clicked 'Know English' link to translate my post into English, the website removed my original tags and replaced them with "c++", "c#", "best language". WHO WROTE THIS CODE, AND WHY? Puzzle.

Full text and comments »

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

By removed1, 13 years ago, In English

Recently one of codeforces participants mentioned Java as 'flexible'. (he has not specified what he was comparing it with).

As a sceptic, I wish it to be demonstrated in problem which I have been interested long time ago.

Words I have for default font in Arena applet are not printable. It is difficult to read, which especially affects challenge phase. After I found something better, my rating grew from 1500-1700 to 2100. An ideal solution would be to use custom font (after all, humans are different). Unfortunately, tools for creating vector fonts are overcomplicated and/or expensive, and vector fonts are not needed at all in this case because the font needed will never go to printer or any other high resolution device. Raster fonts are very easy and fast to edit, but as you have might already guessed, Arena applet running under Sun's JVM does not allow to use them. I know that open JRE/JVM implementations exist. So, what is possible to do?

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By removed1, 13 years ago, translation, In English

Возможно, идея не нова, но...

"Производный челлендж-контест"

Даются обычные ACM-задачи (если на codeforces round предлагалось 3 задачи на два часа, то тут можно 20-30 минут на три задачи), которые уже использовались на каком-нибудь из контестов, для которого доступны решения участников ("контест-прообраз"). Участники за время контеста присылают не решения, а тесты -- набор из N тестов на задачу (как в топкодере, можно делать повторный сабмит). После истечения времени система проводит тестирование  неправильных решений с контеста-прообраза. Число очков, набранных участником, равно количеству решений с контеста-прообраза, неправильность которых удалось обнаружить на наборе тестов, присланных участником. Это, в некотором роде, непомерно раздутая челлендж-фаза с Topcoder.

Разумеется, такой контест, т.к. проводится на уже использованных задачах, может быть only for fun. А последнее в значительной степени зависит от разнообразия разных форматов контестов...

P.S.: недостатки челленджа на топкодере:

То, что ошибочные челленджи отнимают очки, приводит к тому, что многие новички вообще не челленджат. А раз они этого не делают, научиться этому сложно. Как результат, средний участник топкодера имеет челленджей меньше, чем SRM в которых он принимал участие. Я челленджил чаще среднего и мне понадобилось больше года, чтобы общее количество баллов от челленджей стало положительным. Также, бывают нечелленджабельные проблемсеты.

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

Full text and comments »

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

By removed1, 13 years ago, translation, In English

Problem A.

The constraint that edges of each flagstone much be parralel to edges of the square allows to analyze X and Y axes separately, that is, how many segments of length 'a' are needed to cover segment of length 'm' and 'n' -- and take product of these two quantities. Answer = ceil(m/a) * ceil(n/a), where ceil(x) is the least integer which is above or equal to x. Using integers only, it is usually written as ((m+a-1)/a)*((n+a-1)/a). Note that answer may be as large as 10^18, which does not fit in 32-bit integer.

Most difficulties, if any, contestants had with data types and operator priority, which are highly dependant on language used, so they are not covered here.

Problem B.

Let each letter representation of column number be associated with integer in radix-26, where 'A' = 0, 'B' = 1 ... 'Z'=25. Then, when converting letter representation to decimal representation, we take associated integer and add one plus quantity of valid all letter representations which are shorter than letter representation being converted. When converting from decimal representation to letter representation, we have to decide how many letters do we need. Easiest way to do this is to subtract one from number, then quantity of letter representation having length 1, then 2, then 3, and so on, until next subtraction would have produced negative result. At that point, the reduced number is the one which must be written using defined association with fixed number  of digits, with leading zeroes (i.e. 'A's) as needed.

Note that there is other ways to do the same which produce more compact code, but they are more error-prone as well.

Problem C.

The points can be vertices of regular N-polygon, if, and only if, for each pair, difference of their polar angles (as viewed from center of polygon) is a multiple of 2*pi/N. All points should lie on the circle with same center as the polygon. We can locate the center of polygon/circle [but we may avoid this, as a chord (like, say, (x1,y1)-(x2,y2)) is seen at twice greater angle from center, than it is seen from other point of a cricle (x3,y3)]. There are many ways to locate center of circle, the way I used is to build midpoint perpendiculares to segments (x1,y1)-(x2,y2) and (x2,y2)-(x3,y3) in form y = a*x + b and find their intersection. Formula y = a*x + b has drawback that it cannot be used if line is parallel to y, possible workaround is to rotate all points by random angle (using formulae x' = x*cos(a) - y*sin(a), y' = y*cos(a) + x*sin(a) ) until no segments are horizontal (and hence no perperdiculares are vertical).

After the coordinates of the center are known, we use fancy function atan2, which returns angle in right quadrant: a[i] = atan2(y[i]-ycenter, x[i]-xcenter)

Area of  regular polygon increases with increasing N, so it is possible just to iterate through all possible values on N in ascending order, and exit from cycle as first satisfying N is found.

Using sin(x) is makes it easy: sin(x) = 0 when x is mutiple of pi. So, for points to belong to regular, N-polygon,

sin( N * (a[i]-a[j]) /2 )=0

because of finite precision arithmetic, 

fabs( sin( N * (a[i]-a[j]) /2 ) ) < eps

Full text and comments »

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