-is-this-fft-'s blog

By -is-this-fft-, history, 6 weeks ago, In English

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

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::Blocks
CLion
CP Editor
Sublime Text

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!

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

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Also very important: if you are using windows subsystem for linux, ulimit -s unlimited may not work. Use a compiler on native Windows.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    This works for gcc in WSL:

    set_stack_size

    Copied from here.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

on MacOS ulimit -s unlimited gave me bash: ulimit: stack size: cannot modify limit: Operation not permitted, not using root, appending -Wl,-stack_size,20000000 to gcc/clang seems working for me

I used this function to verify I can access 500MB stack
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    use sudo

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 3   Vote: I like it +4 Vote: I do not like it

      I know sudo but don't think it's a good idea to use it all the time. (as far as I know ulimit just changes current session and will not be in effect later or when exiting sudo)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There's a soft and a hard limit. You cannot set the soft limit to anything higher than the hard limit, and you can't increase the hard limit (unless you are root). On Linux the hard limit is usually unlimited, but that might not be the case on MacOS. You can use ulimit -Hs to see the hard limit, or use ulimit -s hard to set the soft limit to the hard limit, i.e. as high as possible.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The hard limit on my machine is around 64MB and I was able to change it to that without root. Also via the linker method the max stack can be specified is 512MB, since declaring a large array of 511MB was fine and a 512MB resulted stack overflow, looks that way is able to bypass the system limit.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

To increase stack size in OSX I do g++-9 -Wl,-stack_size -Wl,100000000 test.cpp && ./a.out

Have it in my library since I can never remember it.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

For newer linkers (on Linux/Mac), the command to set stack size has changed so the common recommendation of -Wl,--stack=268435456 throws a linker error like the following:

/usr/bin/ld: unrecognized option '--stack'
/usr/bin/ld: use the --help option for usage information
collect2: error: ld returned 1 exit status

On modern systems, pass -Wl,-z,stack-size=268435456 to your C(++) compiler instead. This is tested with GNU ld (GNU binutils) 2.43.1, LLD 18.1.8, and mold 2.33.0.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I created separate input and output files as mentioned in Option 2, but VS Code still crashed(on the same C question mentioned in the blog). Are there better choices available?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    At what point did it crash?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I populated the input file, and then ran the code. The first 13 or so test cases ran(there wasn't any output in the output file but I had added a "Hello" line to be printed in the terminal, and there were around 13 "Hello"). After that I left it idle for around 10 minutes but nothing happened(the output file remained empty).

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you show your code? Maybe it was just slow?

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          #include <bits/stdc++.h> #include <fstream> using namespace std; #define endl '\n' #define ll long long #define int long long #define ld long double typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<vector<int>> vvi; typedef pair<ll, ll> pll; #define pb push_back #define eb emplace_back #define srt(v) sort(v.begin(), v.end()) #define all(v) (v).begin(), (v).end() const ll mod = 1e9 + 7; const ll N = 1e6; long double EPS = 1e-7; long long inv(long long a, long long b) { return 1 < a ? b - inv(b % a, a) * b / a : 1; } long long power(long long A, long long B) { if (B == 0) return 1; long long res = power(A, B / 2); if (B % 2) return res * res * A; else return res * res; } ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } vector<bool> nums(N + 1); vector<int> primes; void sieve() { nums[0] = true; nums[1] = true; for (int i = 2; i <= N; i++) { if (nums[i] == false) { primes.push_back(i); for (int j = i * i; j <= N; j += i) { nums[j] = true; } } } } int mex(vi arr) { int m = 0; srt(arr); for (int i = 0; i < arr.size(); i++) { if (arr[i] == m) m++; } return m; } void primeFactors(int n, vi &res) { while (n % 2 == 0) { res.pb(2); n = n / 2; } for (int i = 3; i <= sqrt(n); i = i + 2) { while (n % i == 0) { res.pb(i); n = n / i; } } if (n > 2) res.pb(n); } void main_() { // Open input and output files ifstream fin("faceinput.in"); ofstream fout("faceoutput.out"); int t; fin >> t; for (int caseNum = 1; caseNum <= t; caseNum++) { cout<<"Hello"<<"\n"; int n; fin >> n; string s; fin >> s; int q; fin >> q; vi queries(q); map<int,int>p; for (int i = 0; i < q; i++) { fin >> queries[i]; p[queries[i]]^=1ll; } for (int i = 1; i <=n; i++) { if(p[i]) { for(int j=i;j<=n;j+=i) { int num=s[j-1]-'0'; num^=1ll; s[j-1]=num+'0'; } } } int res = 0; for (int i = 1; i <= n; i++) { if (s[i-1]) { res++; for(int j=i;j<=n;j++) { int num=s[j-1]-'0'; num^=1ll; s[j-1]=num+'0'; } } } // Write the output in the required format fout << "Case #" << caseNum << ": " << res << "\n"; } // Close the file streams fin.close(); fout.close(); } signed main() { main_(); return 0; }
          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
            Rev. 2   Vote: I like it +8 Vote: I do not like it

            $$$N$$$ in this problem is up to 4 million, your code is $$$O(N^2)$$$, it would probably take a day or two to finish. So it's expected that it would not finish in 10 minutes.

            Nothing shows up in the output file because you used "\n" to print line breaks instead of endl. If you use "\n", they might be actually written only when the program finishes working.

            But did anything actually crash (i.e. did VS Code become unusable or similar)?

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it +11 Vote: I do not like it

              Aaah! My bad. The second double for loop's inner one should have update condition j+=i. Also even my logic was wrong. Since I am working with strings it should have been if(s[i-1]=='1') and not just if(s[i-1]). It now got Accepted. Thanks a lot -is-this-fft-

              The O(n^2) solution was making VS code unresponsive. I even had to restart my computer once.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                How do you run your solution in VS Code? Do you press some "run" button or do you write something in the terminal? If the first, does it take you to some debug mode?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  There is a triangle(with its base vertical) on the top right corner. On clicking it, the terminal opens. In CF rounds, I just copy paste the input, click enter and the output comes, all in the terminal itself. I don't run any commands in the terminal.

»
6 weeks ago, # |
  Vote: I like it -81 Vote: I do not like it

Activities for poor competitive programmers

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    > be me
    > competitive programmer
    > decide to participate in a competition with a unique format to compete with other competitive programmers
    > genuinely been having fun taking part every year for like 10 years
    > be called poor because of this

    Why are people like this

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +48 Vote: I do not like it

      > be you
      > competitive programmer
      > see troll comment
      > care enough to respond with greentext on website which is not image board
      > manually make text green, add \ before every >, add <br> after every line
      > complain about being called poor

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -51 Vote: I do not like it

      this way of having fun feels poor-ish

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    hacker cup is actually for the richest competitive programmers, it's one of the only two cp contests i know that you can win by running a parallelized solution on your supercomputer cluster

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      :/

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Has anyone actually done anything like this and gotten a meaningful advantage?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Who's gonna confess to this?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          It's actually less about confessions and more about whether this is actually feasible. Writing programs that can actually be efficiently parallelized is nontrivial (if you actually do some MPI or whatever). The other option is to just take a computer that's really fast but I'm not sure that's an actual thing either.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it -10 Vote: I do not like it

        well...

        for this problem many people had multithread solutions and/or solutions that ran close to the 6 minute limit. not a case with some insane computer but it shows that money really does matter

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the difference between -O2 and -O3?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Different optimizations, -O3 is a higher level. Historically -O3 could have done some incorrect transformations (and I think there is some recent example of this), so I always use -O2 unless I am trying to cheese something through (and it has never made enough of a difference). So probably just using -O2 is fine.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Are templates allowed in the contest like on codeforces?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the difficulty level of the questions?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this post

i get the segmentation fault on it. Now i have increased the stack size and now its working fine

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to create a facebook account fast? Verification (why?) takes one day apparently

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The scoreboard does not load. I think it always worked before the contest in previous years.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Disabling Adblock solved this for me.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Sadly I won't have internet access until December

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am using MacOS but ulimit -s unlimited did not work for me.Even after using this it shows segmentation error core dumped

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I didn't qualify to the next round because of this blog. I used the template you provided to increase the stack size and when I wanted to run my solution on A , the code kept running for more than 6 minutes and the timer ran out. I tried the code on my regular template and it took less than a minute.

I think you owe me a T-shirt.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I actually used a simple command. First, I compiled the code and get .exe file for cpp file. Then open command prompt and change the path to target directory where both input test case .txt file and .exe file are present. Command is : A_file_name.exe <input_test_file.txt> output_test_case.txt. You don't need to even create a separate output file; it creates on it's own. And simply keeps updating (writing file), so you can simply open and check how many test cases have been executed. It hardly took me 15-20s.

    (Sorry for my bad English)