### Golovanov399's blog

By Golovanov399, 3 weeks ago, ,

Hello, codeforces.

I would like to tell you about some tricks and constructions I use in C++. They are not hidden or anything, moreover, most of them are from stl or maybe well known among software engineers, but I often see codes where something is done by hand in, say, 5 lines, while in stl there is a function which does the same.

The things below are filtered by my personal sense of non-popularity (so no __builtin functions) and usage frequency (so there almost surely are similar things I don't know about) and are not really sorted in any reasonable order. Let's begin.

• +704

By Golovanov399, history, 2 months ago, ,

We hope that no difficulties, misunderstanding and "wtf am i asked to do" thoughts ruined your fun!

Problem A: Nash equilibrium
Problem B: DAG
Problem C: Segment tree or Fenwick?
Problem D: Dijkstra
Problem E: Amazing bitset

In problems F, G and J we don't mention in the editorial that we assume you to have parsed the statement into a convenient programming-friendly format.

Problem F: Keep talking and nobody explodes -- easy
Problem G: Keep talking and nobody explodes -- medium
Problem H: Who needs suffix structures?
Problem I: Deja vu
Problem J: Keep talking and nobody explodes -- hard

• +107

By Golovanov399, 9 months ago, ,

Hello everyone!

I'm travelling abroad Russia. It happens that I see things which I haven't seen before (obviously), and it isn't necessary about culture (not so straightforward). For instance, recently I saw a payphone with internet access:

proofpics

I don't know if it's a casual thing in some countries, but I haven't seen not only things like this in my life, but also any working payphone for last ~18 years.

So I wondered if it's possible to submit a problem on codeforces using it. Surprisingly, the payphone was quite convenient, one just needs to get used to it :)

So I challenge everyone to get AC on any problem from the cf problemset using any non-trivial device like smart tv idk or a fridge or whatever your imagination tells you to use. Good luck and have fun!

• +362

By Golovanov399, 10 months ago, ,

Hello everyone.

A flashmt's comment (thank you) gave me an idea to modify a css on all code jam pages so that it doesn't suck that much. So what we need is:

How to use it:

1. In stylish select somewhere "create new style",

2. Press the "write new style" button,

3. Copy this css contents to the code section,

4. Tell this to apply to all urls starting with https://codingcompetitions.withgoogle.com,

5. Click the save button.

What it does so far:

• removes the problem graphs section,

• removes the "show round overview" toggle,

• reduces the height of all buttons,

• makes the section with problems scrollable.

I didn't manage to find out how to make the width of problems columns less so that everyone could see when a round contains 4 problems, not 3. Feel free to comment how to do it if you know (or suggest some other modifications).

And some gifs related.

Before After

I hope that I didn't break something (like accidentally hide the questions button or something), but I'm not sure, so use it at your own risk. I've tested it only in firefox, but it should seem that this must work everywhere (like come on, it's just a css modification).

• +106

By Golovanov399, history, 11 months ago, ,

Hello everyone.

Recent codechef long challenge had a task about queries on paths inside a tree: short, given a tree, each vertex contains a linear function, and given $q$ queries of types "add given linear $f$ to all vertices of the path between $u$ and $v$" and "calculate maximum of $f(z)$ where $z$ is given and $f$ is a function in any of vertices on the path between given $u$ and $v$", $n$ and $q$ are $\leq 10^5$, time limit is 4s.

It seems that the intended time complexity is $O(n\sqrt{n}\log{n})$, but I heard that it required efforts to get AC with this solution. On the other hand, it's easy to get ac with an $O(nq)$ solution.

Don't get it wrong: if we iterate over a path just, for example, by going from both endpoints towards the root, it gets tl (even with pragmas): submission. On the other hand, one can use heavy-light decomposition (this particular implementation is not necessary, I suppose, but it's still very nice) first (that is, sort every vertex' children by their subtree sizes), then rearrange vertices by their dfs in-order, and voilà, every path is now a union of about $\sim\log{n}$ consecutive segments. If we now do basically the same stupid implementation of what we are asked for in the statement, we get ac for 1.6s with pragmas and even ac for 2.6s without pragmas.

Hope this trick is not a mutual knowledge (though it's definitely not a common knowledge). I found it so simple and potentially usable that it deserves a post in my opinion.

• +281

By Golovanov399, history, 12 months ago, ,

Hi everyone.

Some time ago I've written a script which notifies user about fresh changes in the standings during an atcoder contest (under some reasons, one but not the only of them being the last agc, I recalled it just today). More precisely, you set the contest name and a constant $k$ (5 by default), and you get a notification for each of the first $k$ accepted submissions on each problem in the contest. This is how it looks in my laptop (I've run it after the contest finished, so that's why there are a lot of notifications):

Some details:

• The script can be downloaded here. Run python qwe.py -h for help.

• I use notify-send to notify, so one must have this utility to run this script. This can be replaced by your own way, though (change the line 43 in qwe.py).

• I cannot surely determine the task letter by its code (maybe it can be uniquely determined by the last digit, but I am not sure), but I assume that in each contest problems have consecutive codes and the problem A is likely to be solved first.

• In problems with partial scoring any positive score is considered. Moreover, if one passes the problem on, say, 800/1300, and then completely solves it on 1300/1300, you get a notification only for the first submission with positive score for this user.

• It may distract, so use at your own risk.

• +26

By Golovanov399, history, 13 months ago, translation, ,

We are sorry for not having controlled the situation about the streamed editorial and also for the broadcast message about an unethical behaviour of someone from community: here is explanatory comment to the message. When we tried to move the casino problem one position below, something went wrong leading to it being moved one position above (however, Radewoosh didn't seem to feel that something was wrong, congratulations!).

Nevertheless, we hope that you liked the problems, and those of you who decided to do something else after you knew that the round was made unrated can solve the problems when convenient (if they wish).

Problem A of final/div2 (Technogoblet of Fire)
Problem B of div2 (Mike and Children)
Problem B of final/C div2 (System Testing)
Problem C of final/D div2/A div1 (Diana and Liana)
Problem D of final/F div2/C div1 (Compress String)
Problem E of final/E div2/B div1 (Once in a casino)
Problem F of final/D div1 (Power Tree)
Problem G of final/E div1 (The very same Munchhausen)
Problem H of final/F div1 (Secret Letters)

• +157

By Golovanov399, 15 months ago, ,

Hello everyone!

Since the masquerade of colors and ranks was announced, many pseudo-creative shitblogs from pseudo-nutellas will appear soon. Of course, some of them may be funny (especially when it's not about newbies trying to look smarter but vice versa), but one can be sick about all this situation. Usually it's not funny, but annoying.

This is why I decided to create a script which would reveal the true colors and titles. I think it does not (completely) kill the idea of changing colors: if one wants to take part in this masquerade, they can ignore my post and will still see the colors chosen by others (including their own) instead of the true ones.

This extension extends the page loading time because it downloads a ~1.6mb file. It shouldn't change the title on the profile page, but what it should do is make all in-page colors look properly. It also doesn't change the site background since killing the new year spirit is not what I want to reach.

If one prefers a userscript

Happy new year!

• +121

By Golovanov399, history, 16 months ago, translation, ,

We are sorry that you were having troubles with access to Codeforces.

Problem A of elimination/div2
Problem B of elimination/div2
Problem C of elimination/div2
Problem D of elimination/div2 = problem A of div1
Problem E of elimination/div2 = problem B of div1
Problem F of elimination/div2 = problem C of div1
Problem G of elimination/div2 = problem D of div1
Problem E of div1

• +101

By Golovanov399, history, 17 months ago, ,

• +14

By Golovanov399, 2 years ago, ,

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.

• +59

By Golovanov399, history, 2 years ago, ,

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.

• +89

By Golovanov399, 3 years ago, ,

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.