1622 - Robot

All about problems in Volume 16. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

1622 - Robot

Post by brianfry713 » Mon Apr 21, 2014 9:02 pm

Input:

Code: Select all

4 7
8 6 4 6
7 3
10 2 3 8
1 10
4 7 1 7
3 7
2 9 8 10
3 1
3 4 8 6
10 3
3 9 10 8
4 7
2 3 10 4
2 10
5 8 9 5
6 1
4 7 2 1
7 4
3 1 7 2
6 6
5 8 7 6
7 10
4 8 5 6
3 6
5 8 5 5
4 1
8 9 7 9
9 5
4 2 5 10
3 1
7 9 10 3
7 7
5 10 6 1
5 9
8 2 8 3
8 3
3 7 2 1
7 2
6 10 5 10
0 0
AC output:

Code: Select all

Case 1: 493
Case 2: 226
Case 3: 67
Case 4: 402
Case 5: 17
Case 6: 585
Case 7: 376
Case 8: 338
Case 9: 58
Case 10: 220
Case 11: 721
Case 12: 1330
Case 13: 283
Case 14: 55
Case 15: 671
Case 16: 34
Case 17: 737
Case 18: 597
Case 19: 235
Case 20: 248
Check input and AC output for thousands of problems on uDebug!

12061160
New poster
Posts: 7
Joined: Mon Jul 21, 2014 10:38 am

Re: 1622 - Robot

Post by 12061160 » Mon Jul 21, 2014 8:05 pm

still WA...could you give me some logic thoughts? :oops:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1622 - Robot

Post by brianfry713 » Tue Jul 22, 2014 7:16 pm

In this and many problems I solved it by writing a random test case generator for small input values (<= 10), then a brute force solution using backtracking that would TLE for large input values, and then work on getting correct code that will run in the time limit.
To simplify I swapped equivalent values to make NORTH >= SOUTH, and WEST >= EAST.
Then there are two main cases to handle: the first move north or the first move west. You should try both and see which gives a larger answer.
If your first move is north then you keep moving south then north until you run out of south moves. After that make a move west then keep moving east then west until you run out of east moves.
Now your only remaining moves are north and west. If the height of the remaining grid of robots is >= width then move north, otherwise move west. Continue until your run out of robots or run out of moves.
Check input and AC output for thousands of problems on uDebug!

12061160
New poster
Posts: 7
Joined: Mon Jul 21, 2014 10:38 am

Re: 1622 - Robot

Post by 12061160 » Wed Jul 23, 2014 1:40 pm

Already AC!Thanks for random test cases~~
brianfry713 wrote:In this and many problems I solved it by writing a random test case generator for small input values (<= 10), then a brute force solution using backtracking that would TLE for large input values, and then work on getting correct code that will run in the time limit.
To simplify I swapped equivalent values to make NORTH >= SOUTH, and WEST >= EAST.
Then there are two main cases to handle: the first move north or the first move west. You should try both and see which gives a larger answer.
If your first move is north then you keep moving south then north until you run out of south moves. After that make a move west then keep moving east then west until you run out of east moves.
Now your only remaining moves are north and west. If the height of the remaining grid of robots is >= width then move north, otherwise move west. Continue until your run out of robots or run out of moves.

Post Reply

Return to “Volume 16 (1600-1699)”