Connection Status:
Competition Arena > Excavations

Excavations

SRM 584 · 2013-06-25 · by gojira_tc

SRM 584 · 2013-06-25 · by gojira_tc · Dynamic Programming
Class Name: Excavations
Return Type: long
Method Name: count
Arg Types: (vector<int>, vector<int>, vector<int>, int)
Problem Statement

Problem Statement

Once upon a time, there was a civilization called Ruritania. It had n building sites numbered from 0 to n-1. There were various types of buildings such as libraries, markets, and palaces. Each building type was assigned an integer from 1 to 50. The building at site i (0-based index) was of type kind[i].

With the passing of millennia, Ruritania declined and its building sites were covered in sand, concealing all the buildings. Due to wind and terrain, the depth of the sand varied. The building at site i (0-based index) was buried depth[i] meters below the surface.

Recently, an intrepid archeologist excavated K building sites using a machine that could dig to a maximum depth of D meters. Thus, he only discovered buildings that had been buried at most D meters below the surface.

You are given int[]s kind, depth, and found as well as the int K. The types of buildings discovered by the excavation are given by the int[] found, which contains at most one value for each building type even if several buildings of a type were excavated.

Return the number of K-tuples of sites that could have been excavated to arrive at the given values. If the given information is not consistent with any configuration of building sites, return 0.

Constraints

  • kind will contain N elements, where N is between 1 and 50, inclusive.
  • Each element of kind will be between 1 and 50, inclusive.
  • depth will contain N elements.
  • Each element of depth will be between 1 and 100,000, inclusive.
  • found will contain between 1 and 50 elements, inclusive.
  • Each element of found will occur in kind at least once.
  • The elements of found will be distinct.
  • K will be between the number of elements in found and N, inclusive.
Examples
0)
{1, 1, 2, 2}
{10, 15, 10, 20}
{1}
2
Returns: 3

There are four building sites. Two have buildings of type 1 and two have buildings of type 2. The type 1 buildings are at depths 10 and 15. The type 2 buildings are at depths 10 and 20. The archeologist has excavated two sites and discovered only type 1 buildings. He must have excavated one of three possible pairs of sites: Sites 0 and 1. The archeologist's machine excavates to a maximum depth D of at least 10. Sites 0 and 3. The machine excavates to a maximum depth D that falls in the interval [10, 20). Sites 1 and 3. The machine excavates to a maximum depth that falls in the interval [15, 20). The other pairs of sites could not have been excavated. For example, the archeologist could not have excavated sites 0 and 2, because he would have found either none or both of the buildings.

1)
{1, 1, 2, 2}
{10, 15, 10, 20}
{1, 2}
2
Returns: 4

The archeologist could have chosen any pair of sites containing a type 1 and a type 2 building. With a large enough value of D, he could have excavated both.

2)
{1, 2, 3, 4}
{10, 10, 10, 10}
{1, 2}
3
Returns: 0

The archeologist cannot have excavated three sites, or else he would have found three types of buildings.

3)
{1, 2, 2, 3, 1, 3, 2, 1, 2}
{12512, 12859, 125, 1000, 99, 114, 125, 125, 114}
{1, 2, 3}
7
Returns: 35
4)
{50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50}
{2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3}
{50}
18
Returns: 9075135300

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

Coding Area

Language: C++17 · define a public class Excavations with a public method long long count(vector<int> kind, vector<int> depth, vector<int> found, int K) · 60 test cases · 2 s / 256 MB per case

Submitting as anonymous