#### Introduction↵
↵
Instead of algorithms and math, I'll be doing something completely different here.↵
There is something that has bothered me for a long time: people not understanding↵
the tools they use to participate in contests and thus failing to take real advantage↵
of them. And it all goes back to not understanding the command line.↵
↵
Some of you might say, "well surely, the command line is something obsolete and you're ↵
only clinging to it because you [insert ridiculous amateur-psychology here]?"↵
No! The command line is not obsolete, and unless competitive programming becomes↵
so mainstream that software vendors start writing professional-grade tools aimed↵
specifically at us, it won't be.↵
↵
[cut]↵
$~$↵
↵
What is the command line? Any of these:↵
↵
↵
↵
As you can see, it comes in many background colors and fonts, but the basic idea↵
is always the same. It's a box you can type commands in, which it will then execute.↵
↵
Why use the command line?↵
↵
- **Flexible and very powerful.** In competitive programming, there are a number of↵
tasks you have to do to work with your code locally: compiling, running, testing,↵
stress testing and so on. Modern IDEs have tools for these, but they are not really↵
designed with us in mind. Many people have written extensions to do these things↵
comfortably, but what if you need to do something slightly different, something ↵
the extension author had not anticipated? You get stuck and have to make-do with↵
some stupid hack. The command line allows you to do all those things, however you↵
want to. It's very possible that just by changing a few small things will allow↵
you to do what the extension author had not anticipated.↵
- **Submit exactly what you wrote.** A very basic thing in competitive programming↵
that you have to do is test your program, at least on the sample tests. The first thing↵
that beginners usually do is they press the "run" button in their IDE and manually type the↵
test case into the black box that appears. This is very error-prone and very time-consuming.↵
A better way would be to read the input from a file, but now what you submit will be different↵
from what you test locally. People will often tell you to use something called an "ifdef",↵
but that also has its issues, see below.↵
- **Interactive problems.** Some contests such as Google Code Jam offer a testing tool for ↵
interactive problems; IOI also offers various tools to test problems. If you have never ↵
learned the command line, you'll probably have to think for a while about how to run this. ↵
With the command line, it is dead simple.↵
- **Deeper understanding.** Understanding the command line means understanding how everything↵
your IDE does actually works. Then you are also in a better position to customize your ↵
IDE if you choose to continue using it. I mentioned testing tools for interactive problems↵
above. Usually, you have to pass your program as an argument to them. If you have↵
always relied on an IDE to run your code, you might not even grasp the concept↵
of an "executable" and getting this interaction tool to run will be an impossible task.↵
I've had to teach this stuff to people who were otherwise relatively proficient in competitive↵
programming.↵
- **Full control.** The command line offers you the most fundamental level of control↵
over what's actually happening in your computer.↵
↵
**Update 11.09.2022** More generally still, I've noticed that people often learn the bare minimum when it comes to↵
being able to edit and run programs locally. They find one configuration or setup that works by↵
trial and error and stick with that, even though when you look into it, it may be a ridiculously↵
convoluted Rube Goldberg machine. This will work until the situation slightly changes, and then you're stuck.↵
↵
The recent example that prompted me to write this comes from Meta Hacker Cup. There, you have to run the program locally on your computer within a 6-minute window, on a test file that may be quite large (let's say, 60 MB). For a number of people, the workflow included _opening these files_ and _copy-pasting their content somewhere else_. With files this size, it is quite impractical and can easily crash editing programs that are not optimized for large files (regardless of the speed of your computer). ↵
↵
Learning the command line means learning how your computer works. Understanding this stuff means that you can take advantage of it and streamline your setup for testing locally.↵
↵
##### About editors and IDEs↵
↵
As far as text editors go and what I've seen people use to write code, there are basically four categories.↵
↵
1. Classical text editors. Examples: Emacs, vi, gedit, nano, Far Manager, Notepad.↵
2. Lightweight modern code editors. Examples: Visual Studio Code, Sublime Text.↵
3. Full-fledged IDEs. Examples: Visual Studio, CLion, Xcode.↵
4. Code::Blocks.↵
↵
This is obviously not some objective classification, and the lines between the categories↵
get _very_ blurry, but I hope on an intuitive level you understand what I mean.↵
↵
My advice: don't use items in category 3 for competitive programming and don't use items ↵
in category 4 for anything. Full-fledged IDEs are meant to be used for medium-to-large ↵
software projects and are designed with that in mind. They want you to create a Solution and then a↵
Project, then set up a Build Configuration and so on. This is all very good and important↵
if you are maintaining a real software project with hundreds of classes and nontrivial↵
build sequences, but utterly pointless if all your programs are in a single file, which ↵
is what you have to do in competitive programming. Many people copy-paste their code ↵
into the box on CF simply because amid all this complexity, they have no idea where their ↵
.cpp file actually is.↵
↵
Moreover, although they are very powerful, you won't use any of this power. But you still↵
have to pay for that power by having to deal with long loading times if you have a weakish↵
computer, and using a lot of RAM. ↵
↵
Lightweight code editors, on the other hand, are great. They provide some of the simpler ↵
utilities of full IDEs, such as a "rename this variable" function, without introducing↵
all the bloat of full IDEs. In addition, they usually provide easy access to the command↵
line, giving you all the benefits I mentioned above.↵
↵
The moral of the story is that you should use appropriate tools for different tasks.↵
Software engineering very different from competitive programming, and require different↵
tools. I use GNU Emacs for competitive programming and JetBrains Rider at work, and I would↵
never want to do it the other way around.↵
↵
#### Basic tasks using the command line↵
↵
This section is organized as a "lab". If you are new to the command line and want to learn it,↵
I recommend doing everything I tell here. Of course, this is more of a tutorial on "how to ↵
do essential tasks for competitive programming", not a comprehensive tutorial on how to use↵
it in general. But I will go through other necessary commands anyway.↵
↵
##### Setup↵
↵
For this "lab", I suggest using the simplest possible program to code. Forget your good↵
IDE for a bit to avoid any temptations. Don't worry, later we will come back to the↵
fancy editors and using the command line there.↵
↵
The first step is actually opening the command line. ↵
↵
- On Windows, open the Start menu and search for "cmd.exe".↵
- On Mac, open the Finder and search for "Terminal".↵
- On Linux, it depends on your distribution, but you can usually find it by opening some kind of menu and searching for "Terminal". But if you use Linux, you probably already know.↵
↵
Windows actually has two kinds of terminals: cmd.exe and PowerShell. Both have their ups and downs, but↵
the commands are different. In this blog, I will provide commands for cmd.exe but not PowerShell.↵
↵
Once you have got it open, type `ls` (Linux/Mac) or `dir` (Windows) and press Enter. ↵
You should see a list of files and folders located in the folder you're currently in.↵
↵
##### Compiling and running your code↵
↵
I'll be assuming you work with C++, since that is the most common scenario in competitive programming.↵
First, we shall write a program. Of course, you already know how to do this, so there is no point↵
in lingering about it.↵
↵
I've written a program. Save it as `program.cpp`.↵
↵
<spoiler summary="program.cpp">↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
↵
int main () {↵
int a, b;↵
cin >> a >> b;↵
↵
cout << a + b << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
Now, we need to compile and run it. The first step is to actually locate the file in the↵
command line. In some ways, the command line is a lot like a file browser on your computer:↵
↵
↵
↵
At any given time, it is in a certain folder, and you can navigate to other folders.↵
But instead of double-clicking a folder, we use commands like `cd`. You can use:↵
↵
- `cd some_folder` to go to a folder called `some_folder` located in the current folder.↵
- `cd ..` to go to the parent folder.↵
- `pwd` (in Linux/Mac) or `cd` without any extra stuff (in Windows) to print the folder it is currently in.↵
↵
The first task is to use these commands to find the folder you saved your file in.↵
Since I don't know where you saved it, you're going to have to find it on your own.↵
↵
What happens when you press that "Run" button in your IDE is actually two things.↵
↵
- First, your code will be compiled from human-readable code into a magic binary↵
file that the computer knows how to execute.↵
- Second, the computer will run that binary file. ↵
↵
If you are using Windows, you might first need to install a C++ compiler. A version of GCC is bundled↵
in MinGW. It is a bit cumbersome to install it, but there are many good guides online. After that,↵
you can type `g++` like the rest of us. In Linux and Mac, GCC is already installed (on Mac, it's actually↵
clang, but that's not important right now).↵
↵
In modern IDEs the difference between these steps can be very blurry and also,↵
it's not like that for every programming language.↵
On the command line however, you have to understand that these two things are separate↵
steps, and you have to run them separately. First, the compilation. Type↵
↵
~~~~~↵
g++ program.cpp -o program↵
~~~~~↵
↵
This tells another program, called `g++` (the real name is GNU Compiler Collection, g++ is↵
just a shorthand to run it in the console for C++) to compile the file `program.cpp` into a binary↵
and save it as `program` (`-o` is for "output"). `program` will now be another file in the ↵
same folder. This file is one that the computer knows how to execute. To run your program,↵
you can now simply write `./program` (in Linux/Mac) or `program.exe` (in Windows).↵
I'm not going to write (or `program.exe` in Windows) every time, so if you're using Windows↵
just keep in mind that if I tell you to write `./program`, you should write `program.exe`.↵
↵
The `./` can be confusing. On Linux/Mac, when you run a program that is in the same folder as↵
you are, you have to add that `./`. There is a good reason, but I can't get into it right now,↵
so I'll just say that this is just how it is.↵
↵
Now, you can type in the two numbers, press enter, and it will print their sum.↵
↵
There are a couple things to note here. Since compiling and running are separate steps, you should↵
know that:↵
↵
- If you want to run the same program multiple times, for example to test it with multiple different↵
inputs, there is no need to compile it twice.↵
- However, if you modified the code, you also need to compile it again for the changes to take ↵
effect.↵
↵
Finally, in case you get stuck in an infinite loop, Ctrl-C will stop the program.↵
↵
↵
↵
##### Simple testing↵
↵
Once you have written and compiled your code, it is now time to test it, at least on sample tests.↵
↵
Many beginners do it like this. They click the "run" button on their IDE, then a black box opens.↵
They write the test case to the box manually. This is very error-prone and very time-consuming if ↵
your program has a lot of bugs and you have to run and edit it many times before it works.↵
↵
There are other problems with this approach as well. On some IDEs, the black box immediately↵
disappears once the code has run, which means you haven't got the time to check whether the output ↵
is correct. The correct approach here is to figure out how to change the IDE settings so it doesn't ↵
do that, but a lot of students instead apply hacks such as adding `int trash; cin >> trash` to the ↵
end of their code so that it will wait for input and not close immediately. Of course, this means↵
that you have to change the code to submit it, which you will forget to do, thus you get a "Wrong↵
answer" or "Idleness limit exceeded" verdict.↵
↵
In local olympiads, we have discovered that many new-ish students have completely given up testing ↵
their code locally, including testing on sample tests, because of such difficulties. Of course,↵
this has a direct and dire effect on their contest performance.↵
↵
The better approach is to read input from files, but now you have a new problem: how do I make↵
my program read input from files locally but from standard input in the judging system. The↵
wrong solution students come up with is writing their code to read from files and then ↵
changing it before submitting. A slightly less wrong solution is to use `#ifdef`, but then ↵
you have to figure out how to compile the code in a special way.↵
↵
There is a better way! We have already learned how to compile the file `program.cpp` into↵
an executable called `program`, and how to run it using `./program`. Now, make an input file↵
called `input.txt` and paste the test case in there. Put it in the same folder as the file↵
`program`. For example:↵
↵
<spoiler summary="input.txt">↵
~~~~~↵
3 7↵
~~~~~↵
</spoiler>↵
↵
Now, from the command line, run the following:↵
↵
~~~~~↵
./program < input.txt↵
~~~~~↵
↵
The `<` here is the key. It tells the computer to forward the contents of `input.txt`↵
into the standard input, as if you manually entered `3 7`. With any luck, you should see `10`↵
on the screen.↵
↵
Similarly, you can write↵
↵
~~~~~↵
./program > output.txt↵
~~~~~↵
↵
Now, you have to manually write the input, but the output will be written not to the screen, ↵
but to a file called `output.txt`. If the file does not exist, it creates it; if it does exist,↵
it will be overwritten.↵
↵
You can even combine the two as such.↵
↵
~~~~~↵
./program < input.txt > output.txt↵
~~~~~↵
↵
And of course, you can replace `input.txt` and `output.txt` with any file names you choose.↵
↵
This will be useful later, in the "stress testing" section.↵
↵
↵
↵
##### Stress testing↵
↵
Suppose you get a "Wrong answer" or "Runtime error" verdict. What will you do?↵
Well, the first step is usually to just look at the code and try to spot obvious↵
mistakes. But it will happen, and it will happen often, that you get stuck.↵
What do you do then? ↵
↵
The first thing to do is to reproduce the error; find an actual test case↵
where your program fails. Then you can debug the code, to find out where it does↵
the wrong thing. This method is very effective for finding mistakes in your↵
implementation, but also to find out that your idea was wrong and exactly why↵
your idea was wrong.↵
↵
Sometimes you can find such a test case simply by manually testing some case↵
that might be suspicious. Sometimes, you can download the test cases for the problem,↵
for example AtCoder and many olympiads publish all test cases after the contest.↵
But this doesn't help you during a contest; also it may happen that the test case↵
you failed at is very large, which you effectively can't manually debug.↵
↵
There is a better way! Many of you have seen this comment of mine:↵
↵
> Have you tried the following:↵
>↵
> - Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)↵
> - Write a program to generate thousands of small (!) test cases↵
> - Using those two, find a test case where your program gives the wrong answer↵
> - Use print statements or a debugger to see where exactly your program does the wrong thing.↵
↵
**The problem.** Now, we are going to learn how. First of all, we need a problem to solve, because↵
I don't think anyone is going to make a mistake on the A + B problem we were solving ↵
before. So, let's look at [CSES 1090 — Ferris Wheel](https://cses.fi/problemset/task/1090/)↵
(thanks [user:de_sousa,2022-04-22] for suggesting it!).↵
↵
Someone might come up with the following solution:↵
↵
> Sort the children from lightest to heaviest and process them in that order.↵
> If a child is too heavy to fit in the current gondola, send that gondola↵
> on its way and take a new one. Otherwise, just add the child to the↵
> current gondola.↵
↵
I have implemented it here. Save it as `ferris.cpp` and compile it as usual↵
to `ferris`.↵
↵
<spoiler summary="ferris.cpp">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int main () {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int n, max_gondola_weight;↵
cin >> n >> max_gondola_weight;↵
↵
vector<int> children (n);↵
for (int i = 0; i < n; i++) {↵
cin >> children[i];↵
}↵
↵
// interesting part starts here↵
sort(children.begin(), children.end());↵
int gondolas_used = 1, current_gondola_weight = 0;↵
for (int child : children) {↵
if (current_gondola_weight + child > max_gondola_weight) {↵
// the new child can not be added to the current↵
// gondola. start a new gondola.↵
gondolas_used++;↵
current_gondola_weight = child;↵
} else {↵
// add the child to the current gondola↵
current_gondola_weight += child;↵
}↵
}↵
↵
cout << gondolas_used << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
If you submit it, you will see that it gets WA on 7 of the 12 tests. Now you might wonder↵
whether you've made a mistake in implementation or if the idea is wrong altogether.↵
To do so, it is best to look at an actual test. Now, on CSES you can actually view the↵
failing test, and there are some small ones, but let's ignore this for the purposes of↵
demonstration, because a lot of the time, this isn't going to be the case. Instead,↵
we are going to find a failing test case by stress testing.↵
↵
**The naive solution.** Now, let's look at, line by line, the instructions. The first line is:↵
↵
> - Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)↵
↵
We can't copy someone else's solution on CSES, so we are going to have to write one ourselves.↵
How should we go about it? Here are a few guidelines.↵
↵
- It doesn't matter how fast or slow this naive and simple solution is. You're only going to run it on small test cases.↵
- It is best to make this as simple as possible, using as little logic as possible. Make it so simple it can't be wrong.↵
↵
For this problem, here's an idea. Instead of sorting the list of children, let's try all possible↵
orderings. One of them has got to be right: if you visualize an optimal solution, we can put the↵
gondolas in a line and read the children in this order, then that will be an order for the children.↵
It might be that our solution would put some children in earlier gondolas, but that can't increase↵
the number of gondolas, and it can't decrease either because the set of gondolas is optimal.↵
↵
I have implemented it here. Save it as `ferris_naive.cpp` and compile as usual to get↵
`ferris_naive`.↵
↵
<spoiler summary="ferris_naive.cpp">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int main () {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int n, max_gondola_weight;↵
cin >> n >> max_gondola_weight;↵
↵
vector<int> children (n);↵
for (int i = 0; i < n; i++) {↵
cin >> children[i];↵
}↵
↵
// interesting part starts here ↵
int best = n; // it's always possible to put each child in their own gondola↵
↵
// start with the sorted order, and try all possible orders from there↵
sort(children.begin(), children.end());↵
↵
// do ... while (next_permutation) goes through all the orders of the children↵
do {↵
int gondolas_used = 1, current_gondola_weight = 0;↵
for (int child : children) {↵
if (current_gondola_weight + child > max_gondola_weight) {↵
// the new child can not be added to the current↵
// gondola. start a new gondola.↵
gondolas_used++;↵
current_gondola_weight = child;↵
} else {↵
// add the child to the current gondola↵
current_gondola_weight += child;↵
}↵
}↵
best = min(best, gondolas_used);↵
} while (next_permutation(children.begin(), children.end()));↵
↵
cout << best << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
It's a bit suspicious that I reused some code from earlier, but if the idea↵
is wrong, we will still find a countertest.↵
↵
**The generator.** The second line:↵
↵
> - Write a program to generate thousands of small (!) test cases↵
↵
The way to do this is to write a program that generates one random test case. ↵
Some guidelines again:↵
↵
- This code can be very quick-and-dirty. During a contest, you shouldn't spend↵
time polishing things like that. Whip it out as quickly as you can.↵
- The generator doesn't need to generate any possible test with equal probability↵
or anything like that. All you need is a program that could reasonably well↵
produce any valid small test case.↵
- As a consequence, even though [rand is evil](61587), it's totally fine to use ↵
`rand()` here to generate random numbers. ↵
- It's a good idea to take the random seed from an argument and not set it by↵
time, so you can easily regenerate a test if you need to.↵
↵
I have implemented a simple generator for the Ferris Wheel problem here. Save it↵
as `ferris_gen.cpp` and compile as usual to produce `ferris_gen`.↵
↵
<spoiler summary="ferris_gen.cpp">↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
↵
int main (int argc, char **argv) {↵
// argv is an array of strings↵
// atoi is a C function for converting a string into an int↵
↵
srand(atoi(argv[1])); // srand sets the random seed↵
int n = atoi(argv[2]);↵
int x = atoi(argv[3]);↵
↵
cout << n << " " << x << endl;↵
for (int i = 0; i < n; i++) {↵
cout << 1 + rand() % x << " ";↵
}↵
cout << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
The code is pretty self-explanatory; the main question you might have is ↵
"what are `argc` and `argv`"? Another brilliant feature of the command line!↵
Once I have compiled the code, I can run it from the command line as such:↵
`./ferris_gen 5 3 8`. The stuff after the program name are its arguments,↵
and they can be accessed through `argc` and `argv`. `argc` is the number of↵
arguments; in this case, 4. `argv` is the list of arguments. In this case,↵
`argv` will be an array containing `["./ferris_gen", "5", "3", "8"]`. ↵
This allows me to change the random seed or input size without changing↵
the code or reading it from input. ↵
↵
**The script.** Now, the third line. ↵
↵
> - Using those two, find a test case where your program gives the wrong answer↵
↵
Now, how do we combine our three programs to actually find a failing test case?↵
There is one more important part of the command line that we have to talk about:↵
_scripting_. You don't have to type everything into the command line manually.↵
It is possible to save lists of commands as _scripts_. When you execute one,↵
it will run all these commands sequentially. Scripts also support familiar ↵
features of programming languages such as ifs and loops, so you can write little↵
programs this way.↵
↵
Our task is now to generate thousands of test files, run both the naive and the↵
correct solution on them. To do it, I have written a script file. ↵
↵
For Linux/Mac: save the following as `script.sh`↵
↵
~~~~~↵
for i in `seq 1 100`; do↵
# prints the current test number↵
# I like to do this so I can see progress is being made↵
echo $i ↵
↵
./ferris_gen $i 4 5 > input.txt↵
./ferris < input.txt > output.txt↵
./ferris_naive < input.txt > answer.txt↵
↵
diff output.txt answer.txt || break↵
done↵
~~~~~↵
↵
For Windows: save the following as `script.bat`↵
↵
~~~~~↵
@echo off↵
↵
for /l %%i in (1, 1, 100) do (↵
echo %%i↵
↵
ferris_gen.exe %%i 4 5 > input.txt↵
ferris.exe < input.txt > output.txt↵
ferris_naive.exe < input.txt > answer.txt↵
↵
fc output.txt answer.txt || goto :out↵
)↵
↵
:out↵
~~~~~↵
↵
The syntax is weird, but it is essentially a for-loop. How those lines in ↵
the middle work has been discussed already: ↵
↵
- use `ferris_gen` to generate a test case, forward it to `input.txt`,↵
- run `ferris` with the input in `input.txt`, save the output to `output.txt`,↵
- do the same for `ferris_naive`, save the output to `answer.txt` this time.↵
↵
All that's left to do is to check if `output.txt` and `answer.txt` are the same.↵
`diff` (`fc` in Windows) is a command that does that. If the files don't match, it will print the mismatched↵
lines and exit with a nonzero exit code. The part after `||` is executed only then, ↵
and it is just a break. ↵
↵
If this code breaks early, the script has found a test case where the naive and wrong↵
solution disagree. It will be available in `input.txt`. Otherwise, it found no ↵
countertest. In this case, try varying the input size parameters, or run it on more cases.↵
↵
On Linux/Mac, to run the test, you first need to give yourself permissions to run it; to do that,↵
use ↵
↵
~~~~~↵
chmod +x script.sh↵
~~~~~↵
↵
And finally you can run it as: `./script.sh` (Linux/Mac) or `script.bat` (Windows).↵
↵
In my case, it found a countertest on the very first try:↵
↵
~~~~~↵
4 5↵
4 2 3 1 ↵
~~~~~↵
↵
Indeed, the greedy solution will sort them and come up with this partition:↵
$\\{\\{1, 2\\}, \\{3\\}, \\{4\\}\\}$. But there is a better way: ↵
$\\{\\{1, 4\\}, \\{2, 3\\}\\}$. We have identified, that the greedy idea↵
is probably wrong or incomplete. It's now time to rethink the solution.↵
↵
Once someone told me "I already have little time to practice and now↵
you're telling me to write MORE code? What's WRONG with you?" after I explained↵
this. In reality, writing these extra bits of code will only take a few minutes↵
if you can code fluently, while trying to debug code without an actual case↵
can take hours. Yes, I actually use this method regularly during contests.↵
↵
↵
↵
##### Measuring time taken↵
↵
Sometimes, you need to know exactly how much time your program took.↵
Maybe you're not sure whether it will TLE or barely pass. Maybe you're↵
optimizing the constant and need to know if you're on the right track.↵
↵
Something people will do is measuring the time taken in the code:↵
↵
~~~~~↵
int main () {↵
auto start = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();↵
// insert awesome algorithm here↵
auto stop = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();↵
cerr << "Took " << stop - start << "ms" << endl;↵
}↵
~~~~~↵
↵
There is a simpler way! On Linux/Mac, from the command line, you can simply write↵
↵
~~~~~↵
time ./program < input.txt↵
~~~~~↵
↵
I don't know how to do this on Windows.↵
↵
The `time` command will run everything after it as normal, and report the time taken.↵
Now, this doesn't make in-code time measuring completely pointless, especially if you want↵
something more fine-grained such as measuring how much each step took, but a lot of the time↵
it is unnecessary, and the `time` command will do just fine.↵
↵
↵
↵
##### Testing interactive problems↵
↵
Testing interactive problems is hard. One way is to manually type inputs,↵
which can be fine, except a lot of the times it isn't. One way is to write↵
your own (simple) interactor to see if your code works properly. Now ↵
you have the problem: how do I make the two processes communicate with↵
one another?↵
↵
There are ways to do it with "pure" command line (with `mkfifo` and so on),↵
but I think it is simplest to just use Google Code Jam's tool, which I↵
have linked [here](https://pastebin.com/bGCz3QA2). Now that you know↵
how to run programs from the command line, it should be simple to run this↵
one to test your program. You can simply write↵
↵
~~~~~↵
python3 interactive_runner.py ./judge -- ./solution↵
~~~~~↵
↵
#### Using the command line in code editors↵
↵
So, am I telling you to stop using any modern code editing tools, going back↵
to the 80s? No! People who create IDEs are generally aware of how useful the↵
command line is and have provided ways to access it. ↵
↵
##### GNU Emacs↵
↵
By `M-x ansi-term`. Or, in normal people' language, by typing Alt-X, then "ansi-term", then enter.↵
↵
##### Visual Studio Code↵
↵
By using "Terminal" in the top menu:↵
↵
↵
↵
##### Sublime Text↵
↵
By installing the Terminus extension.
↵
Instead of algorithms and math, I'll be doing something completely different here.↵
There is something that has bothered me for a long time: people not understanding↵
the tools they use to participate in contests and thus failing to take real advantage↵
of them. And it all goes back to not understanding the command line.↵
↵
Some of you might say, "well surely, the command line is something obsolete and you're ↵
only clinging to it because you [insert ridiculous amateur-psychology here]?"↵
No! The command line is not obsolete, and unless competitive programming becomes↵
so mainstream that software vendors start writing professional-grade tools aimed↵
specifically at us, it won't be.↵
↵
[cut]↵
$~$↵
↵
What is the command line? Any of these:↵
↵
↵
↵
As you can see, it comes in many background colors and fonts, but the basic idea↵
is always the same. It's a box you can type commands in, which it will then execute.↵
↵
Why use the command line?↵
↵
- **Flexible and very powerful.** In competitive programming, there are a number of↵
tasks you have to do to work with your code locally: compiling, running, testing,↵
stress testing and so on. Modern IDEs have tools for these, but they are not really↵
designed with us in mind. Many people have written extensions to do these things↵
comfortably, but what if you need to do something slightly different, something ↵
the extension author had not anticipated? You get stuck and have to make-do with↵
some stupid hack. The command line allows you to do all those things, however you↵
want to. It's very possible that just by changing a few small things will allow↵
you to do what the extension author had not anticipated.↵
- **Submit exactly what you wrote.** A very basic thing in competitive programming↵
that you have to do is test your program, at least on the sample tests. The first thing↵
that beginners usually do is they press the "run" button in their IDE and manually type the↵
test case into the black box that appears. This is very error-prone and very time-consuming.↵
A better way would be to read the input from a file, but now what you submit will be different↵
from what you test locally. People will often tell you to use something called an "ifdef",↵
but that also has its issues, see below.↵
- **Interactive problems.** Some contests such as Google Code Jam offer a testing tool for ↵
interactive problems; IOI also offers various tools to test problems. If you have never ↵
learned the command line, you'll probably have to think for a while about how to run this. ↵
With the command line, it is dead simple.↵
- **Deeper understanding.** Understanding the command line means understanding how everything↵
your IDE does actually works. Then you are also in a better position to customize your ↵
IDE if you choose to continue using it. I mentioned testing tools for interactive problems↵
above. Usually, you have to pass your program as an argument to them. If you have↵
always relied on an IDE to run your code, you might not even grasp the concept↵
of an "executable" and getting this interaction tool to run will be an impossible task.↵
I've had to teach this stuff to people who were otherwise relatively proficient in competitive↵
programming.↵
- **Full control.** The command line offers you the most fundamental level of control↵
over what's actually happening in your computer.↵
↵
**Update 11.09.2022** More generally still, I've noticed that people often learn the bare minimum when it comes to↵
being able to edit and run programs locally. They find one configuration or setup that works by↵
trial and error and stick with that, even though when you look into it, it may be a ridiculously↵
convoluted Rube Goldberg machine. This will work until the situation slightly changes, and then you're stuck.↵
↵
The recent example that prompted me to write this comes from Meta Hacker Cup. There, you have to run the program locally on your computer within a 6-minute window, on a test file that may be quite large (let's say, 60 MB). For a number of people, the workflow included _opening these files_ and _copy-pasting their content somewhere else_. With files this size, it is quite impractical and can easily crash editing programs that are not optimized for large files (regardless of the speed of your computer). ↵
↵
Learning the command line means learning how your computer works. Understanding this stuff means that you can take advantage of it and streamline your setup for testing locally.↵
↵
##### About editors and IDEs↵
↵
As far as text editors go and what I've seen people use to write code, there are basically four categories.↵
↵
1. Classical text editors. Examples: Emacs, vi, gedit, nano, Far Manager, Notepad.↵
2. Lightweight modern code editors. Examples: Visual Studio Code, Sublime Text.↵
3. Full-fledged IDEs. Examples: Visual Studio, CLion, Xcode.↵
4. Code::Blocks.↵
↵
This is obviously not some objective classification, and the lines between the categories↵
get _very_ blurry, but I hope on an intuitive level you understand what I mean.↵
↵
My advice: don't use items in category 3 for competitive programming and don't use items ↵
in category 4 for anything. Full-fledged IDEs are meant to be used for medium-to-large ↵
software projects and are designed with that in mind. They want you to create a Solution and then a↵
Project, then set up a Build Configuration and so on. This is all very good and important↵
if you are maintaining a real software project with hundreds of classes and nontrivial↵
build sequences, but utterly pointless if all your programs are in a single file, which ↵
is what you have to do in competitive programming. Many people copy-paste their code ↵
into the box on CF simply because amid all this complexity, they have no idea where their ↵
.cpp file actually is.↵
↵
Moreover, although they are very powerful, you won't use any of this power. But you still↵
have to pay for that power by having to deal with long loading times if you have a weakish↵
computer, and using a lot of RAM. ↵
↵
Lightweight code editors, on the other hand, are great. They provide some of the simpler ↵
utilities of full IDEs, such as a "rename this variable" function, without introducing↵
all the bloat of full IDEs. In addition, they usually provide easy access to the command↵
line, giving you all the benefits I mentioned above.↵
↵
The moral of the story is that you should use appropriate tools for different tasks.↵
Software engineering very different from competitive programming, and require different↵
tools. I use GNU Emacs for competitive programming and JetBrains Rider at work, and I would↵
never want to do it the other way around.↵
↵
#### Basic tasks using the command line↵
↵
This section is organized as a "lab". If you are new to the command line and want to learn it,↵
I recommend doing everything I tell here. Of course, this is more of a tutorial on "how to ↵
do essential tasks for competitive programming", not a comprehensive tutorial on how to use↵
it in general. But I will go through other necessary commands anyway.↵
↵
##### Setup↵
↵
For this "lab", I suggest using the simplest possible program to code. Forget your good↵
IDE for a bit to avoid any temptations. Don't worry, later we will come back to the↵
fancy editors and using the command line there.↵
↵
The first step is actually opening the command line. ↵
↵
- On Windows, open the Start menu and search for "cmd.exe".↵
- On Mac, open the Finder and search for "Terminal".↵
- On Linux, it depends on your distribution, but you can usually find it by opening some kind of menu and searching for "Terminal". But if you use Linux, you probably already know.↵
↵
Windows actually has two kinds of terminals: cmd.exe and PowerShell. Both have their ups and downs, but↵
the commands are different. In this blog, I will provide commands for cmd.exe but not PowerShell.↵
↵
Once you have got it open, type `ls` (Linux/Mac) or `dir` (Windows) and press Enter. ↵
You should see a list of files and folders located in the folder you're currently in.↵
↵
##### Compiling and running your code↵
↵
I'll be assuming you work with C++, since that is the most common scenario in competitive programming.↵
First, we shall write a program. Of course, you already know how to do this, so there is no point↵
in lingering about it.↵
↵
I've written a program. Save it as `program.cpp`.↵
↵
<spoiler summary="program.cpp">↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
↵
int main () {↵
int a, b;↵
cin >> a >> b;↵
↵
cout << a + b << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
Now, we need to compile and run it. The first step is to actually locate the file in the↵
command line. In some ways, the command line is a lot like a file browser on your computer:↵
↵
↵
↵
At any given time, it is in a certain folder, and you can navigate to other folders.↵
But instead of double-clicking a folder, we use commands like `cd`. You can use:↵
↵
- `cd some_folder` to go to a folder called `some_folder` located in the current folder.↵
- `cd ..` to go to the parent folder.↵
- `pwd` (in Linux/Mac) or `cd` without any extra stuff (in Windows) to print the folder it is currently in.↵
↵
The first task is to use these commands to find the folder you saved your file in.↵
Since I don't know where you saved it, you're going to have to find it on your own.↵
↵
What happens when you press that "Run" button in your IDE is actually two things.↵
↵
- First, your code will be compiled from human-readable code into a magic binary↵
file that the computer knows how to execute.↵
- Second, the computer will run that binary file. ↵
↵
If you are using Windows, you might first need to install a C++ compiler. A version of GCC is bundled↵
in MinGW. It is a bit cumbersome to install it, but there are many good guides online. After that,↵
you can type `g++` like the rest of us. In Linux and Mac, GCC is already installed (on Mac, it's actually↵
clang, but that's not important right now).↵
↵
In modern IDEs the difference between these steps can be very blurry and also,↵
it's not like that for every programming language.↵
On the command line however, you have to understand that these two things are separate↵
steps, and you have to run them separately. First, the compilation. Type↵
↵
~~~~~↵
g++ program.cpp -o program↵
~~~~~↵
↵
This tells another program, called `g++` (the real name is GNU Compiler Collection, g++ is↵
just a shorthand to run it in the console for C++) to compile the file `program.cpp` into a binary↵
and save it as `program` (`-o` is for "output"). `program` will now be another file in the ↵
same folder. This file is one that the computer knows how to execute. To run your program,↵
you can now simply write `./program` (in Linux/Mac) or `program.exe` (in Windows).↵
I'm not going to write (or `program.exe` in Windows) every time, so if you're using Windows↵
just keep in mind that if I tell you to write `./program`, you should write `program.exe`.↵
↵
The `./` can be confusing. On Linux/Mac, when you run a program that is in the same folder as↵
you are, you have to add that `./`. There is a good reason, but I can't get into it right now,↵
so I'll just say that this is just how it is.↵
↵
Now, you can type in the two numbers, press enter, and it will print their sum.↵
↵
There are a couple things to note here. Since compiling and running are separate steps, you should↵
know that:↵
↵
- If you want to run the same program multiple times, for example to test it with multiple different↵
inputs, there is no need to compile it twice.↵
- However, if you modified the code, you also need to compile it again for the changes to take ↵
effect.↵
↵
Finally, in case you get stuck in an infinite loop, Ctrl-C will stop the program.↵
↵
↵
↵
##### Simple testing↵
↵
Once you have written and compiled your code, it is now time to test it, at least on sample tests.↵
↵
Many beginners do it like this. They click the "run" button on their IDE, then a black box opens.↵
They write the test case to the box manually. This is very error-prone and very time-consuming if ↵
your program has a lot of bugs and you have to run and edit it many times before it works.↵
↵
There are other problems with this approach as well. On some IDEs, the black box immediately↵
disappears once the code has run, which means you haven't got the time to check whether the output ↵
is correct. The correct approach here is to figure out how to change the IDE settings so it doesn't ↵
do that, but a lot of students instead apply hacks such as adding `int trash; cin >> trash` to the ↵
end of their code so that it will wait for input and not close immediately. Of course, this means↵
that you have to change the code to submit it, which you will forget to do, thus you get a "Wrong↵
answer" or "Idleness limit exceeded" verdict.↵
↵
In local olympiads, we have discovered that many new-ish students have completely given up testing ↵
their code locally, including testing on sample tests, because of such difficulties. Of course,↵
this has a direct and dire effect on their contest performance.↵
↵
The better approach is to read input from files, but now you have a new problem: how do I make↵
my program read input from files locally but from standard input in the judging system. The↵
wrong solution students come up with is writing their code to read from files and then ↵
changing it before submitting. A slightly less wrong solution is to use `#ifdef`, but then ↵
you have to figure out how to compile the code in a special way.↵
↵
There is a better way! We have already learned how to compile the file `program.cpp` into↵
an executable called `program`, and how to run it using `./program`. Now, make an input file↵
called `input.txt` and paste the test case in there. Put it in the same folder as the file↵
`program`. For example:↵
↵
<spoiler summary="input.txt">↵
~~~~~↵
3 7↵
~~~~~↵
</spoiler>↵
↵
Now, from the command line, run the following:↵
↵
~~~~~↵
./program < input.txt↵
~~~~~↵
↵
The `<` here is the key. It tells the computer to forward the contents of `input.txt`↵
into the standard input, as if you manually entered `3 7`. With any luck, you should see `10`↵
on the screen.↵
↵
Similarly, you can write↵
↵
~~~~~↵
./program > output.txt↵
~~~~~↵
↵
Now, you have to manually write the input, but the output will be written not to the screen, ↵
but to a file called `output.txt`. If the file does not exist, it creates it; if it does exist,↵
it will be overwritten.↵
↵
You can even combine the two as such.↵
↵
~~~~~↵
./program < input.txt > output.txt↵
~~~~~↵
↵
And of course, you can replace `input.txt` and `output.txt` with any file names you choose.↵
↵
This will be useful later, in the "stress testing" section.↵
↵
↵
↵
##### Stress testing↵
↵
Suppose you get a "Wrong answer" or "Runtime error" verdict. What will you do?↵
Well, the first step is usually to just look at the code and try to spot obvious↵
mistakes. But it will happen, and it will happen often, that you get stuck.↵
What do you do then? ↵
↵
The first thing to do is to reproduce the error; find an actual test case↵
where your program fails. Then you can debug the code, to find out where it does↵
the wrong thing. This method is very effective for finding mistakes in your↵
implementation, but also to find out that your idea was wrong and exactly why↵
your idea was wrong.↵
↵
Sometimes you can find such a test case simply by manually testing some case↵
that might be suspicious. Sometimes, you can download the test cases for the problem,↵
for example AtCoder and many olympiads publish all test cases after the contest.↵
But this doesn't help you during a contest; also it may happen that the test case↵
you failed at is very large, which you effectively can't manually debug.↵
↵
There is a better way! Many of you have seen this comment of mine:↵
↵
> Have you tried the following:↵
>↵
> - Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)↵
> - Write a program to generate thousands of small (!) test cases↵
> - Using those two, find a test case where your program gives the wrong answer↵
> - Use print statements or a debugger to see where exactly your program does the wrong thing.↵
↵
**The problem.** Now, we are going to learn how. First of all, we need a problem to solve, because↵
I don't think anyone is going to make a mistake on the A + B problem we were solving ↵
before. So, let's look at [CSES 1090 — Ferris Wheel](https://cses.fi/problemset/task/1090/)↵
(thanks [user:de_sousa,2022-04-22] for suggesting it!).↵
↵
Someone might come up with the following solution:↵
↵
> Sort the children from lightest to heaviest and process them in that order.↵
> If a child is too heavy to fit in the current gondola, send that gondola↵
> on its way and take a new one. Otherwise, just add the child to the↵
> current gondola.↵
↵
I have implemented it here. Save it as `ferris.cpp` and compile it as usual↵
to `ferris`.↵
↵
<spoiler summary="ferris.cpp">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int main () {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int n, max_gondola_weight;↵
cin >> n >> max_gondola_weight;↵
↵
vector<int> children (n);↵
for (int i = 0; i < n; i++) {↵
cin >> children[i];↵
}↵
↵
// interesting part starts here↵
sort(children.begin(), children.end());↵
int gondolas_used = 1, current_gondola_weight = 0;↵
for (int child : children) {↵
if (current_gondola_weight + child > max_gondola_weight) {↵
// the new child can not be added to the current↵
// gondola. start a new gondola.↵
gondolas_used++;↵
current_gondola_weight = child;↵
} else {↵
// add the child to the current gondola↵
current_gondola_weight += child;↵
}↵
}↵
↵
cout << gondolas_used << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
If you submit it, you will see that it gets WA on 7 of the 12 tests. Now you might wonder↵
whether you've made a mistake in implementation or if the idea is wrong altogether.↵
To do so, it is best to look at an actual test. Now, on CSES you can actually view the↵
failing test, and there are some small ones, but let's ignore this for the purposes of↵
demonstration, because a lot of the time, this isn't going to be the case. Instead,↵
we are going to find a failing test case by stress testing.↵
↵
**The naive solution.** Now, let's look at, line by line, the instructions. The first line is:↵
↵
> - Write a very naive and simple solution to the problem (maybe exponential complexity) (if you can, you may also just copy someone else's solution)↵
↵
We can't copy someone else's solution on CSES, so we are going to have to write one ourselves.↵
How should we go about it? Here are a few guidelines.↵
↵
- It doesn't matter how fast or slow this naive and simple solution is. You're only going to run it on small test cases.↵
- It is best to make this as simple as possible, using as little logic as possible. Make it so simple it can't be wrong.↵
↵
For this problem, here's an idea. Instead of sorting the list of children, let's try all possible↵
orderings. One of them has got to be right: if you visualize an optimal solution, we can put the↵
gondolas in a line and read the children in this order, then that will be an order for the children.↵
It might be that our solution would put some children in earlier gondolas, but that can't increase↵
the number of gondolas, and it can't decrease either because the set of gondolas is optimal.↵
↵
I have implemented it here. Save it as `ferris_naive.cpp` and compile as usual to get↵
`ferris_naive`.↵
↵
<spoiler summary="ferris_naive.cpp">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int main () {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
↵
int n, max_gondola_weight;↵
cin >> n >> max_gondola_weight;↵
↵
vector<int> children (n);↵
for (int i = 0; i < n; i++) {↵
cin >> children[i];↵
}↵
↵
// interesting part starts here ↵
int best = n; // it's always possible to put each child in their own gondola↵
↵
// start with the sorted order, and try all possible orders from there↵
sort(children.begin(), children.end());↵
↵
// do ... while (next_permutation) goes through all the orders of the children↵
do {↵
int gondolas_used = 1, current_gondola_weight = 0;↵
for (int child : children) {↵
if (current_gondola_weight + child > max_gondola_weight) {↵
// the new child can not be added to the current↵
// gondola. start a new gondola.↵
gondolas_used++;↵
current_gondola_weight = child;↵
} else {↵
// add the child to the current gondola↵
current_gondola_weight += child;↵
}↵
}↵
best = min(best, gondolas_used);↵
} while (next_permutation(children.begin(), children.end()));↵
↵
cout << best << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
It's a bit suspicious that I reused some code from earlier, but if the idea↵
is wrong, we will still find a countertest.↵
↵
**The generator.** The second line:↵
↵
> - Write a program to generate thousands of small (!) test cases↵
↵
The way to do this is to write a program that generates one random test case. ↵
Some guidelines again:↵
↵
- This code can be very quick-and-dirty. During a contest, you shouldn't spend↵
time polishing things like that. Whip it out as quickly as you can.↵
- The generator doesn't need to generate any possible test with equal probability↵
or anything like that. All you need is a program that could reasonably well↵
produce any valid small test case.↵
- As a consequence, even though [rand is evil](61587), it's totally fine to use ↵
`rand()` here to generate random numbers. ↵
- It's a good idea to take the random seed from an argument and not set it by↵
time, so you can easily regenerate a test if you need to.↵
↵
I have implemented a simple generator for the Ferris Wheel problem here. Save it↵
as `ferris_gen.cpp` and compile as usual to produce `ferris_gen`.↵
↵
<spoiler summary="ferris_gen.cpp">↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
↵
int main (int argc, char **argv) {↵
// argv is an array of strings↵
// atoi is a C function for converting a string into an int↵
↵
srand(atoi(argv[1])); // srand sets the random seed↵
int n = atoi(argv[2]);↵
int x = atoi(argv[3]);↵
↵
cout << n << " " << x << endl;↵
for (int i = 0; i < n; i++) {↵
cout << 1 + rand() % x << " ";↵
}↵
cout << endl;↵
}↵
~~~~~↵
</spoiler>↵
↵
The code is pretty self-explanatory; the main question you might have is ↵
"what are `argc` and `argv`"? Another brilliant feature of the command line!↵
Once I have compiled the code, I can run it from the command line as such:↵
`./ferris_gen 5 3 8`. The stuff after the program name are its arguments,↵
and they can be accessed through `argc` and `argv`. `argc` is the number of↵
arguments; in this case, 4. `argv` is the list of arguments. In this case,↵
`argv` will be an array containing `["./ferris_gen", "5", "3", "8"]`. ↵
This allows me to change the random seed or input size without changing↵
the code or reading it from input. ↵
↵
**The script.** Now, the third line. ↵
↵
> - Using those two, find a test case where your program gives the wrong answer↵
↵
Now, how do we combine our three programs to actually find a failing test case?↵
There is one more important part of the command line that we have to talk about:↵
_scripting_. You don't have to type everything into the command line manually.↵
It is possible to save lists of commands as _scripts_. When you execute one,↵
it will run all these commands sequentially. Scripts also support familiar ↵
features of programming languages such as ifs and loops, so you can write little↵
programs this way.↵
↵
Our task is now to generate thousands of test files, run both the naive and the↵
correct solution on them. To do it, I have written a script file. ↵
↵
For Linux/Mac: save the following as `script.sh`↵
↵
~~~~~↵
for i in `seq 1 100`; do↵
# prints the current test number↵
# I like to do this so I can see progress is being made↵
echo $i ↵
↵
./ferris_gen $i 4 5 > input.txt↵
./ferris < input.txt > output.txt↵
./ferris_naive < input.txt > answer.txt↵
↵
diff output.txt answer.txt || break↵
done↵
~~~~~↵
↵
For Windows: save the following as `script.bat`↵
↵
~~~~~↵
@echo off↵
↵
for /l %%i in (1, 1, 100) do (↵
echo %%i↵
↵
ferris_gen.exe %%i 4 5 > input.txt↵
ferris.exe < input.txt > output.txt↵
ferris_naive.exe < input.txt > answer.txt↵
↵
fc output.txt answer.txt || goto :out↵
)↵
↵
:out↵
~~~~~↵
↵
The syntax is weird, but it is essentially a for-loop. How those lines in ↵
the middle work has been discussed already: ↵
↵
- use `ferris_gen` to generate a test case, forward it to `input.txt`,↵
- run `ferris` with the input in `input.txt`, save the output to `output.txt`,↵
- do the same for `ferris_naive`, save the output to `answer.txt` this time.↵
↵
All that's left to do is to check if `output.txt` and `answer.txt` are the same.↵
`diff` (`fc` in Windows) is a command that does that. If the files don't match, it will print the mismatched↵
lines and exit with a nonzero exit code. The part after `||` is executed only then, ↵
and it is just a break. ↵
↵
If this code breaks early, the script has found a test case where the naive and wrong↵
solution disagree. It will be available in `input.txt`. Otherwise, it found no ↵
countertest. In this case, try varying the input size parameters, or run it on more cases.↵
↵
On Linux/Mac, to run the test, you first need to give yourself permissions to run it; to do that,↵
use ↵
↵
~~~~~↵
chmod +x script.sh↵
~~~~~↵
↵
And finally you can run it as: `./script.sh` (Linux/Mac) or `script.bat` (Windows).↵
↵
In my case, it found a countertest on the very first try:↵
↵
~~~~~↵
4 5↵
4 2 3 1 ↵
~~~~~↵
↵
Indeed, the greedy solution will sort them and come up with this partition:↵
$\\{\\{1, 2\\}, \\{3\\}, \\{4\\}\\}$. But there is a better way: ↵
$\\{\\{1, 4\\}, \\{2, 3\\}\\}$. We have identified, that the greedy idea↵
is probably wrong or incomplete. It's now time to rethink the solution.↵
↵
Once someone told me "I already have little time to practice and now↵
you're telling me to write MORE code? What's WRONG with you?" after I explained↵
this. In reality, writing these extra bits of code will only take a few minutes↵
if you can code fluently, while trying to debug code without an actual case↵
can take hours. Yes, I actually use this method regularly during contests.↵
↵
↵
↵
##### Measuring time taken↵
↵
Sometimes, you need to know exactly how much time your program took.↵
Maybe you're not sure whether it will TLE or barely pass. Maybe you're↵
optimizing the constant and need to know if you're on the right track.↵
↵
Something people will do is measuring the time taken in the code:↵
↵
~~~~~↵
int main () {↵
auto start = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();↵
// insert awesome algorithm here↵
auto stop = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();↵
cerr << "Took " << stop - start << "ms" << endl;↵
}↵
~~~~~↵
↵
There is a simpler way! On Linux/Mac, from the command line, you can simply write↵
↵
~~~~~↵
time ./program < input.txt↵
~~~~~↵
↵
I don't know how to do this on Windows.↵
↵
The `time` command will run everything after it as normal, and report the time taken.↵
Now, this doesn't make in-code time measuring completely pointless, especially if you want↵
something more fine-grained such as measuring how much each step took, but a lot of the time↵
it is unnecessary, and the `time` command will do just fine.↵
↵
↵
↵
##### Testing interactive problems↵
↵
Testing interactive problems is hard. One way is to manually type inputs,↵
which can be fine, except a lot of the times it isn't. One way is to write↵
your own (simple) interactor to see if your code works properly. Now ↵
you have the problem: how do I make the two processes communicate with↵
one another?↵
↵
There are ways to do it with "pure" command line (with `mkfifo` and so on),↵
but I think it is simplest to just use Google Code Jam's tool, which I↵
have linked [here](https://pastebin.com/bGCz3QA2). Now that you know↵
how to run programs from the command line, it should be simple to run this↵
one to test your program. You can simply write↵
↵
~~~~~↵
python3 interactive_runner.py ./judge -- ./solution↵
~~~~~↵
↵
#### Using the command line in code editors↵
↵
So, am I telling you to stop using any modern code editing tools, going back↵
to the 80s? No! People who create IDEs are generally aware of how useful the↵
command line is and have provided ways to access it. ↵
↵
##### GNU Emacs↵
↵
By `M-x ansi-term`. Or, in normal people' language, by typing Alt-X, then "ansi-term", then enter.↵
↵
##### Visual Studio Code↵
↵
By using "Terminal" in the top menu:↵
↵
↵
↵
##### Sublime Text↵
↵
By installing the Terminus extension.
