AliceInWanderland

TCO10 Semi 1 · 2010-04-11 · by lyrically

TCO10 Semi 1 · 2010-04-11 · by lyrically · Dynamic Programming

Show categories

Class Name: AliceInWanderland

Return Type: long

Method Name: getMinimum

Arg Types: (vector<int>, vector<int>, vector<string>)

Problem Statement

Alice has fallen into the rabbit-hole. Now she is in a strange world.

The world is an infinitely large grid on a plane. Alice is in the cell (0, 0) at time 0. Alice sees rabbits wandering. Rabbit i is in the cell (rabbitX[i], rabbitY[i]) at time 0. At time t - 0.5 (t being a positive integer) the rabbit will step one cell according to t-th (1-based) character of the infinite repetition of String moves[i]. 'R' means increasing x, 'L' means decreasing x, 'U' means increasing y and 'D' means decreasing y. At each time t (t being a positive integer) Alice will perform a move that consists of two following steps:

First, she steps to one of her eight neighboring cells or chooses to stay in her current cell.
Then, if there are one or several rabbits in her destination cell, she touches all of them.

Return the minimum possible time for Alice to touch all the rabbits. If this time is strictly greater than 1,000,000,000,000,000 or she can never touch all the rabbits, return -1 instead.

Constraints

rabbitX will contain between 1 and 11 elements, inclusive.
rabbitX, rabbitY and moves will contain the same number of elements.
Each element of rabbitX and rabbitY will be between -1,000,000,000 and 1,000,000,000, inclusive.
For each index i, (rabbitX[i], rabbitY[i]) will not be (0, 0).
Each element of moves will contain between 1 and 50 characters, inclusive.
Each character in moves will be either 'R', 'L', 'U' or 'D'.

Examples

{ 4 }
{ 2 }
{ "ULDR" }
Returns: 3

The rabbit moves (4, 2) -> (4, 3) -> (3, 3) -> (3, 2) -> (4, 2) -> ... In order to touch the rabbit at time 3, Alice can move as follows: (0, 0) -> (1, 1) -> (2, 2) -> (3, 2).

{ 10, -20 }
{ 0, 0 }
{ "RL", "LULD" }
Returns: 80

Alice should pursue rabbit 0 first in this case.

{ 30, -40 }
{ 0, 0 }
{ "RL", "DLUL" }
Returns: 188

Alice should pursue rabbit 1 first in this case.

{ 0 }
{ 1 }
{ "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU" }
Returns: -1

Alice can never touch the rabbit.

{ -551823, 770210, 287436, -140476, 41272, 177287, -693253, 957374 }
{ 149299, 462027, -93710, -624374, 149825, 346324, 892345, -382205 }
{ "RDULRULRUDLURLDURLUDLURDLURLDURLDURLUDRLUDLURLR", 
  "RUDLDRULDRUDLRDLURDLRDLRDULRULDURLDURULDURULDRULD", 
  "ULDULRUDLRULDULRULDRULDULRLDRULDRULUDRDLRLDLU", 
  "DURDLRUDULLRDULULRULDRULULDRULDRULDRULULDRLDRLDRDR", 
  "ULUDLRULDRULDRULULDRULDDDLUDRULDLULRDULDUURDLURL", 
  "RULDLURULDLRUDLRUDULRUDLRULRDLRULDURLDRUDLRULDULRU", 
  "DURLDLRULDULRULDRLDLRUDLURDULRLDULRULDLULRUDLULRU", 
  "DULRUDURUDULRULDULRUDURULDULRLDRULDLRULDULRULDURL" }
Returns: 4486904

{ 1000000000, 1000000000, -1000000000, -1000000000, 1000000000, 1000000000, -1000000000, -1000000000, 0, 0, 0}
{ 0, 0, 0, 0, 0, 0, 0, 0, 1000000000, 1000000000, -1000000000}
{ "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRU", 
  "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRD", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLU", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLD", 
  "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRUU", 
  "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRDD", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLUU", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLDD", 
  "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUR", 
  "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUL", 
  "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR" }
Returns: -1

It will take too much time.

{ 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
{ "RDULRULRUDLURLDURLUDLURDLURLDURLDURLUDRLUDLURLRDUL", "RUDLDRULDRUDLRDLURDLRDLRDULRULDURLDURULDURULDRULDR", "ULDULRUDLRULDULRULDRULDULRLDRULDRULUDRDLRLDLURUDUR", "DURDLRUDULLRDULULRULDRULULDRULDRULDRULULDRLDRLDRDR", "ULUDLRULDRULDRULULDRULDDDLUDRULDLULRDULDUURDLURLDL", "RULDLURULDLRUDLRUDULRUDLRULRDLRULDURLDRUDLRULDULRU", "DURLDLRULDULRULDRLDLRUDLURDULRLDULRULDLULRUDLULRUL", "DULRUDURUDULRULDULRUDURULDULRLDRULDLRULDULRULDURLD", "LRULDULRULDRDULDRULDULRULDRULDRULDRULDRULDRULDRULD", "RULDRULDRULDRULULDRULDRULDRULULDRULDRULDRULULDULRD", "UULDULULDLRUDRULDLURDULRUDULURLDURDLURDLURULDULRUL" }
Returns: 1214616

old case: { 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 } { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } { "RDULRULRUDLURLDURLUDLURDLURLDURLDURLUDRLUDLURLRDUL", "RUDLDRULDRUDLRDLURDLRDLRDULRULDURLDURULDURULDRULDR", "ULDULRUDLRULDULRULDRULDULRLDRULDRULUDRDLRLDLURUDUR", "DURDLRUDULLRDULULRULDRULULDRULDRULDRULULDRLDRLDRDR", "ULUDLRULDRULDRULULDRULDDDLUDRULDLULRDULDUURDLURLDL", "RULDLURULDLRUDLRUDULRUDLRULRDLRULDURLDRUDLRULDULRU", "DURLDLRULDULRULDRLDLRUDLURDULRLDULRULDLULRUDLULRUL", "DULRUDURUDULRULDULRUDURULDULRLDRULDLRULDULRULDURLD", "LRULDULRULDRDULDRULDULRULDRULDRULDRULDRULDRULDRULD", "RULDRULDRULDRULULDRULDRULDRULULDRULDRULDRULULDULRD", "UULDULULDLRUDRULDLURDULRUDULURLDURDLURDLURULDULRUL", "UDRLDRULDLRULULDLRULDRULUDLRULDULULRULDRULULDRULDR", "ULULDULRULRULDULRURULDULRULDULRULDULRUDULRULDULULR", "ULRULDULDRULULDURUUDULDLUULLUDULRULRUDULRDULRUDULR" }

{ 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
{ "RDULRULRUDLURLDURLUDLURDLURLDURLDURLUDRLUDLURLRDUL", "RUDLDRULDRUDLRDLURDLRDLRDULRULDURLDURULDURULDRULDR", "ULDULRUDLRULDULRULDRULDULRLDRULDRULUDRDLRLDLURUDUR", "DURDLRUDULLRDULULRULDRULULDRULDRULDRULULDRLDRLDRDR", "ULUDLRULDRULDRULULDRULDDDLUDRULDLULRDULDUURDLURLDL", "RULDLURULDLRUDLRUDULRUDLRULRDLRULDURLDRUDLRULDULRU", "DURLDLRULDULRULDRLDLRUDLURDULRLDULRULDLULRUDLULRUL", "DULRUDURUDULRULDULRUDURULDULRLDRULDLRULDULRULDURLD", "LRULDULRULDRDULDRULDULRULDRULDRULDRULDRULDRULDRULD", "RULDRULDRULDRULULDRULDRULDRULULDRULDRULDRULULDULRD", "UULDULULDLRUDRULDLURDULRUDULURLDURDLURDLURULDULRUL" }
Returns: 1214616

Old case: { 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 } { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } { "RDULRULRUDLURLDURLUDLURDLURLDURLDURLUDRLUDLURLRDUL", "RUDLDRULDRUDLRDLURDLRDLRDULRULDURLDURULDURULDRULDR", "ULDULRUDLRULDULRULDRULDULRLDRULDRULUDRDLRLDLURUDUR", "DURDLRUDULLRDULULRULDRULULDRULDRULDRULULDRLDRLDRDR", "ULUDLRULDRULDRULULDRULDDDLUDRULDLULRDULDUURDLURLDL", "RULDLURULDLRUDLRUDULRUDLRULRDLRULDURLDRUDLRULDULRU", "DURLDLRULDULRULDRLDLRUDLURDULRLDULRULDLULRUDLULRUL", "DULRUDURUDULRULDULRUDURULDULRLDRULDLRULDULRULDURLD", "LRULDULRULDRDULDRULDULRULDRULDRULDRULDRULDRULDRULD", "RULDRULDRULDRULULDRULDRULDRULULDRULDRULDRULULDULRD", "UULDULULDLRUDRULDLURDULRUDULURLDURDLURDLURULDULRUL", "UDRLDRULDLRULULDLRULDRULUDLRULDULULRULDRULULDRULDR", "ULULDULRULRULDULRURULDULRULDULRULDULRUDULRULDULULR", "ULRULDULDRULULDURUUDULDLUULLUDULRULRUDULRDULRUDULR", "ULRUDLRLDRUDULRULDLURUDULRULDULRULULRDULDRURULULDU" }

14)

{ -744, 499, 1219, -153, 591, 1753, 62, 2426, 92, -907, -535 }
{ -1933, -205, -2345, 1578, 1783, 747, 746, -928, -176, -2022, 946 }
{ "DURDRDDDDRUDDDDDRDDU", "RUUUURRUURDRDRDURRDLRRUURDDRRR", "URLUUDRDRUDRUUDRLURUURRUDUUDLUUDLR", "LDRRUDR", "DDLLDLLDUDULLDLUDLD", "DLRRURRUUUULDRDR", "LDDUURDDDDDRUDDDLDRRDDDUUDDDLDDUR", "RRRRRRRULR", "RRLLLLLULLLDDRLLLRLD", "LUDUULULLDLL", "UDLUDUDUUDRUDD" }
Returns: 64079

Old case: { -744, 499, 1219, -153, 591, 1753, 62, 2426, 92, -907, -535, 1816 } { -1933, -205, -2345, 1578, 1783, 747, 746, -928, -176, -2022, 946, 475 } { "DURDRDDDDRUDDDDDRDDU", "RUUUURRUURDRDRDURRDLRRUURDDRRR", "URLUUDRDRUDRUUDRLURUURRUDUUDLUUDLR", "LDRRUDR", "DDLLDLLDUDULLDLUDLD", "DLRRURRUUUULDRDR", "LDDUURDDDDDRUDDDLDRRDDDUUDDDLDDUR", "RRRRRRRULR", "RRLLLLLULLLDDRLLLRLD", "LUDUULULLDLL", "UDLUDUDUUDRUDD", "DDDDDDDDUDRUDDD" }

17)

{ 14912457, -15469502, -19025080, -7181741, 9248306, 22197418, 11575219, 17709091, -10912630, 4246560, 21075576 }
{ -91381, 7852756, 11120227, 8118112, 11773899, -14888408, 1490926, 20568602, 22369515, 11863537, 6521532 }
{ "LRUUUULUULL", "UUDUUDDDLUDUDUULUURLDUUUUUDUUUUDUULUDUR", "DDDRDDDDDLDUDUULDLLRDDLDLD", "DDDUDURLUURUUUURUDDDUDDDUDURDRUUUDUDDDULL", "DLDRLDRDULLLLLLDDRDDLURRLLRDLRDULL", "RL", "DLUUDULLULUUUDULU", "URLLLLLURRLRLLLLDRLLRLR", "DRLRLDDDLRDRUDLLULURLDDDURLDRRDDUDDLLUDL", "RRRDDDRRDDRRDURDRDDDRDDR", "DLLLLLLLLRLRLLUURULU" }
Returns: 162882568

Old case: { 14912457, -15469502, -19025080, -7181741, 9248306, 22197418, 11575219, 17709091, -10912630, 4246560, 21075576, 16632418 } { -91381, 7852756, 11120227, 8118112, 11773899, -14888408, 1490926, 20568602, 22369515, 11863537, 6521532, -9077762 } { "LRUUUULUULL", "UUDUUDDDLUDUDUULUURLDUUUUUDUUUUDUULUDUR", "DDDRDDDDDLDUDUULDLLRDDLDLD", "DDDUDURLUURUUUURUDDDUDDDUDURDRUUUDUDDDULL", "DLDRLDRDULLLLLLDDRDDLURRLLRDLRDULL", "RL", "DLUUDULLULUUUDULU", "URLLLLLURRLRLLLLDRLLRLR", "DRLRLDDDLRDRUDLLULURLDDDURLDRRDDUDDLLUDL", "RRRDDDRRDDRRDURDRDDDRDDR", "DLLLLLLLLRLRLLUURULU", "LUDU" }

29)

{ -203889, 4177249, -7903610, 4050272, -6951036, 8252752, -4288573, -4905681, 1823836, -1592747, -10581992 }
{ -7327265, -7836741, 2848674, 5373765, 2281228, 7075271, 8223110, 7916788, 10517603, 8604950, 7799947 }
{ "ULRRURRLUUDLLR", "RRRRLRDRLLLDLDRLUDLDRLLLULRRUUULLDDDLL", "RDRRULUDLULURULRULDUUUDLLULLDLURDLUL", "UDDDDLDLDLLDRURRDR", "LRRRRLRDDLLRDRRRRRR", "LLLULLRLURLULLURLLDLULLLLDL", "RDLULD", "UUUUUURURDRURUURUURURDUUL", "LRDDLDDRLRDURRLRDDDDLDLRLL", "UUUDDDLUURRUDUDRUUDUUURDDUD", "LLLRULDLUDDDUDULDDLDRLLDDLDLDLRDLDDL" }
Returns: 124632768

Old case: { -203889, 4177249, -7903610, 4050272, -6951036, 8252752, -4288573, -4905681, 1823836, -1592747, -10581992, 6056175 } { -7327265, -7836741, 2848674, 5373765, 2281228, 7075271, 8223110, 7916788, 10517603, 8604950, 7799947, 7470398 } { "ULRRURRLUUDLLR", "RRRRLRDRLLLDLDRLUDLDRLLLULRRUUULLDDDLL", "RDRRULUDLULURULRULDUUUDLLULLDLURDLUL", "UDDDDLDLDLLDRURRDR", "LRRRRLRDDLLRDRRRRRR", "LLLULLRLURLULLURLLDLULLLLDL", "RDLULD", "UUUUUURURDRURUURUURURDUUL", "LRDDLDDRLRDURRLRDDDDLDLRLL", "UUUDDDLUURRUDUDRUUDUUURDDUD", "LLLRULDLUDDDUDULDDLDRLLDDLDLDLRDLDDL", "RLLDDLULLLULRLL" }

52)

{ 147817130, 147815290, 0, 0, 0, -147815290, -147815290, -147815290, 0, 0, 0 }
{ 0, 0, 147815290, 147815290, 147815290, 0, 0, 0, -147815290, -147815290, -147815290 }
{ "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRU", "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRUU", "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUR", "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUL", "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULL", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLU", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLD", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLDD", "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDL", "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR", "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRR" }
Returns: 1000000000000000

ans = 10^15

53)

{ 147817131, 147815290, 0, 0, 0, -147815290, -147815290, -147815290, 0, 0, 0 }
{ 0, 0, 147815290, 147815290, 147815290, 0, 0, 0, -147815290, -147815290, -147815290 }
{ "URRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR", "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRUU", "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUR", "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUL", "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULL", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLU", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLD", "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLDD", "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDL", "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR", "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRR" }
Returns: -1

ans = 10^15 + 1

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

Coding Area

Language: C++17 · define a public class AliceInWanderland with a public method long long getMinimum(vector<int> rabbitX, vector<int> rabbitY, vector<string> moves) · 55 test cases · 2 s / 256 MB per case