<html>
<head>
<META HTTP-EQUIV="Pragma" CONTENT="no-cache">
<META HTTP-EQUIV="Expires" CONTENT="-1">
<title> note page </title>
</head>
<body bgcolor=#ffffff>
<pre>
TopCoder Collegiate Challenge > NE and SE Regional Round
Tuesday, February 18 2003
Problem Set Analysis & Opinion
The first problem set of the collegiate challenge turned out to be a little bit trickier than previous first round problem sets have been, though still easier than the average division 1 problem set. Only 191 people competed from the two regions, and of those only 113 ended up with positive points - 78 from the northeast, and 35 from the southeast. dgarthur was able to complete all three of the problems in an impressive 35 minutes, and with 50 points from the challenge phase, he easily took first. In second, 160 points behind, is insomnia, with 4 successful challenges. Good luck to everyone in the next round!
NameSort
Used as: Level 1:
Value 250
Submission Rate 160 / 191 (83.77%)
Success Rate 98 / 160 (61.25%)
High Score ColinMacLeod for 239.72 points
Sorting can be done in a variety of ways. The simplest way to implement it in this case, where runtime is not an issue, is probably to simply use two loops:
for i = 1 to n
for j = 1 to i-1
if(element i should come before element j)
swap elements i and j
To tell if one element should come before another, you simply have to tokenize each element, and compare the final tokens, ignoring case. If there is a tie, you need to know the original index, so you should probably keep track of the indices and swap them along with the elements.
RoadWork
Used as: Level 2:
Value 500
Submission Rate 89 / 191 (55.28%)
Success Rate 46 / 89 (51.69%)
High Score niteneb for 471.50 points
If the roads were shorter, it would be easy to iterate through each one foot section of road, and check to see if it is included in multiple contracts. However, since the roads are up to 2 billions feet long, this is clearly not an option. Instead, we should divide the roads into a number of segments, and then determine if each segment is contained within multiple contracts, and then add the length of the whole segment, if it is all covered by multiple contracts. The trick is to pick the segments so that the whole segment is guaranteed to be covered by the same number of contracts. One simple way to do this is to add all of the points in start and end into one array, and sort that array. The segments of interest will now be defined as the region between adjacent elements in the array. It should be clear that there is no way for only part of one of these segments to be covered by multiple contracts. Now that way have defined our segments, it is simple to test each of the segments to see if it's covered:
all = union(start,end)
sort(all)
ret = 0
for i = 0 to all.size-2
count = 0
for j = 0 to start.size-1
if(start[j]<=all[i] && end[j] >= all[i+1])
count = count + 1
if(count > 1)ret = ret + all[i+1]-all[i]
TupleLine
Used as: Level 3:
Value 1000
Submission Rate 20 / 191 (10.47%)
Success Rate 12 / 20 (60.00%)
High Score dgarthur for 708.62 points
Like any line, a line here is defined by two points. As a result, the simplest way to do this is to pick two points, and examine the line defined by those two points. The first thing to check is that the line is maximal. This is probably the hardest part of the problem, but it is not very algorithmically difficult. First, you should find the distance tuple between the two points. Each non-zero element of distance tuple should have the same absolute value. If this is not the case, then the two points cannot lie along a maximal line. For example, (0,0) and (1,2) cannot lie along a maximal line because the slope of the line is 2, and thus when the line traverses an n by n box, it will hit only n/2 cells. Once you have done this, you still have to check that the length of the line is the same as the size of the box. For example, if the size of the box is 3, and two points are (0,1) and (1,2), the line through them does not include 3 points, only 2. One way to do this is to generate all of the points along the line, and count them. There are other ways to do this too, but generating the points is probably a good way to do it, since this lets you count the total points easily. Once you have generated the points along the line, you simply iterate through all of the points and count how many were given to you. AdminBrett wrote the shortest solution I have seen, though it takes a minute to see how it works:
public class TupleLine {
public int quickLine(int size, String[] chosen) {
int ret = size-1;
for (int i = 0; i < chosen.length; i++) {
for (int j = i+1; j < chosen.length; j++) {
int[] curri = new int[chosen[j].length()], currj = new int[curri.length], diff = new int[curri.length];
int div = 1000, cntused = 0, cntunused = 0;
for (int x = 0; x < diff.length; x++) {
curri[x] = chosen[i].charAt(x)-'0';
currj[x] = chosen[j].charAt(x)-'0';
diff[x] = curri[x]-currj[x];
while (diff[x]%div!=0) div--;
} for (int x = 0; x < diff.length; x++) diff[x] /= div;
outer:for (int x = -10; x <= 10; x++) {
int[] temp = (int[])diff.clone();
for (int y = 0; y < temp.length; y++) {
temp[y] = curri[y]+x*
</pre>
</body>
</html>
Linux System Admin Tips: There are over 200 Linux tips and tricks in this article. That is over 100 pages covering everything from NTP, setting up 2 IP address on one NIC, sharing directories among several users, putting running jobs in the background, find out who is doing what on your system by examining open sockets and the ps command, how to watch a file, how to prevent even root from deleting a file, tape commands, setting up cron jobs, using rsync, using screen conveniently with emacs, how to kill every process for a user, security tips and a lot more. These tip grow weekly. The above link will download the text version for easy grep searching. There is also an html version here.
Breaking Firewalls with OpenSSH and PuTTY: If the system administrator deliberately filters out all traffic except port 22 (ssh), to a single server, it is very likely that you can still gain access other computers behind the firewall. This article shows how remote Linux and Windows users can gain access to firewalled samba, mail, and http servers. In essence, it shows how openSSH and Putty can be used as a VPN solution for your home or workplace.
MySQL Tips and Tricks: Find out who is doing what in MySQL and how to kill the process, create binary log files, connect, create and select with Perl and Java, remove duplicates in a table with the index command, rollback and how to apply, merging several tables into one, updating foreign keys, monitor port 3306 with the tcpdump command, creating a C API, complex selects, and much more.
Create a Live Linux CD - BusyBox and OpenSSH Included: These steps will show you how to create a functioning Linux system, with the latest 2.6 kernel compiled from source, and how to integrate the BusyBox utilities including the installation of DHCP. Plus, how to compile in the OpenSSH package on this CD based system. On system boot-up a filesystem will be created and the contents from the CD will be uncompressed and completely loaded into RAM -- the CD could be removed at this point for boot-up on a second computer. The remaining functioning system will have full ssh capabilities. You can take over any PC assuming, of course, you have configured the kernel with the appropriate drivers and the PC can boot from a CD. This tutorial steps you through the whole processes.
SQLite Tutorial : This article explores the power and simplicity of sqlite3, first by starting with common commands and triggers, then the attach statement with the union operation is introduced in a way that allows multiple tables, in separate databases, to be combined as one virtual table, without the overhead of copying or moving data. Next, the simple sign function and the amazingly powerful trick of using this function in SQL select statements to solve complex queries with a single pass through the data is demonstrated, after making a brief mathematical case for how the sign function defines the absolute value and IF conditions.
The Lemon Parser Tutorial: This article explains how to build grammars and programs using the lemon parser, which is faster than yacc. And, unlike yacc, it is thread safe.
How to Compile the 2.6 kernel for Red Hat 9 and 8.0 and get Fedora Updates: This is a step by step tutorial on how to compile the 2.6 kernel from source.
Virtual Filesystem: Building A Linux Filesystem From An Ordinary File. You can take a disk file, format it as ext2, ext3, or reiser filesystem and then mount it, just like a physical drive. Yes, it then possible to read and write files to this newly mounted device. You can also copy the complete filesystem, since it is just a file, to another computer. If security is an issue, read on. This article will show you how to encrypt the filesystem, and mount it with ACL (Access Control Lists), which give you rights beyond the traditional read (r) write (w) and execute (x) for the 3 user groups file, owner and other.
Working With Time: What? There are 61 seconds in a minute? We can go back in time? We still tell time by the sun?
Mike Chirico, a father of triplets (all girls) lives outside of
Philadelphia, PA, USA. He has worked with Linux since 1996, has a Masters
in Computer Science and Mathematics from Villanova University, and has
worked in computer-related jobs from Wall Street to the University of
Pennsylvania. His hero is Paul Erdos, a brilliant number theorist who was
known for his open collaboration with others.
Mike's notes page is souptonuts. For
open source consulting needs, please send an email to
mchirico@gmail.com. All consulting work must include a donation to
SourceForge.net.
