AtLeastKDays
SRM 795 · 2020-12-11 · by misof
Problem Statement
There are N cities, numbered from 0 to N-1. For each ordered pair of cities (u, v) you know the cost costs[u][v] of flying directly from u to v. Each such flight takes one day. Flight costs are not necessarily symmetric.
Suppose you are in city u and you want to get to city v. You would like to use this opportunity to obtain a frequent flyer status. In order to get the status, you have to travel on at least minDays consecutive days. What is the minimum total cost c(u, v) of a flight schedule that gets you from u to v in minDays or more days?
Return the sum of all N*N values c(u, v). Note that this includes trips that start and end in the same city.
Notes
- The diagonal of the array costs contains the character '-' denoting that staying in a city is not a valid form of traveling.
- Digits in costs represent the corresponding numerical values. For example, if costs[4][7] = '3', the flight from 4 to 7 has cost 3.
Constraints
- N will be between 2 and 50, inclusive.
- costs will contain exactly N elements.
- Each element of costs will contain exactly N characters.
- For each u, costs[u][u] will be '-'.
- Each other character in costs will be between '1' and '9', inclusive.
- minDays will be between 1 and 10^9, inclusive.
{"-12",
"3-6",
"45-"}
1
Returns: 34
We are traveling for at least one day. For some pairs of cities the optimal solution is to take the direct flight and stop. These are c(0,1) = 1, c(0,2) = 2, c(1,0) = 3, c(2,0) = 4, and c(2,1) = 5. If we have to start and end in the same city, we need to fly for at least two days. The optimal travel costs for these cases are c(0,0) = c(1,1) = 4 and c(2,2) = 6. This leaves us with travel from 1 to 2. There is a direct flight that costs 6, but also a cheaper option: to fly from 1 to 0 and then from 0 to 2, paying only 3+2 = 5. Thus, c(1,2) = 5. The returned value is the sum of all c(u,v): 4+1+2+3+4+5+4+5+6 = 34.
{"-111111111",
"1-11111111",
"11-1111111",
"111-111111",
"1111-11111",
"11111-1111",
"111111-111",
"1111111-11",
"11111111-1",
"111111111-"}
1000000000
Returns: 100000000000
For each of the 10*10 pairs of vertices we can get from u to v in exactly 10^9 days while paying 1 for each ticket. Thus, each c(u, v) is 10^9 and therefore the final answer is 10^11.
{"-12",
"3-6",
"45-"}
6
Returns: 122
The same costs as in example 0, but now we are traveling for at least 6 days. One of the things worth noting is that c(0,1) = 13. The optimal way of traveling from 0 to 1 in at least 6 days is to travel in 7 days, alternating between cities 0 and 1 the whole time. Another thing worth noting is that c(0,2) = 14. Again, optimal travel involves seven days, in which we travel as follows: 0-1-0-1-0-1-0-2.
{"-1897688282326927855795277755247378635759387656729", "1-653589649243369872697255784495434783692383726244", "95-12344725283236265463972388769433992836935774923", "991-5626983397685336877338727286656596997249228996", "6363-179856728948244398259482438289973833883499938", "78571-49736937283556632649589285737343543444334873", "865737-1547378789889257283933782748993552974463262", "2675571-592668388796295682285873779339634558956232", "65795782-17232625222895368723662998736873884622545", "328888441-6432543243468924453469996894289987766882", "6498332774-174289746678354565974734457552784945829", "73634568361-87566725697344676365265599382438658535", "538677337953-1952768623695967857545522665774774493", "2899639676581-879645475625927266859923489452893299", "44567596967356-14593757364674434243627439636594455", "669265284695921-8444257866365296569446966262388488", "5894687738843855-127865632547739667526953648656447", "46936648554364961-55359866277833765459524275755975", "849528958283958525-1697685255999884872737864252664", "7754534724486345791-762669947452328954724599829575", "89444572594689824882-13595232769633792699436792928", "357554593639524646741-4488748238433433524833923474", "4654284823583757652624-168727644529568922783375673", "49875669594885272533651-43276267774363997846398655", "242689552652764833544387-1642668775657875472947833", "3844493578593952275824871-558698892445774224442275", "24276684994482449487229564-18473755994562382729236", "757275554758234877999942891-8459827659553985927557", "5282777924353668237867649446-187892669684588926936", "75332467835657359439253729331-43435545898245273699", "859564864462255385245983248676-1366693777952229968", "7433756967755544597648783382251-932525388554993463", "88644577634356794983424968988564-13785582434778629", "822223233524692369455739329922991-8787468956978687", "9245753639737285654226496398583789-162652672986843", "28735945798786844597687864822897261-58572363388678", "727844826672953638987595897586883722-1239795826987", "4777757682562483693224649835978556631-358985662886", "42873468444955886366992252823849697899-15622822342", "957979738963729793593556499597649752261-4964979535", "8357227322979743542356445377888855886484-149242225", "74787538743783536647668262684637899747331-68332997", "448748552953732353984762789423663283323639-1597547", "2342369596846786397472752225663259558877691-646526", "47293236555337464683886332549777826272238698-16646", "558799997572726338996897378639494726994492581-2926", "3427995928826577498677299639456277643574848895-147", "39646638743544522724362272662495578633392464371-95", "967622875443894333972649293563776939522983248626-1", "6336944493278238697367437649288898958285289667431-"}
977611780
Returns: 2444029454350
{"-19382245348372559494622444549485545644", "1-9237623975955463756632782484397365724", "78-152949322396385283847949854858858429", "561-83635675755254665279627956394392572", "7893-1374833948782984587522385687766683", "95961-952839852635285555335337669489792", "769379-19862978289367456833477745223392", "3239551-9655585368845493692335824627844", "73692382-156893268274536898759653762687", "439967651-87885525665476794326635633698", "5454325754-1487699899645484463433299784", "92978288821-383853256953496583257527469", "255845792484-15458944845657568559843488", "9849588794451-2835973843847878849354973", "67796534329264-177747728777774648762743", "246732837349291-68234564364758554946294", "9962778474856984-1986449753627542885254", "52293785324364681-847272796795748489962", "327265399475764326-13262262236774625826", "6246448597272562591-7424543848668366734", "83446657776878785278-177287972756333558", "535422852556359858251-89653884467589258", "3692993948596626464243-1462996662569592", "22587562778565356227521-642694294685442", "437287533569797235856394-18626887337935", "4353843559982669563246671-5988433558465", "58564684682392482755629852-188889943468", "235893954698677234247675631-64875349594", "3253396252636887686333937784-1999569847", "94744997285823757536756338571-858282853", "477487673827636234292896883544-15574298", "7525873327569822595996865426861-5638765", "87946239323976429568222343434628-125384", "943286225935285284623528639885421-78864", "9477286437896642823457694546328525-1848", "39744242797936745284383557878397481-236", "842738276799637572329574589768395374-17", "8336625939565332577728379962522488841-2", "36297685268832572567662433999558477443-"}
872386239
Returns: 1326899472195
Submissions are judged against all 144 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AtLeastKDays with a public method long long sumOfMinCosts(vector<string> costs, int minDays) · 144 test cases · 2 s / 256 MB per case