### Coder's blog

By Coder, history, 4 years ago, ,

Suppose the input for a problem is positive integer N and answer happens to be 1/N. Here is what happens for different constraints on N. You decide which version is the hardest.

1.

N <= 10^9

Everyone does math and all solutions look like

cout << 1.0 / N


2.

N <= 10^6

You see solutions from above but some contestants decide to use iterative approach, something like

double ans = 1.0;
for (int i = 2; i <= N; i++) ans = ans * (i - 1) / i;


3.

N <= 10^5

Mostly solutions from above, but some contestants use recursion (maybe with memoization)

double f(int N) {
if (N == 1) return 1.0;
return f(N - 1) * (N - 1) / N;
}


4.

N <= 500

Solutions from above, but some contestants go with O(N^3) dynamic programming instead

5.

N <= 109

Contestants think there is a typo and go with first solution

6.

N <= 100

Some contestants realize that you can precompute all answers

const double ans[100]={1.0, 0.5, 0.333333333, ... }


7.

N <= 47

Intended solution from Ukrainian author has O(N^4) complexity

8.

N <= 36

You see lot of solutions with meet-in-the middle approach

9.

N <= 20

You start to see a lot of bitwise operations in codes that can mean dynamic programming on subsets

10.

N <= 10

Some C++ codes use next_permutation(), Java coders having harder time

•
• +252
•

 » 4 years ago, # |   0 LOL
 » 4 years ago, # | ← Rev. 2 →   +36 N ≤ 5. Long contest. THE HARDEST PROBLEM IN THE CONTEST!N ≤ 50. 70% of all solutions fall in challenge phase, 50% of them in the first 30 seconds.N ≤ 106, Hungary: TL is too low, no chance of reading the input (CEOI, practice session).
 » 4 months ago, # |   -14 LOL hahaha
 » 4 months ago, # |   -18 sometimes it produces trap foro contestants. N <= 18 and they starts to think about bitmasks though it is a sorting problem xD