Golovanov399's blog

By Golovanov399, 10 months ago, In English

Hello, codeforces!

I have created a tool for testing interactive problems. If you do not know what it is, I recommend you to read Interactive Problems Guide before/instead of reading this blog. It is important to understand that this tool does not help, in any way, to solve interactive (and all other types of) problems, where by "solve" I mean "come up with the solution". Today's June Lunchtime introduced an interactive problem called XOR, The Detective, where I used my tool and it helped me to debug my solution, so I would like to use this chance to show the tool in work. With all of this out of the way, let's begin.

Debugging interactive solutions in general

I can't say about everyone, but for me personally debugging a solution to an interactive problem is much harder than to a non-interactive one. First of all, basic testing on samples is already non-trivial: while usually I copy-paste the sample into a file, which I then read from, it does not work this way with interactive problems. I don't know which queries my solution is going to ask, and hence what to respond; so I can't write all the answers into the file, as I don't know them in advance. And even if I have tested the solution by manually entering the correct responses, and then I want to test it on the same test again (say, I fixed a minor bug), I cannot simply select all text and paste it into the input file, because I need to separate the queries from the responses.

Moreover, calculating the responses itself requires visualizing things in my head or calculating xors or something, which takes time and efforts.

So what one usually does to (stress-)test an interactive problem is the following: comment the parts of the code which read stuff and replace them by internally calculating the answer with some chosen input. For example, instead of:

int ask(int x) {
    cout << "? " << x << endl;
    int res;
    cin >> res;
    return res;
}

one can use something like:

int ask(int x) {
//  cout << "? " << x << endl;
//  int res;
//  cin >> res;
//  return res;
    return calculate_answer(x);
}

If one doesn't want to comment/uncomment stuff before each submission, they can use macros, for example:

int ask(int x) {
#ifdef TEST
    return calculate_answer(x);
#else
    cout << "? " << x << endl;
    int res;
    cin >> res;
    return res;
#endif
}

Then the only change that needs to be done before submission is commenting the line with #define TEST (or even nothing, if you compile your code with -DTEST).

Personally I like this way, because it is quite fast, convenient, and automatically allows you to use internal implemented stuff when answering a query (for example, if your solution calculates the depth of every vertex in a rooted tree anyway, you can use it to return the distance between two vertices).

So what does this tool do?

The tool works in the following way: you write an interactor and then run something like interact ./solution ./interactor, where solution and interactor are your executables. Some advantages in comparison with the first method:

  • You don't need to change your code before submission;
  • Usually it is easier and faster to write the interactor from scratch (arguable, but it is certainly almost never longer or more difficult);
  • You see the colored interaction protocol, where it is also easy to see which line was printed by which program.

For example, in the problem I mentioned, when I finished implementing my solution, to test it, I wrote the following simple interactor:

int.cpp

When I ran interact ./qwe ./int, I saw this:

output of the command

Because of this report, I found that my code didn't manage to properly restore the bits where two numbers differ, so I knew which part of my code was faulty. And indeed, after fixing a bug I got this:

interact ./qwe ./int

After I submitted my code, it passed all the tests.

Installation and usage

The script can be downloaded from my github. To use it, one simply runs python3 interact.py <args>. It is probably more convenient to setup the following workflow, though:

  • Create a directory for such scripts (optional);
  • Move the script in such a directory (or in any other);
  • If you use Linux, you may make this file executable using chmod +x interact.py;
  • If you use Linux + Terminal, add the following line in your .bashrc or .zshrc: alias interact="python3 <path-to-script> --color". In my case, it is alias interact="$HOME/misc/interact.py --color" (I omit python3 because I made the script executable). To use it immediately after this, you may need to relaunch the terminal or run source ~/.bashrc (source ~/.zshrc and similar);
  • If you use Windows, you may want to add the directory containing this script in the path variable. Probably, you also need something to make the script executable, I don't know anything about this.

After these steps you should be able to run the script from anywhere using the interact command. How to use it, though?

If you run interact -h you will see the following message:

interact -h

I think it is self-explanatory. One note: you need the solution and interactor executables to be single-file commands. For example, if you write the solution in python and run it with python3 sol.py, you can't specify this two words command as <solution exec>. It is easy to fix, though; maybe I'll do it.

I haven't tested it much, so feel free to report bugs or something. I also want to emphasize that this tool doesn't do anything useful except neat visualization of the interacting process; and is probably not going to be in need of frequently. Also, as far as I remember, this script should not require any additional libraries, but if it does, just install what it requires.

Full text and comments »

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

By Golovanov399, history, 11 months ago, In English

Happy new year everyone!

The next projecteuler problem is in 30 minutes. If you want to receive such notifications half an hour before other pe problems, feel free to subscribe to https://t.me/pe_in_30, its sole purpose is exactly this. It should work most of the time.

Full text and comments »

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

By Golovanov399, 2 years ago, In English

Sorry for the issues with a couple of problems

Problem A of tc/div2 (Finding Sasuke)
Problem B of tc/div2 (A New Technique)
Problem C of tc/C div2/A div1 (Perform Easily)
Problem D of tc/D div2/B div1 (Shurikens)
Problem E of tc/E div2/C div1 (Solo mid Oracle)
Problem F of tc/D div1 (Roads and Ramen)
Problem E of div1 (A Convex Game)

Full text and comments »

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

By Golovanov399, 2 years ago, translation, In English

Hi all!

This weekend, at Oct/25/2020 14:05 (Moscow time) we will hold Codeforces Round 679. It is based on problems of Technocup 2021 Elimination Round 1 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2021 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The Elimination Round authors are AndreySergunin, Endagorion, amethyst0, and me, Golovanov399. Thanks to KAN and 300iq for their coordination. This round would also be not possible without the help of our testers: kalki411, 300iq, arjunsanjeev7, brunomont, Chocobar, iankury, low_, psevdoinsaf, scnucjh, and teapotd, thank you so much!

Have fun!

The Elimination Round will feature 6 problems, preliminary costs are
500 — 1000 — 1500 — 2000 — 2250 — 3000.

Div. 1 will feature 5 problems, preliminary costs are 500 — 1000 — 1250 — 2000 — 2500.

Div. 2 will feature 5 problems, preliminary costs are 500 — 1000 — 1500 — 2000 — 2250.

Добрый день!

В воскресенье, 25-го сентября в 14:05 по московскому времени состоится Отборочный Раунд 1 олимпиады для школьников Технокубок 2021. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 14:15 до 16:05).

Зарегистрироваться на Отборочный Раунд 1 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.

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

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если Вы школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Авторы отборочного раунда — AndreySergunin, Endagorion, amethyst0 и я, Golovanov399. Спасибо KAN и 300iq за координацию. Кроме того, хочу выразить благодарность тестерам, без помощи которых этот раунд не состоялся бы: kalki411, 300iq, arjunsanjeev7, brunomont, Chocobar, iankury, low_, psevdoinsaf, scnucjh и teapotd!

Full text and comments »

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

By Golovanov399, 2 years ago, In English

Hello everyone,

Mike said that they will likely make the streams tab hideable, but it probably takes time. On the other side, implementing a simple userscript took me 5 minutes, so here it is:

userscript

To install a userscript, you can use the Tampermonkey extension, or if it is not secure or does not work with your browser, google what you should use for yourself. Anyway it is probably a temporary option. There is also another way provided by dpaleka.

Full text and comments »

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

By Golovanov399, 3 years ago, In English

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.

Full text and comments »

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

By Golovanov399, history, 3 years ago, In English

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

Full text and comments »

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

By Golovanov399, 3 years ago, In English

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!

Full text and comments »

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

By Golovanov399, 4 years ago, In English

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).

Full text and comments »

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

By Golovanov399, history, 4 years ago, In English

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.

Full text and comments »

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

By Golovanov399, history, 4 years ago, In English

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.

Full text and comments »

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

By Golovanov399, history, 4 years ago, translation, In English

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)

Full text and comments »

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

By Golovanov399, 4 years ago, In English

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.

UPD: I've updated it, so that now it caches the handle file instead of downloading it every time codeforces page loads.

Happy new year!

Full text and comments »

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

By Golovanov399, history, 4 years ago, translation, In English

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

Full text and comments »

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

By Golovanov399, history, 4 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Full text and comments »

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

By Golovanov399, 5 years 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. riadwaw 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.

Full text and comments »

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

By Golovanov399, history, 5 years 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.

Full text and comments »

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

By Golovanov399, 5 years 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.

Full text and comments »

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