Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

### bvd's blog

By bvd, history, 6 days ago, ,

This problem is a variation of the following problem:

http://icpcvncentral.tk/public/practice_problem.php?id=I19CE&fbclid=IwAR2j4yF6-LvsAn7ATxinyuo7LYj97MSiDIKCHsclI6dIr-bWgAySbqYRQ98

For some reason, I misread "longest" into "shortest", which made the problem much harder.

My version of this problem:

Given $n$ points $(a_1,0)$, $(a_2,0)$, ..., $(a_n,0)$. Pick $k$ points from $n$ points and calculate the shortest distance $d$ between two points in those $k$ points. Calculate the expected value of $d$.

An easier version of this problem:

$n$ points are $(1,0)$, $(2,0)$, ..., $(n,0)$.

Is this problem solvable in $O(n^3)$, $O(n^2)$, $O(nk)$ or even $O(n\log{n})$? Thank you.

• +28

By bvd, history, 3 years ago, ,

I'm currently stuck on Sortware Bugs — CTU Open 2012.

Problem Summary:

You're given a string S and a string B (S has at most 107 characters, and B has at most 1000 characters); and you need to remove B from S repeatedly until there is no B in S.

Can you give me some hints? I have been trying to solve this problem for two days, and I cannot figure out any way to solve this problem.

There is a solution on the Internet; however, since it is not in English (and Google Translate didn't help much), I cannot understand it :(.

Thank you :)

• 0

By bvd, history, 3 years ago, ,

English version:

The first problem is similar to Problem G — Inverse Factorial in 2016 ICPC North American Qualifier Contest; however, there is a twist: if there is no n for the given value n!, you need to output  - 1.

I think there is a solution for this problem, but I can not find it :)

By the way, a gifted 9-grader in Vietnam has no idea about FFT anything similar to that.

• +3

By bvd, history, 3 years ago, ,

This is how I normally calculate the determinant of a matrix.

However, the complexity of this algorithm is O(n!).

How to calculate it in polynomial time?

• +8

By bvd, history, 4 years ago, ,

English version

Find all prime numbers between N and M, with 0 < N < M < 1025.

A further classification said that the time limit is 1 second and M - N < 109.

I'm wondering if there is a solution for this problem.