Блог пользователя Coder

Автор Coder, история, 9 лет назад, По-английски

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
  • Проголосовать: не нравится

Автор Coder, 12 лет назад, По-английски

Have you noticed that in Div2-only matches there are always unrated people in top? And later most of them are abandoning that account? Even though they could participate unofficially with their main account, they are stealing rating from Div2 people.

Some of the most obvious heroes: superpears siIlycross multiset Bigsophie

Полный текст и комментарии »

  • Проголосовать: нравится
  • +101
  • Проголосовать: не нравится