Massive Algorithms: Problem A. Bot Trust - Qualification Round 2011

Dashboard - Qualification Round 2011 - Google Code Jam

Problem

Blue and Orange are friendly robots. An evil computer mastermind has locked them up in separate hallways to test them, and then possibly give them cake.
Each hallway contains 100 buttons labeled with the positive integers {1, 2, ..., 100}. Button k is always k meters from the start of the hallway, and the robots both begin at button 1. Over the period of one second, a robot can walk one meter in either direction, or it can press the button at its position once, or it can stay at its position and not press the button. To complete the test, the robots need to push a certain sequence of buttons in a certain order. Both robots know the full sequence in advance. How fast can they complete it?
For example, let's consider the following button sequence:
O 2, B 1, B 2, O 4
Here, O 2 means button 2 in Orange's hallway, B 1 means button 1 in Blue's hallway, and so on. The robots can push this sequence of buttons in 6 seconds using the strategy shown below:

Time | Orange           | Blue
-----+------------------+-----------------
  1  | Move to button 2 | Stay at button 1
  2  | Push button 2    | Stay at button 1
  3  | Move to button 3 | Push button 1
  4  | Move to button 4 | Move to button 2
  5  | Stay at button 4 | Push button 2

  6  | Push button 4    | Stay at button 2

Note that Blue has to wait until Orange has completely finished pushing O 2 before it can start pushing B 1.

Input

The first line of the input gives the number of test cases, T. T test cases follow.
Each test case consists of a single line beginning with a positive integer N, representing the number of buttons that need to be pressed. This is followed by N terms of the form "R_i P_i" where R_i is a robot color (always 'O' or 'B'), and P_i is a button position.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of seconds required for the robots to push the given buttons, in order.

Limits

1 ≤ P_i ≤ 100 for all i.

Small dataset

1 ≤ T ≤ 20.
1 ≤ N ≤ 10.

Large dataset

1 ≤ T ≤ 100.
1 ≤ N ≤ 100.

Input	Output
`3 4 O 2 B 1 B 2 O 4 3 O 5 O 8 B 100 2 B 2 B 1`	`Case #1: 6 Case #2: 100 Case #3: 4`

Official Analysis: https://code.google.com/codejam/contest/975485/dashboard#s=a&a=0
Anyway, if you think about this problem from the perspective of a single robot, the strategy should be pretty intuitive: always move towards the next button and then push it as soon as it comes up in the sequence.

So the most natural solution to this problem is a straight simulation:

Keep track of which buttons have been pressed, and look ahead in the sequence to figure out which button is next for each robot.
One second at a time, have each robot move towards its next button.
Once it gets to the button, the robot should push it if it's next in the sequence, and just wait otherwise.

At most 100 buttons needs to be pressed altogether and the distance between buttons is at most 100, so this solution will run plenty fast.

http://blog.chinaunix.net/uid-20520151-id-3069061.html

两个99米的长廊每隔1m放置一个button，机器人O和B分别在两个长廊的第一个button处。机器人向前移动一格耗费一秒，向后移动一格也耗费一秒，按下button也要耗费一秒，停留在原地等待的时间也是以秒为单位的。两个机器人互不干扰，但是一个机器人O，必须等待另一个机器人B做完当前所有动作并按下按钮后才能按下按钮，而按按钮之前可以随意的移动和等待。现在要根据给定的输入顺序，求出两个机器人完成动作的时间总和。

Solution:
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for(int zz = 1; zz <= T;zz++){
int N = in.nextInt();
int bat = 1;
int oat = 1;
int btime = 0;
int otime = 0;
for(int i = 0; i < N;i++){
if(in.next().equals("B")){
int next = in.nextInt();
btime = max(btime+abs(bat-next), otime)+1;
bat = next;
}else{
int next = in.nextInt();
otime = max(otime+abs(oat-next), btime)+1;
oat = next;
}
}
System.out.format("Case #%d: %d\n", zz, max(btime, otime));
}
}
http://vairoj.com/2011/05/google-code-jam-2011-my-take-on-bot-trust.html


	def min_time(directive): """directive -- the button pushing sequence e.g.
	[('O',2),('B',1),('B',2),('O',4)]
	"""
	bot = { 'O': (0, 1), # (time, position)
	'B': (0, 1) }
	time = 0
	for b, loc in directive:
	distance = abs(bot[b][1] - loc)
	time = max(time, bot[b][0] + distance) + 1
	bot[b] = (time, loc)
	return time

	def main():
	num_tests = int(sys.stdin.readline())
	for t in range(1, num_tests + 1):
	line = sys.stdin.readline().split()
	line.pop(0) # ignore number of steps, can be infered
	directive = zip(line[::2], [int(x) for x in line[1::2]])
	mtime = min_time(directive)
	print "Case #%d: %d" % (t, mtime)

http://algorithmsquestionsforinterviews.blogspot.com/2013/03/day-24-bot-trust.html
Read full article from Dashboard - Qualification Round 2011 - Google Code Jam

Problem A. Bot Trust - Qualification Round 2011 - Google Code Jam