Golovanov399's blog

By Golovanov399, 4 months ago, In English,

Hello everyone,

About 7 months ago I posted here about a tool for converting some rectangular grid cell coordinates into a sort of interactive picture. AlexDmitriev proposed to make the same for hexagonal grids. Personally for me drawing hexagons during the contest is a pleasure, but it takes time and it's definitely a good idea to make such tool. Yesterday I remembered about this and made it, so welcome. Here are some use cases.

When you proceed, you should see something like this:

This tool does almost the same as the rectangular one, but there are some differences:

  • Show axis directions checkbox. The most useless checkbox, it just shows you the axis for the used coordinate system without even labeling them.

  • Show coordinates checkbox. Writes a pair of coordinates in each cell.

  • Show cell under cursor. If in the previous version cursor revealed coordinates of the cell which it was over, here it highlights this cell. However, it has some limits, read further.

  • Show grid. Shows cell borders. Here is where the evilest evil hides. You see, drawing a rectangular grid of size n × m requires drawing O(n + m) lines. Here is a different story. To draw a hexagonal grid of size about n × m one should draw O(nm) segments. Of course they can be decomposed into O(n + m) (intersected) paths, but I'm not sure whether it will reduce the drawing time (however, it'll reduce the number of .beginPath() commands, but I don't know if it's so slow in js). This is why there is a size threshold after which grid drawing may take a long, and one can unmark this checkbox to draw only needed cells (of course in O(theircount)). It's especially annoying if one moves his mouse over a big grid which is being redrawn after each move (yes, maybe after a while I will not erase everything but repaint only the cell under cursor), so if the bounding box is big enough, one can see an icon with a cursor and a cell crossed out. This means that the cell under your cursor will not be highlighted independently of the previous checkbox. It's made in order to make this ugly performance less visible for users.

Maybe (not very likely) some new functionality will be added. You can copy and modify any code you'll find.

Read more »

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

By Golovanov399, history, 7 months ago, In English,

Hello everyone,

Some of you may know about recently discovered vulnerabilities (well, technically, there in one vulnerability and two attacks using it). I am not a cybersecurity expert, I know what is going on about the "read-all-those-breaking-news-titles" level, but as I understood, some things can slow down by 30%. So I have a couple of questions:

  1. Do testing systems like codeforces, yandex.contest, topcoder, atcoder, csacademy etc apply the patch? I don't know if testing machines store something that is important and shouldn't be stolen.

  2. If yes, does this mean that we now should multiply all time limits by 0.7? Maybe this coefficient is not so small because 30% is reached on some other type of operations which are not used in cp? On the other hand, branch prediction is used almost always in cp, as I know.

Somebody who knows how this works, answer, please.

Read more »

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

By Golovanov399, 12 months ago, In English,

Hello, everyone.

I guess that those of you who doesn't solve problems only in his mind use pen and paper to make some notes, eg draw graphs, points, lines, permutations, shortly, everything. It's very convenient, but there are tools on the internet that make this process more comfortable in several cases: for example, a graph editor or a geometry widget (there was a nice page by zxqfl, but it seems to be expired or something). All these services allow to obtain visualizations from some (debug-)print-friendly format, which can save your time.

Once I decided to write a tool for drawing grids (as I remember, it was approximately when I was solving the task from the last russiancodecup). You can find it here. Some usecases are also provided. The default text in the textfield is a brief manual, but you can type something and see what happens.

Below you can see an example of usage (based on the problem from rcc above):

Maybe (not very likely) some new functionality will be added. You can copy and modify any code you'll find.

Read more »

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