bvd's blog

By bvd, 7 days ago, In English,

Since the passing of ICPC chief archivist Professor Miguel Revilla, the problem statements of 2018 ICPC Regionals and 2019 ICPC Regionals have not been fully archived. Therefore, I decided to write this blog to archive the problems of all North American ICPC competitions in the 2019-2020 season for the good of the community (actually for Codeforces contributions).

You can help by providing links to the missing information or pointing out mistakes in the below table. Any help will be appreciated, and I will update this blog frequently.

Because I'm not archiving problems from other continents, I encourage other Codeforces users to archive problems from their continents and write similar blogs.

Regional Problemset Solution Testdata Judge
UChicago Qualifier 2019 Kattis Kattis
ICPC North America Qualifier 2019 PDF Solution Testdata Kattis
2019 Atlantic Canadian Preliminary Contest
BOSPRE — Eastern Contest PDF
2019 East Central NA Regional Contest PDF Solution Testdata Kattis
2019 NENA Regional Qualifier Kattis Kattis
2019 Rocky Mountain Regional Contest Kattis Solution Kattis
2019 Greater NY Regional Contest Problems Solution Testdata
2019 Mid-Central USA Regional Contest Kattis Kattis
2019 Mid-Atlantic USA Regional Contest Kattis Kattis
2019 North Central NA Regional Contest Titles Kattis Kattis
2019 Northeast North America Regional Contest Kattis Kattis
2019 Pacific Northwest Regional Contest PDF Solution Testdata
2019 South Central USA Regional Contest Titles Kattis Solution Kattis
2019 Southeast USA Regional Contest PDF Solution Testdata
2019 Southern California Regional Contest PDF
2019 UCF Qualifier PDF Solution Testdata
Lethbridge Collegiate Programming Contest
Alberta Collegiate Programming Contest Kattis Kattis
2019 LSU Spring Preliminary

Note

  • In the 2019 East Central NA Regional Contest, the solution for the problems is in the Problem Files.
  • The 2019 North Central NA Regional Contest and the 2019 South Central USA Regional Contest share some common problems. Therefore, I include a link to the titles of the problems.

Update

  • I found the solution of the 2019 Rocky Mountain Regional Contest and the problem set of BOSPRE 2019 on the official ICPC website. It seems to be that ICPC is still archiving problems from Regional contests.

Read more »

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

By bvd, history, 2 months 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