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, In English,

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.

Read more »

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

By bvd, history, 3 years ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By bvd, history, 3 years ago, In English,

17493195_1919527948281479_2748595590774946471_o.jpg

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.

Read more »

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

By bvd, history, 3 years ago, In English,

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?

P.S: Why I need to calculate the determinant of a matrix in polynomial time?

Read more »

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

By bvd, history, 4 years ago, In English,

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.

Read more »

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