EppsNet Archive: Programming

Competitive Programming: POJ 2195 – Going Home

Description On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man. Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a ‘.’ means an empty space, an ‘H’ represents a house on that point, and am ‘m’ indicates there is a little man on that point. You can think of each point on the grid map as a quite large square, so it can… Read more →

Competitive Programming: POJ 3169 – Layout

Description Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate). Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like… Read more →

Competitive Programming: POJ 1125 – Stockbroker Grapevine

Description Stockbrokers are known to overreact to rumors. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge in the stock market. For maximum effect, you have to spread the rumors in the fastest possible way. Unfortunately for you, stockbrokers only trust information coming from their “Trusted sources” This means you have to take into account the structure of their contacts when starting a rumor. It takes a certain amount of time for a specific stockbroker to pass the rumor on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumor, as well as the time it will take for the rumor to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive… Read more →

Competitive Programming: POJ 2488 – A Knight’s Journey

Description Background The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans? Problem Find a path such that the knight visits every square once. The knight can start and end on any square of the board. Input The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such… Read more →

Competitive Programming: POJ 1159 – Palindrome

Description A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome. As an example, by inserting 2 characters, the string “Ab3bd” can be transformed into a palindrome (“dAb3bAd” or “Adb3bdA”). However, inserting fewer than 2 characters does not produce a palindrome. Input Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from ‘A’ to ‘Z’, lowercase letters from ‘a’ to ‘z’ and digits from ‘0’ to ‘9’. Uppercase and lowercase letters are to be considered distinct.… Read more →

Competitive Programming: POJ 2663 – Tri Tiling

Description In how many ways can you tile a 3xn rectangle with 2×1 dominoes? Here is a sample tiling of a 3×12 rectangle. Input Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30. Output For each test case, output one integer number giving the number of possible tilings. Sample Input 2 8 12 -1 Sample Output 3 153 2131 Link to problem Solution below . . . Read more →

Developers Should Abandon Agile

No matter what framework or method your management thinks they are applying, learn to work this way: Produce running, tested, working, integrated software every two weeks, every week. Build your skills until you can create a new fully operational version every day, twice a day, multiple times a day. Keep the design of that software clean. As it grows, the design will tend to become complex and crufty. Resist and reverse this tendency consciously, refactoring in tiny continuous steps, all the time, so that your rate of progress is as steady and consistent as possible. Use the current increment of software as the foundation for all your conversations with your product leadership and management. Speak in terms of what’s ready to go, and in terms of what they’d like you to do next. This is the development team’s best hope for a reasonable life. By keeping the software always ready… Read more →

Competitive Programming: POJ 1426 – Find The Multiple

Description Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits. Input The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input. Output For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable. Sample Input 2 6 19 0 Sample Output 10 100100100100100100 111111111111111111 Link to problem Solution below . . . Read more →

Competitive Programming: POJ 2084 – Game of Connections

Description This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, . . . , 2n – 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect. It’s still a simple game, isn’t it? But after you’ve written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right? Input Each line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 < = n Read more →

Competitive Programming: USACO Big Barn

Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal or vertical axis. EXAMPLE Consider the following grid of Farmer John’s land where ‘.’ represents a parcel with no trees and ‘#’ represents a parcel with trees: 1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # .… Read more →

Competitive Programming: POJ 1654 – Area

Description Consider an infinite full binary search tree (see the figure below), the numbers in the nodes are 1, 2, 3, …. In a subtree whose root node is X, we can get the minimum number in this subtree by repeating going down the left node until the last level, and we can also find the maximum number by going down the right node. Now you are given some queries as “What are the minimum and maximum numbers in the subtree whose root node is X?” Please try to find answers for the queries. Input In the input, the first line contains an integer N, which represents the number of queries. In the next N lines, each contains a number representing a subtree with root number X (1 Read more →

Competitive Programming: POJ 2242 – The Circumference of the Circle

Description To calculate the circumference of a circle seems to be an easy task – provided you know its diameter. But what if you don’t? You are given the cartesian coordinates of three non-collinear points in the plane. Your job is to calculate the circumference of the unique circle that intersects all three points. Input The input will contain one or more test cases. Each test case consists of one line containing six real numbers x1,y1,x2,y2,x3,y3, representing the coordinates of the three points. The diameter of the circle determined by the three points will never exceed a million. Input is terminated by end of file. Output For each test case, print one line containing one real number telling the circumference of the circle determined by the three points. The circumference is to be printed accurately rounded to two decimals. The value of pi is approximately 3.141592653589793. Sample Input 0.0 -0.5… Read more →

Teaching Computer Science: How to Get Top-Notch Teachers in the Classroom

I read something every day where educators and/or elected officials are talking about the importance for our kids, our country, our future, etc., of teaching computer science, the sticking point being an extreme shortage of qualified teachers. A person entering the workforce with a computer science degree is unlikely to go into teaching because of the opportunity cost: they can earn a lot more money as a software engineer. The likelihood of getting a mid-career tech industry professional to switch into teaching is even lower. Teacher salaries are based in large part on years of service. A mid-career person switching into teaching is not going to get a mid-career teacher’s salary, they are going to get a first-year teacher’s salary. So here’s the idea: Give CS professionals the opportunity to apply their years in industry to years of service as a teacher. It’s still a pay cut going from software… Read more →

Teaching Computer Science: The Phones Aren’t Helping You

I’m volunteering a couple mornings a week at a local high school, helping out with computer science classes. The way the classes are taught, via an online curriculum, provides a great temptation to kids to get off-task, which they do, usually by entertaining themselves with their phones. They get off-task in other ways too — web surfing, doing homework for other classes — but the main distractor is the phones . . .   “As I mentioned before, I worked with another CS class a couple years ago. No phones allowed in the classroom. “I remember one day the assistant principal was in class observing . . . a student had a phone out, looking at it . . . he was holding it under the table so no one could see it, but this guy, the assistant principal, he did see it. “Oh man, did he hit the roof!… Read more →

Teaching Computer Science: When You Need Help, Ask For Help

I’m volunteering a couple mornings a week at a local high school, helping out with computer science classes. It’s a mixed class . . . most of the students are taking AP Computer Science Principles, and about 10 kids just recently started a second-semester Visual Basic class. The VB kids were pretty inquisitive at first but started to get discouraged . . . in my opinion because of the way the material is presented to them via an online curriculum. The current approach to teaching computer science in American schools, because of the shortage of (I almost said “lack of”) qualified teachers is to use packaged courses delivered to students online. My observation is students assume that because they’ve been put in front of a computer full of lessons, they’re expected to be able to read and understand the material and complete the assignments on their own with no help.… Read more →

Teaching Computer Science: Asking for Help

I’m volunteering a couple mornings a week at a local high school, helping out with computer science classes. This morning, in AP Computer Science Principles, the teacher went through an explanation of the hexadecimal number system, then gave an in-class assignment for students to convert their cell phone number to hexadecimal. Not in two parts, 3 digits and 4 digits, but as a 7-digit number. It seemed pretty obvious from the interaction and the body language and the looks on their faces that a lot of students didn’t get it, but in a class of 25 students, only one student asked for help. Until the teacher finished with that student and asked “Does anyone else need help?” and eight more students immediately raised their hand. I asked the teacher, “Can I address the class for a minute?”   “First off, doing a 7-digit hex conversion is not easy. I know… Read more →

Teaching Computer Science: It’s Not Easy to Teach a Subject in Which You Have No Training

A recent issue of Science has an article on the pipeline for computer science teachers . . . The first sentence says, “It’s not easy to teach a subject in which you have no training.” That could be the whole article, really. That’s about all you need to know about the current state of computer science instruction: It’s not easy to teach a subject in which you have no training. Cameron Wilson, chief operating officer and president of the Code.org Advocacy Coalition, is quoted as saying, “It’s really hard to convince a computer science professional to give up a job that pays up to three times more to pursue teaching. And I don’t think we should.” Wilson’s opinion that computer science classes should not be taught by someone who actually knows something about computer science is probably influenced by the fact that Code.org is one of the leading providers of… Read more →

More Words and Phrases I’m Sick Unto Death Of

Although I can’t claim never to have said these things myself, if I had a dollar for every time I’ve heard someone say either a) “It was working fine 10 minutes ago,” or b) “It works okay on my machine,” I would be comfortably retired by now. Thus spoke The Programmer. Read more →

What Does a Programmer Do?

I was asked to give a talk last week to a high school computer science class on “What Does a Programmer Do?” (I’m indebted to Jim McCarthy for the “lords and ladies of logic” section.)   Programming is problem solving. At the highest level, the problem that programmers solve is that people want to be able to do things with computers that they can’t do. And by computers, I don’t mean just the kind of computers you have on the desks here, I mean phones, watches, cars . . . more and more different kinds of devices are running software. So one good thing about being a programmer is that pretty much every field of endeavor now uses software and data. You can work at a tech company like Microsoft or Google or Twitter or Facebook, but you can also work in healthcare, finance, education, sports . . . you… Read more →

I’m a Winner!

I’ve been doing the daily challenges at CodeFights for quite a while and yesterday’s challenge is the first time I got first place! (CodeFights ranks solutions by fewest number of characters, with solution time as the tiebreaker.) Read more →

« Previous PageNext Page »