Codeforces в консоли linux
Основопологающие алгоритмы в ядре ОС Линукс
Очень долгое время я не мог понять: когда я буду писать алгоритмы и структуры в продакшн коде также, как я это делал на олимпиаде? Время шло, а ничего сложнее бинарного поиска и расстояния Левенштейна не нужно было (все работало и так быстро, а структуры и алгоритмы были бы в ущерб модулярности).
Конечно, очень часто нам не нужно думать об эффективных алгоритмах, когда всю тяжелую работу выполняют база данных, веб-сервер и операционная система. А твой код лишь рисует веб-странички или кнопочки в приложении на айфон.
Но именно в этих сложных системах (ОС, базы данных, веб-сервер, компиляторы, др) и используются все те основы, что мы с вами читаем с книжек типа CLRS.
Полный ответ об алгоритмах из книжек был дан на stackexchange и потом был репостнут в блогах и позже на HN. Сегодня я решил перевести ответ об ОС Линукс со своими комментариями (отсебятина) и ссылками на ресурсы на русском языке.
Так давайте поговорим об ОС Линукс, оказывается там можно встретить все, что учит любой школьник до 9 класса (а может и раньше):
- Связанные списки, двусвязаные списки и lock-free версии
- B+ сбалансированное дерево, как мы помним они еще используются в файловой системе
- Двусвязаные списки отсортированные по приоритетам (их используют mutex локи)
- Красно-черные сбалансированные деревья используются очень много где
- Дерево интервалов (НЕ дерево отрезков как в e-maxx, а дерево интервалов, где в каждой вершине сбалансированного бинарного дерева лежит два числа: от и до)
- Radix tree (более знакомый нам как Бор)
- Куча с приоритетами используется в cgroups: ограничение ресурсов доступных процессу. Модная нынче контейнеризация (LXC использует cgroups, а модный Docker использует LXC), также не удивлюсь, если линуксовская версия runexe использует cgroups.
- Хэширование по Кнуту: раз и два
- Хэш-таблицы используются для inodes — структура хранящая мета-даныне о файлах на файловой системе
- Битовые массивы (прям как Си++шный bitarray)
- Бинарный поиск, бинарный поиск в B-дереве
- Поиск в глубину и ширину
- КМП и Бойер-Мур
- Сортировка слиянием иcпользуется для системы сборки мусора
Также советуется к прочтению оригинальный пост, там еще больше примеров с ссылками на статьи на английском языке.
И в добавку примеры использования динамического программирования: link
Codeforces в консоли linux
Ввод неизвестного количества данных C++
Пишу на С++. И тут появляется задание(тренировка СПБГУ#22 ) G,а в нём нужно вводить (я использую cin) неизвестное количество чисел,вот я и не знаю как отследить,что ввод был закончен.С файлом всё просто,а тут. Помогите
UPD. Some info
как проверить что ввод закончен?
Спасибо,а то я тут перед новым годом нанервничался )
может сделать фаг по этому,а то ,я думаю, с этим многие проблемы имеют
С файлом всё просто,а тут.
Можешь это место по-подробнее объяснить?
как я понял, топикстартеру с файлами проще потому что там EOF есть
seydua имеет в виду, что тут EOF есть в точно таком же виде, как и в файлах.
В консоли это невозможно.
UPD: слишком поздно написал
UPD2: в консоли — имеется ввиду без файлов в codeblocks(или тому подобное) нажав на клавишу F9.
UPD3: Извините за неправильный ответ. Раньше мне всегда твердили что это невозможно. Слова беру назад и большое спасибо Avitella и andreyv. Узнал что-то новое)
В linux консоли есть комбинация клавиш CTRL + D. Так что все возможно 🙂
- Ctrl+Z, Enter под Windows
- Ctrl+D под Linux
спасибо, долго искал
Если нужен построчный ввод неизвестного количества данных поможет такое:
While(cin>>n) < // >или While(!cin.eof())< // >
еще же scanf-ом можно
int x; while (scanf(«%d», &x) == 1)< //do smth >
Можно использовать итераторы:
В олимпиадах я такого не видел)
Моя не понимать. Вы тут объявили eos , но не инициализировали. Я правильно понимаю, что у него в стандартном конструкторе будет какая-то шняга, которая аналогична «бла-бла-бла» и позволяет понять, когда у нас конец ввода? Но тогда вопрос, в качестве так сказать инициализатора it мы передали cin , а почему без инициализатора будет то, что нам нужно? Объясните, пожалуйста, подробнее, а то лень копаться в референсах/исходниках и чекать у себя на компе, будет ли работать ваш пример.
UPD. Скомипилилось и отработало. Объясните, почему.
Вы понимаете правильно. Работает так потому что его так написали.
A special value for this iterator exists: the end-of-stream; When an iterator is set to this value . has been constructed using its default constructor (without associating it with any basic_istream object).
Codeforces в консоли linux
Codeforces command-line interface tool
Codeforces Tool is a command-line interface tool for Codeforces.
It’s written in golang (without any browser driver). And it’s fast, small(only about 7 MB), cross-platform(Windows, macOS, Linux) and powerful.
You can find the source and binary files in my git repo https://github.com/xalanq/cf-tool
You can download the tool from release page https://github.com/xalanq/cf-tool/releases
- Support Contests, Gym, Groups and acmsguru.
- Support all programming languages in Codeforces.
- Submit codes.
- Watch submissions’ status dynamically.
- Fetch problems’ samples.
- Compile and test locally.
- Clone all codes of someone.
- Generate codes from the specified template (including timestamp, author, etc.)
- List problems’ stats of one contest.
- Use default web browser to open problems’ pages, standings’ page, etc.
- Setup a network proxy. Setup a mirror host.
- Colorful CLI.
I have tested the tool for contest Codeforces Round #551 (Div. 2).
It’s not a cheating tool, but a tool for beautiful life 🙂
Pull requests are always welcome.
Examples
Let’s simulate a competition.
cf race 1136 or cf race https://codeforces.com/contest/1136
To start competing the contest 1136!
If the contest has not started yet, cf will count down. If the contest have started or the countdown ends, cf will use the default browser to open dashboard’s page and problems’ page, and fetch all samples to the local.
cd ./cf/contest/1136/a (May be different from this, please notice the message on your screen)
Enter the directory of problem A, the directory should contain all samples of the problem.
Generate a code with the default template. The filename of the code is problem id by default.
Use Vim to write the code (It depends on yourself).
Compile and test all samples.
List problems’ stats of the contest.
Open the standings’ page of the contest.
I double click the program but it doesn’t work
Codeforces Tool is a command-line tool. You should run it in terminal.
I cannot use cf command
You should put the cf program to a path (e.g. /usr/bin/ in Linux) which has been added to system environment variable PATH.
Or just google «how to add a path to system environment variable PATH».
How to add a new testcase
Create two extra testcase files inK.txt and ansK.txt (K is a string with 0
Enable tab completion in terminal
Note: If there is a new version released (especially a new command added), you should run docopt-completion cf again.
Upvoted. I must say that this is the most complete codeforces problem parser that I have seen so far.
Thanks for the effort!
Will you support Linux in the future?
He mentioned that Linux is supported.
Yeah. Right. csrf / evercookie extraction.
Good thing that Mike never bothered to provide good api and forces people to scrape pages if you plan doing anything cf related ever.
It is saying me something like this whenever I am trying to test or submit . Is there any way I can change the config so that it doesn’t ask me for the option.
/.cfconfig , and delete one ‘cpp’ from ‘suffix’
You can run cf upgrade to update the program.
Looks like a perfect match for VS Code by using only terminal command.
Yeah. The VS Code extension is in TODO list:)
So busy. sorry. I hope someone could help me 🙂
Awesome tool thank you very much for that. I tested app previous week and everything worked fine. But now there are some problems:
- After command cf submit code will be submitted but status does not change it remains as «Running» and application freezes.
- After command cf race writes «Cannot find countdown».
You should upgrade the program 🙂 glhf
- Status does not change, but Ctrl + C can kill process. I think if status does not change in console automatically then this application is inconvenient to use, better send it through browser, because we do almost same actions in case we use app and in case we do not use app
- not fixed
Check your version by cf —version . The latest one is v0.5.4
- It works for me. I just tried to submit in 5 minutes ago. May be you should wait some seconds after submitting?
- It doesn’t work for the contest Codeforces Round #567 (Div. 2) with 5 days countdown (I don’t think this is a very bad problem, maybe I’ll fix it later), but it works for me in a virtual contest Codeforces Round #564 (Div. 1) with a 5 minutes countdown.
yes it works now, thank you for answer.
I can’t log in though I entered my correct username and password
Try again? I made an update.
I didn’t noticed it was case sensitive.
Which cf program has to put in /usr/bin?
You don’t need to install it. Just copy the execution file to the /usr/bin . Ses FAQ #2 I cannot use cf command
It says permission denied when i try to move it to /usr/bin even when i have allowed the execution as a program
go to your home directory and create a new folder called bin. Now paste the tool in that folder. Now open up the terminal and type gedit
/.bashrc and add this statement at the end of the file export PATH=»/home/$USER/bin:$PATH» .
I actually got it by using sudo and then pasting in /usr/bin
Can anyone explain me the use of template and how does it work and why is it required?
For eg: if my code is written in 123.cpp and i want to compile it then i use:
g++ -o 123 123.cpp // a binary file is created with name 123 corresponding to my code.
Now when i submit it using : cf submit contest-id problem-id 123.cpp How does the template work( suffix, alias, before script, script, after script, path).
Is it necessary to write my code in the same path as entered in template?
There are 2 template types: Code template and script template.
The script template contains the language you use (e.g. cpp, python, java), the path of code template and some extra info. You cannot submit your code before configuring the script template. You can add a script template by cf config and then select 1 . There will be some hints guiding you to configure the template.
The code template just a code file, you can generate a code file from this template by cf gen .
You said you want to compile the code, so you should focus on the script template.
There are some concepts in script template:
- suffix means the template will be used by detecting the suffix of the submitting or testing code file. E.g. you have a file in current path: a.py. Then you use cf submit , the tool will use the template which has the suffix py .
- alias means an alias for the template. E.g. you have a template with alias cpp and a template with alias py . You can use cf gen cpp to generate a code file with template cpp or cf gen py to generate a code file with template py .
- Template absolute path means the code template’s path (using it in cf gen ).
- before script, script, after script: In usage (You can see it by cf —help )
You can see how before script, script, after script works. In short, when you use cf test , the commands will be executed in sequence:
I’m sorry for my bad English. I can not express these things clearly.
Thanks a lot. It was really helpful.
One more thing that I noticed ( probably a bug ; not sure ) is that whenever we try to issue multiple commands of cf open using different contest-ids, it opens the contest page of first command issued .
Eg : cf open 100 (contest page for contest id 100 opens) cf open 200 (contest page for contest id 100 opens) cf open 300 (contest page for contest id 100 opens)
Although this issue is not experienced while specifying problem-id.
Eg: cf open 100 a (problem page for 100 a opens) cf open 200 b (problem page for 200 b opens) cf open 300 c (problem page for 300 c opens)
Hope this might be useful for next version! 😉