Lynbrook Computer Science

Announcement:

• Gunn Programming Contest

• Sign up at bit.ly/gunnproco12
• February 25th, 9am – 3pm

• Harker Invitational

• Sign up at bit.ly/harkerproco12
• March 17th, 8:30am – 3:30pm

Our full solution to last week’s PotW can be found at http://ideone.com/iC4F6, and our meeting slides can be found here. Today we presented some problems from last year’s Harker Invitational. If you wish to take a closer look to practice, the entire problem set can be found here.

The new PotW(9.2 from the packet) is as follows:

• Determine the ancestors of a node in an organization graph. Given a list of employee to boss relationships and a list of queries, determine which of the queries must be satisfied.  Each organizational line is composed of one team: the first element will be the number of employees in the group, the first name will be the boss, and each following name will be the direct employees. Each query is composed of two people: X and then Y. Determine if X must obey Y.
• The input is guaranteed to be valid: there will be no cyclic relationships, and all names will correspond properly.
• # of employees < 1000
• # of queries < 1000
• Worth 25 points
• Sample Input:
  4 (# of groups)
  2 BigBoss Amy Fred
  3 Amy Wilson Stoker Bubba
  4 Wilson James Marc Tim Alan
  2 Fred Wilma Dino
  3 (# of queries)
  Alan Dino
  Alan BigBoss
  Wilson James
• Sample Output:
  no
  yes
  no