Coder's blog

By Coder, history, 9 years ago, In English

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

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

LOL

»
9 years ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

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).

»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

LOL hahaha

»
6 years ago, # |
  Vote: I like it -18 Vote: I do not like it

sometimes it produces trap foro contestants. N <= 18 and they starts to think about bitmasks though it is a sorting problem xD