Connection Status:
Competition Arena > TravellingPurchasingMan

TravellingPurchasingMan

SRM 579 · 2012-12-13 · by vexorian

SRM 579 · 2012-12-13 · by vexorian · Graph Theory
Class Name: TravellingPurchasingMan
Return Type: int
Method Name: maxStores
Arg Types: (int, vector<string>, vector<string>)
Problem Statement

Problem Statement

You are interested in purchasing items from a number of stores in a local market. The market is composed of N stores numbered from 0 to N-1. The stores with numbers from 0 to M-1 are interesting to you and all the other stores are not interesting. Some pairs of stores are connected by roads.

You are given a String[] interestingStores which contains M elements and describes the interesting stores. The i-th element corresponds to store i and is formatted "OPEN CLOSE DURATION" (quotes for clarity), where OPEN is the opening time (in seconds), CLOSE is the closing time (in seconds) and DURATION is the time (in seconds) required to make a purchase in this store. You can initiate a purchase from a store at any time T between OPEN and CLOSE, inclusive. In order to do so, you need to arrive to the store at time T (or earlier). The purchase will be finalized at time T + DURATION and you need to stay at the store for the entire duration of your purchase. Note that it is possible for a purchase to end when the store is already closed. You cannot make multiple purchases in the same store.

The roads are given by the String[] roads. Each element of roads describes a single bidirectional road and is formatted "A B LENGTH" (quotes for clarity). Here A and B are the numbers of stores connected by the road and LENGTH is the time (in seconds) required to move from A to B (or from B to A) using this road.

Your start at time 0 at the location of store N-1. Return the maximum number of purchases in interesting stores that you can make.

Notes

  • You are allowed to wait for any amount of time at any location.

Constraints

  • N will be between 1 and 50, inclusive.
  • roads will contain between 1 and 50 elements, inclusive.
  • Each element of roads will be formatted "A B LENGTH" (quotes for clarity), where A, B and LENGTH are integers with no unnecessary leading zeros.
  • In each road, A and B will each be between 0 and N-1, inclusive.
  • In each road, A and B will be distinct.
  • In each road, LENGTH will be between 1 and 604,800, inclusive.
  • There will exist at most one road between each pair of stores.
  • interestingStores will contain between 1 and min{16, N} elements, inclusive,
  • Each element of interestingStores will be formatted "OPEN CLOSE DURATION" (quotes for clarity), where OPEN, CLOSE and DURATION are integers with no unnecessary leading zeros.
  • In each store, OPEN will be between 0 and 604,800, inclusive.
  • In each store, CLOSE will be between OPEN+1 and 604,800, inclusive.
  • In each store, DURATION will be between 1 and 604,800, inclusive.
Examples
0)
3
{"1 10 10" , "1 55 31", "10 50 100" }
{"1 2 10"}
Returns: 1

It is not possible to make more than one purchase: If you decide to make the purchase at store 2: You need to wait 10 seconds until it opens. Then wait until time = 110 seconds for the purchase to finish. At 110 seconds, all the other stores will be closed. If you instead decide to make the purchase at store 1: You first need travel through the road and arrive store 1 at time = 10. The purchase finishes at time = 41. After you travel back to store 2, the time will be 51 seconds and store 2 will be closed. There is no way to reach store 0 when store 2 is the starting point.

1)
3
{"1 10 10" , "1 55 30", "10 50 100" }
{"1 2 10"}
Returns: 2

This time we can travel to store 1, make the purchase and return to store 2 exactly at time = 50 to make two purchases in total.

2)
5
{"0 1000 17"}
{"2 3 400", "4 1 500", "4 3 300", "1 0 700", "0 2 400"}
Returns: 0

It is not possible to reach store 0 before it closes.

3)
25
{"41257 54985 26521","16226 67120 1326","54421 60605 53372","52398 58957 40184","59698 88159 14782","39728 75437 12470","39215 97166 31604"}
{"0 1 41504","1 2 55076","0 4 60074","4 6 34802","4 9 23908","1 3 58948","4 11 4024","11 10 33185","3 13 27069","13 17 8164","9 19 25872","4 14 58866","14 23 9418","23 8 48655","9 18 52708","8 22 6697","13 7 11413","5 15 34403","0 10 33164","15 23 44676","1 7 31920","19 3 43466","12 16 36349","21 14 33740","13 2 10775","9 24 23944","3 0 12152","12 18 42036","8 12 31759","14 15 58777","23 7 36538","8 2 638","8 20 30635","16 17 30280","3 7 39219","15 0 52712","1 10 16597","21 1 26771","7 2 60009"}
Returns: 1
4)
36
{"55038 111843 42713","24898 58111 38720","42624 44284 33587","19508 44737 39482","59211 119048 56096","20505 61172 54111","48274 54164 29762","56781 81164 50500","50333 109561 17555","29381 83596 10676","54403 112844 31794","18560 46303 5196","43943 47142 3475","46612 58637 7413"}
{"0 1 5102","1 3 30916","1 4 16108","4 2 49579","1 8 43125","3 11 19333","4 13 49304","2 5 54270","5 9 47488","0 17 37435","3 14 1124","4 10 44583","13 21 37602","2 23 53392","3 25 45461","25 24 52339","23 12 24680","24 29 33783","9 7 11951","7 33 38586","1 32 18826","13 16 10071","0 6 32490","32 30 29266","2 20 45749","5 7 26448","9 21 17756","1 10 4459","9 33 6555","10 11 51660","10 3 30807","11 14 28329","13 14 16128","31 9 31430","32 25 46132","5 33 9820"}
Returns: 0

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

Coding Area

Language: C++17 · define a public class TravellingPurchasingMan with a public method int maxStores(int N, vector<string> interestingStores, vector<string> roads) · 201 test cases · 2 s / 256 MB per case

Submitting as anonymous