harold de armas
cse website
In Class
2/7/2007
Okay, so I promised that I would post the code for this class soonish. I will, but for now, here is the patterned output for problem 264.
TERM 1 IS 1/1 TERM 2 IS 1/2 TERM 3 IS 2/1 TERM 4 IS 3/1 TERM 5 IS 2/2 TERM 6 IS 1/3 TERM 7 IS 1/4 TERM 8 IS 2/3 TERM 9 IS 3/2 TERM 10 IS 4/1 TERM 11 IS 5/1 TERM 12 IS 4/2 TERM 13 IS 3/3 TERM 14 IS 2/4 TERM 15 IS 1/5 TERM 16 IS 1/6 TERM 17 IS 2/5 TERM 18 IS 3/4 TERM 19 IS 4/3 TERM 20 IS 5/2 TERM 21 IS 6/1 TERM 22 IS 7/1 TERM 23 IS 6/2 TERM 24 IS 5/3 TERM 25 IS 4/4 TERM 26 IS 3/5 TERM 27 IS 2/6 TERM 28 IS 1/7 TERM 29 IS 1/8 TERM 30 IS 2/7 TERM 31 IS 3/6 TERM 32 IS 4/5 TERM 33 IS 5/4 TERM 34 IS 6/3 TERM 35 IS 7/2 TERM 36 IS 8/1 TERM 37 IS 9/1 TERM 38 IS 8/2 TERM 39 IS 7/3 TERM 40 IS 6/4
As you can see, the pattern in the numerator is to keep going up and down to an increasingly larger odd number, and the numerator keeps going up and down to an increasingly larger even number. The original problem has a different pattern and was used to construct this solution. The original pattern was to consistantly count up to and down from the same increasing number. This solution is a good example of taking an existing method and tailoring it to a desired solution.
Solution:
In Class
10/4/2006
Last week, we briefly talked about DFS and related it to a problem. The big thing I was looking to get out of the lecture was that the problems at the contest generally fall into different categories that require categorical algorithms. One key skill is to be able to identify problems and discern the algorithm required and the difficulty to implement the algorithm with the neccesary changes.
This week, we will be focusing in on more specifics. Another important skill is to be able to quickly get input and put output. In my experience, this has been through the use of C style I/O. None of that fancy 'cin' or 'cout' stuff here.
Most of the information here is boiled down from the cplusplus reference site. First things first though, #include<stdio.h>
There's two methods that you should intimately familiarize yourself with: scanf and printf. They both follow roughly the same syntax, function("string", arguments). The format string specifies how you will either read in the data or print out the data.
The string is the complicated part, but it becomes quite easy as soon as you get it. For scanf (reading in data) the string is a string as expected and will read in data, but as soon as it hits a special token in the string, it will read the data how you want it. The full syntax for the "tokens" is as follows:
%[*][width][mod]type
The type is most commonly i (integer), c (character), f (float), s (string), or x (hex). The modifier changes if it will read in short or long values for numbers. The width specifies the maximum number of characters to read if whitespace isn't encountered first. An optional * may be added and the argument will be ignored when trying to assign. The biggest thing to remember is the function assigns to an address, so you need to use a & for all of those declared variables.
For printf, there isn't much difference. The format string looks like this:
%[flag][width][.precision][mod]type
The types and the mods allowed are pretty much the same. The precision will specify the minimum number of digits in an integer displayed, the number of decimal places in a float, and the maximum number of characters in a string. The width specifies the width of the display for the integers, padded with whitespace, or zeros if led by a zero. The flag can be - or +, - will left align to the column width and + will force a sign on signed numbers.
Lastly for C I/O, sscanf and sprintf does all of the same things, except they expect a first argument of the string to read from or print to.
P.S., I was re-browsing the time library and I found this nifty piece of code that might prove useful in the time calcuation type problems.
/* mktime example: weekday calculator */
#include <stdio.h>
#include <time.h>
int main ()
{
time_t rawtime;
struct tm * timeinfo;
int year, month ,day;
char * weekday[] = { "Sunday", "Monday",
"Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday"};
/* prompt user for date */
printf ("Enter year: "); scanf ("%d",&year);
printf ("Enter month: "); scanf ("%d",&month);
printf ("Enter day: "); scanf ("%d",&day);
/* get current timeinfo and modify it to user's choice */
time ( &rawtime );
timeinfo = localtime ( &rawtime );
timeinfo->tm_year = year - 1900;
timeinfo->tm_mon = month - 1;
timeinfo->tm_mday = day;
/* call mktime: timeinfo->tm_wday will be set */
mktime ( timeinfo );
printf ("That day is a %s.\n", weekday[timeinfo->tm_wday]);
return 0;
}
In Class
9/20/2006
Hey everyone, just bear with me for the time being as the content for this group is being created as I come up with it.
The programming contest is a timed event where teams of three are given a set of problems to attempt. Scoring is based on the number of problems solved, the time required to complete the problems, and the number of incorrect submissions is weighted against the time as well.
Skills that are useful during the contest are of course fast thinking, but not only about solutions. Given a set of problems, you should be able to identify the difficulty of all of the problems quickly. The for each of the problems, you should be able to determine the algorithm that is required to solve the problem. Most of the problems given can be organized into groups based on the solution required for each of them. Examples of categories are:
- Sorting
- Exhaustive Search
- Graph Theory
- Dynamic Programming
- Greedy Algorithms
- Computational Geometry
- Number Theory
From: Algorithmist.
Once the right method to solve the problem can be identified, the solution is a matter of modifying the algorithm to suit your needs.
Another useful skill is the quick preparation of problems. Most of the programming contest questions require you to read in a certain amount of input and generate the desired output for a number of test cases. The overall structure of each program is going to be very similar. For Example...
int main()
{
while(casesleft)
{
getinput;
procoutput;
}
}
Since all of the input and output is handled through STDIN and STDOUT, get yourself familiar with it. I know that in your CS classes you learn how to do C++ I/O and are very familiar with
cout<<"Hello World";
Now it's time to get used to
printf("Hello World")
Alot of the problems will require you to print out numbers to three decimal places that are left aligned to five places with another hex values in paranthesis. I'd love to see the cout statement for that... Until you figure that out though, I'll give you
printf("%-5.3f(%X)", f, i)
Much quicker to come up with, no setting flags, and I now have time to move on to bigger and better things.
The last skill that we'll need to develop is the identification of "killer cases." The judge of these contests want to make the problems difficult, and another way they accomplish that is to come up with off the wall cases that no one in their right mind would think of.
To get everyone into the swing of things, go ahead and try problems 105 and 130 on the Problemset to warm up.
After Class
9/20/2006
Find a problem on acm.uva.es and solve it according to your skill level.
- CS 202 or Below - Any Problem
- Sophomores < 40%
- Juniors/Seniors < 30%
- Grad < 20%
Try to get the submission to work online and e-mail me the problem number and your solution with the online judge's response before next week's meeting so I can post them online and we can discuss them. As always, comments are welcome!
Registration information
for acm.uva.es online judge
If you don't already have an account, go to the acm.uva.es Problemset site, click Register on the left, and Follow all of the instructions.
Once you've created an account, you can submit problems for grading in the online judge. After completing and testing your code, go to the acm.uva.es Problemset site and click to submit your code.