Meta Hacker Cup is upon us again. Along with it comes the unique format where we have to run our code on large test cases ourselves. Unfortunately, past experience shows that not everyone knows how to do this reliably. Usually, after the first round, many people lose points as a result of an unreliable workflow. This time, let's try to prevent that from happening. Sorry for the somewhat self-important title, but I really do wish that everyone understood this and that no one will fail the contest because of this.
Don't EVER copy-paste huge files
A lot of people's workflow to run a solution is the following:
- Click some green button in the IDE
- A box comes up, copy-paste the input into that box
- The output shows up somewhere
This may work well for running your solution on small sample test cases. It is terrible for running your solution on the huge test cases in Meta Hacker Cup. In last year's Round 1, the full test case for problem C was 37.5 megabytes in size and 6 million lines long. A 20 year old computer is very much capable of handling a file that large, but most graphical tools are not built with such files in mind.
I did an experiment. I opened my code for that problem in VS Code, compiled it and ran the program in VS Code's terminal. Then, I copy-pasted that 6 million line input file into that terminal. VS Code froze and I had to kill it. I'm fairly certain that this will happen on pretty much every consumer laptop. If you do this and your computer crashes, it's not because your laptop is old and slow, it's because you used a tool for something it wasn't designed for. Even if it doesn't crash, the clipboard itself has an upper limit on some systems. You shouldn't even need to open these files. Many text editors aren't designed for large files either and might crash; again, this is not because your computer is slow, it's because the tools aren't designed for large files.
Here's how you should be working with these files.
Option 1. Use pipes to read the input from a file and write the output to a file. For example, ./program < input.txt > output.txt reads the input from input.txt and writes it to output.txt. Read my blog on command line to learn more.
Option 2. Read the input from files directly. In your program, you can write
#include <fstream>
// ...
int main () {
ifstream fin ("input.txt");
ofstream fout ("output.txt");
}
Now, you can read from fin (e.g. fin >> n >> m) and write to fout (e.g. fout << "Case #" << i << ": " << ans << '\n').
Option 3. If you like Option 2, but cin and cout are burnt deeply into your muscle memory, you can do
#include <cstdio>
// ...
int main () {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
Now cin reads from input.txt and cout writes to output.txt.
Set a higher stack size
I've written a simple C++ program. It generates a random tree by selecting the parent of vertex $$$u$$$ to be in $$$[u - 6, u - 1]$$$. Then, it prints the depth of the last vertex. Here is the program.
code#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6;
vector<int> ch [N];
int depth [N];
void dfs (int u, int d) {
depth[u] = d;
for (int nxt : ch[u])
dfs(nxt, 1 + d);
}
int main () {
for (int i = 1; i < N; i++) {
int p = i - 1 - rand() % 5;
if (p < 0)
p = 0;
ch[p].push_back(i);
}
dfs(0, 0);
cout << depth[N - 1] << '\n';
}
Try running this on your computer; it doesn't take any input. With high probability, you'll see this message:
Segmentation fault (core dumped)
What is going on? Have I perhaps made some implementation mistake? No: the reason this code segfaults is that the recursion goes too deep. A slightly simplified explanation is that when you are calling a recursive function, the compiled program needs to remember all recursive calls that led to the current call, and it runs out of memory to write this information into. This issue commonly comes up if there is, for example, a graph problem where you need to write DFS.
Option 1. (Linux and probably Mac OS, only if running command line) Type ulimit -s unlimited into the terminal before running your solution in the same terminal.
Option 2. (All platforms) Follow the instructions here.
Compile with -O2
-O2 is a flag given to the compiler that enables certain optimizations. You might not be aware of it, but every submission you submit to Codeforces or any other online judge is compiled with that flag. If the input files are large, you probably want to compile with this as well, otherwise your solution will run rather slowly.
If you compile from the command line, you can just do g++ -O2 solution.cpp -o solution. If you compile using some button in your IDE, it depends on your IDE, but you should be able to add this flag from some menu. Here's how to do it on some common tools. Please note that there are all kinds of setups and if you are doing something different, you probably need to do these things differently as well. If you use some tools, you should in general be well-versed in how to use and configure these tools.
Code::BlocksSelect "Settings" from the menu on top and choose "Compiler...". Enable "[-O2]" under Optimization.
CLionChoose "Edit Configurations".
Add -O2 to "compiler options".
CP EditorSelect "Options" from the menu on the top and choose "Preferences". Select "C++ Compile and Run Commands". Add -O2 to "C++ Compile Command" and click Apply.
Sublime TextSelect "Preferences" from the menu on the top and choose "Browse packages". A folder will open. Navigate to the subfolder called "User" and create a file called "C++ Single File with -O2.sublime-build". Paste in the following configuration:
{
"shell_cmd": "g++ \"$$${file}\" -O2 -o \"$$${file_path}/${file_base_name}\"",
"file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
"working_dir": "${file_path}",
"selector": "source.c++",
"variants":
[
{
"name": "Run",
"shell_cmd": "g++ \"$$${file}\" -O2 -o \"$$${file_path}/$$${file_base_name}\" && \"$$${file_path}/${file_base_name}\""
}
]
}
Now you can choose "C++ Single File with -O2" from Tools -> Build System.
If you disregard any of the rules above and lose points as a result, it is your own fault! It's not the fault of Hacker Cup organizers and it's not because you have an old and slow computer!
