Lynbrook Computer Science

Today the officer team went over last meeting’s PotW(thanks Jimmy!) and some USACO problems from past two rounds; our explanations can be found here.

There is no PotW this week since we will announce the top scorers of first semester next week. Just don’t forget to code on your own. ☺

Welcome to a new semester of school and, of course, of CS Club!

Today we discussed one possible solution to the Problem of the Week (the problem actually lasted an entire month), and presented Dijkstra’s Algorithm.

The new Problem of the Week is as follows:

• Today, Bessie wants to take a trip to a city, but doesn’t know where yet. She has x dollars to spend, and the airline she is using charges $1 per mile. Tell her how many cities she might be able to visit, if she starts at node #1. Please note that all possible flights are one-way only, and after visiting her destination, she must also return. She can also take as many flights as she wants. Please also include node #1 in your count.
• Assume that every city is visitable from every other city given an infinite amount of money.
• Also assume that all plane flight distances are less than 1000.
• Let N=# of cities, and M=# of flights.
• For 25 points, solve for N<100 and M<100
• For 40 points, solve for N<10000 and M<100000

Sample input:
11   (x)
4 6   (# of cities, # of flights)
1 2 1   (flight #1: city #1, city #2, then distance in miles)
2 3 3   (flight #2)
1 3 6   (etc.)
3 1 7
3 4 6
4 1 2
Sample output:
3 (she can visit nodes #1,2, or 3, but not 4)

The problem can also be found, along with some hints, in the meeting slides.

Note that today is the last day to take the January USACO! Because the problems are harder this month, you are given four hours for the contest, rather than three. As usual, participation counts for 5 points towards your PotW score. Happy coding!

As the last meeting of this semester, today’s meeting was brief. We went over the solution to last week’s Problem of the Week(credits to Qingqi), and introduced the new problem, which is as follows:

• Farmer John wants to create a scenic trail on his field, and has hired you. To maximize your pay, make the trail as long as possible.
• However, his field has trees on it, and he refuses to cut them down because he is environmentally conscious. Trees are denoted with “Y”, and empty spaces are denoted with “.”.
• The trail starts at the top left corner and cannot intersect with itself (it is NOT a loop)

Sample Input:                   Sample Output (not optimal):
4 5    (rows columns)      RRRRDLLDDLULD
…..
.Y…
…Y.
…..

• The time limit is 10 seconds, and the dimensions of the grid are less than 80. Since it is impossible to consistently generate the optimal solution within a reasonable amount of time, scoring will be relative to your placing out of all submissions: the kth best will receive 54-3*k points, with ties rounding up.

Because the problem is quite challenging, you will have about a month to solve it. Please submit your solution by 1/8/2012 11:59 PM. This is our last PotW of this semester, so make sure you do it! We will have cool prizes!

Last but not least, remember to take the second round of USACO this coming weekend. Just like last time, you will receive 5 points for participating.

Our meeting slides with hints can be found here, and good luck on your finals!

CS Club will resume on 1/9/2012.

In today’s meeting, we went over last week’s PotW solution and  a couple searching algorithms. We focused mainly on depth-first search(DFS) and breadth-first search(BFS). Regarding these search algorithms and graph theory, more information and pseudocode can be found in our meeting slides. The new PotW is:

• This problem has nothing to do with cows, but for some reason cows are nodes, and friendships are edges. Check if the graph is a tree.
• Each edge is undirected, since friendships are mutual (hopefully)
• A tree is a graph such that all nodes are connected and there is only one unique way to get between each two nodes
• The first line of the input contains the number of nodes (less than 1,000,000) and then the number of edges (also less than 1,000,000)
• Each successive line contains an edge, and has two indices, where indices are numbered starting from one
• The output should be either “YES” or “NO”
• Sample Input:
  3 2
  1 2
  2 3
• Sample Output:
  YES

The entire problem is worth 30 points.

The November USACO is over, and preliminary results have been released! Good job to everyone who participated!

In today’s meeting, we went over solutions to one bronze, one silver, and one gold division problem from the last USACO. We also went over the solution to last week’s Problem of the Week, and introduced the new problem, which is as follows:

• One day, at school, Bessie wrote a string of matching ‘(‘s and ‘)’s. As soon as she got home, however, she noticed that she had definitely made some mistakes!
• She plans on covering this up by simply erasing some of the parentheses on the left and right, while aiming for the longest substring.
• The substring she obtains must be a valid sequence of parentheses – each ‘(‘ must match to a ‘)’ to its right, and vice versa. Tell Bessie the length of the longest valid substring.

• For 15 points, implement a solution for length < 100.
• For 25 points, length < 1,000.
• For 35 points, length < 1,000,000.

For input/output examples, and to look over the solutions presented at this meeting, see the meeting slides.

In today’s meeting, we gave a brief introduction to artificial intelligence and some of its many applications, and also introduced a new Problem of the Week, which is as follows:

In an effort to swindle his cows, Farmer John has devised a (not so) brilliant game to play against Bessie. Bessie, compensating for her bovine intelligence, pays you with milk to write a program that helps play for her.
The game begins with n stacks of coins and m_i coins in each stack, and Farmer John graciously lets Bessie go first. If each player takes 1 to k coins from one stack on each turn, and the player who takes the last coin out of all stacks wins, determine who will win assuming optimal play.

For 15 points, solve the problem for n=1 (1 stack of coins).
For 15 more points, solve the problem for 1 < n < 1,000,000
All integers in the input are less than 1,000,000 in magnitude.

Sample Input:
1 2 (one stack, take up to two coins at a time)
6 (the stack has six coins)
Sample Output:
John (either “John” or “Bessie”)

For more sample input/output examples, and a helpful hint, see the meeting slides.

As a reminder, if you haven’t taken USACO yet, you still have until the end of today to take it! Remember, USACO participation counts for 5 points towards your PotW score, so if you have time you really should take it!

Happy Halloween! Today we went over greedy algorithms and when and when not to use them. We also went over two solutions to the previous Problem of the Week and introduced the new Problem of the Week. The new PotW is as follows:

• It’s Monday, and Halloween, so naturally, the cows are out partying. Bessie has a list of N<100,000 parties and their start/end times (in 24 hr format), and she wants to maximize the number of parties she attends, k. She must attend the entirety of each party.
• Note that the parties are sorted by end time (VERY important).

Sample Input:
4
0:00 0:05
0:00 0:10
0:05 0:15
0:15 0:20
Sample Output: (print out k on a single line)
3

• This is worth 20 pts, but for 15 extra pts, print out on a second line the maximum amount of time she can spend attending k parties (fairly difficult).

To learn how to apply a greedy algorithm to the problem of the week, check out the meeting slides. As a hint for the extension, you can use dynamic programming and binary search – don’t worry if you can’t solve it though, it’s designed as a tiebreaker.