Connection Status:
Competition Arena > Diophantine

Diophantine

TCO19 Wildcard Fun Round · 2019-08-16 · by misof

TCO19 Wildcard Fun Round · 2019-08-16 · by misof · Dynamic Programming, Math, Search, Sorting
Class Name: Diophantine
Return Type: long
Method Name: countSolutions
Arg Types: (int, int)
Problem Statement

Problem Statement

This problem has a nonstandard time limit: 7 seconds.

Let p[] be the sequence of all primes in increasing order: p[0]=2, p[1]=3, p[2]=5, and so on.

Let D be a positive integer constant. For each i >= 0, let q[i] = p[i] * p[i+D].

Consider the following equation: V + W + X + Y = Z.

You are given ints N and D. Count the number of solutions to this equation such that V <= W <= X <= Y and all numbers V,W,X,Y,Z are in the set QN = { q[0], q[1], ..., q[N-1] }.

Notes

  • A positive integer is a prime if it has exactly two positive integer divisors. Note that 1 is not a prime.

Constraints

  • N will be between 1 and 2,500, inclusive.
  • D will be between 0 and 2,500, inclusive.
Examples
0)
15
1
Returns: 2

The two solutions are: 6 + 15 + 323 + 323 = 667 6 + 143 + 221 + 1147 = 1517 Note that the first solution uses the value 323 twice.

1)
2470
0
Returns: 0

No solutions at all.

2)
30
500
Returns: 1

One solution. In it, the right-hand side of the equation is 406,279.

3)
47
7
Returns: 14
4)
1
0
Returns: 0

Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Diophantine with a public method long long countSolutions(int N, int D) · 87 test cases · 2 s / 256 MB per case

Submitting as anonymous