FastPrep
Problem · Graph

Drop-Off Centers

Learn this problem
● HardAtlassian logoAtlassianFULLTIMEOA

Problem statement

Each graph node is a potential drop-off center owned by one company. A contracted company contributes all of its centers. Count non-empty company subsets for which every pair of selected centers is at least minDistance apart by shortest-road distance.

Function

findCount(n: int, graphFrom: int[], graphTo: int[], graphWeight: int[], minDistance: int, company: int[]) → int

Examples

Example 1

n = 3graphFrom = [1,2,3]graphTo = [2,3,1]graphWeight = [3,2,5]minDistance = 4company = [1,2,3]return = 4

The valid subsets are each singleton and companies 1 with 3.

Constraints

  • 2 <= n <= 1000
  • 1 <= edges <= n(n-1)/2
  • 1 <= edge weight, minDistance <= 100
  • 1 <= companies <= 10
  • There is at most one road between a node pair.

More Atlassian problems

drafts saved locally
public int findCount(int n, int[] graphFrom, int[] graphTo, int[] graphWeight, int minDistance, int[] company) {
  // Write your code here.
}
n3
graphFrom[1,2,3]
graphTo[2,3,1]
graphWeight[3,2,5]
minDistance4
company[1,2,3]
expected4
checking account