Competitive Programming: SPOJ – Build the Fence

At the beginning of spring all the sheep move to the higher pastures in the mountains. If there are thousands of them, it is well worthwhile gathering them together in one place. But sheep don’t like to leave their grass-lands. Help the shepherd and build him a fence which would surround all the sheep. The fence should have the smallest possible length! Assume that sheep are negligibly small and that they are not moving. Sometimes a few sheep are standing in the same place. If there is only one sheep, it is probably dying, so no fence is needed at all …

Input

t [the number of tests <= 100]
[empty line]
n [the number of sheep <= 100000]
x1 y1 [coordinates of the first sheep]

xn yn
[integer coordinates from -10000 to 10000]
[empty line]
[other lists of sheep]

Text grouped in [ ] does not appear in the input file. Assume that sheep are numbered in the input order.

Output

o [length of circumference, rounded to 2 decimal places]
p1 p2 … pk
[the sheep that are standing in the corners of the fence; the first one should be positioned bottommost and as far to the left as possible, the others ought to be written in anticlockwise order; ignore all sheep standing in the same place but the first to appear in the input file; the number of sheep should be the smallest possible]
[empty line]
[next solutions]

Example

Input:
8

5
0 0
0 5
10 5
3 3
10 0

1
0 0

3
0 0
1 0
2 0

4
0 0
0 0
0 1
1 0

3
0 0
0 1
1 0

6
0 0
-1 -1
1 1
2 2
3 3
4 4

2
10 0
0 0

7
-3 -4
2 -3
4 3
-4 2
0 5
2 -3
-1 4

Output:
30.00
1 5 3 2

0.00
1

4.00
1 3

3.41
1 4 3

3.41
1 3 2

14.14
2 6

20.00
2 1

26.98
1 2 3 5 4

Warning: large Input/Output data, be careful with certain languages

Link to problem

Solution below . . .

Read more

Teaching Computer Science: You Just Got to Really Want To

I’m volunteering a couple mornings a week in a high school computer science class . . .

Vladimir Horowitz

“Does anyone recognize this gentleman?” No one does. “Any pianists in the class?” About 5 kids raise their hands. “Do you ever go to YouTube and watch videos of pieces that you’re trying to learn?” Yes, they do.

“Ok, this is Vladimir Horowitz.” Last time around, no one was able to identify Martha Graham.

“I always know the name after you say it though,” one girl says.

“Well, there’s more to life than technology, kids. There’s music, art, dance, literature . . . all these things help blow the dust off our ordinary existence.

“I’ll get back to Horowitz in a minute. Last time I was here, I heard a conversation about how hard is it to go to college as a CS major.

“I have some good news and bad news. I’ll start with the bad news, which is not really that bad.

“If you want to go to college as an engineering major, including computer science, the bar for admission is going to be higher than it is for some other majors, one reason being that engineering mistakes can be very costly. We don’t want to have space shuttles blowing up. We don’t want to spend 50 million dollars on software systems that don’t work. So we can’t be graduating incompetent engineers.

“We can graduate English majors or music majors who are not very good because they can’t do any real damage in the world. What are they going to do? Write a bad sentence? Play a few wrong notes?

“But engineering mistakes can be very costly, so there’s a filtering process for engineers.

“Now the good news. Someone asked Horowitz this question: ‘How do you play all these difficult pieces?’ And his answer was ‘You just got to really want to.’

Question and answer

“I don’t want to say that you can do anything if you really want to, but you can amaze a lot of people, including perhaps yourself, with what you can do if you really want to.

“I want to emphasize that you really want to, because you may hear people say that they want something and yet you notice they’re not willing to change anything they’re doing in life in order to get it. Which means they don’t really want it.

“But based on students I’ve worked with before who are now CS majors at good schools, I can tell you that those of you in this class can do that as well, if you really want to.”

Competitive Programming: POJ 2185 – Milking Grid

Description

Every morning when they are milked, the Farmer John’s cows form a rectangular grid that is R (1 <= R <= 10,000) rows by C (1 <= C <= 75) columns. As we all know, Farmer John is quite the expert on cow behavior, and is currently writing a book about feeding behavior in cows. He notices that if each cow is labeled with an uppercase letter indicating its breed, the two-dimensional pattern formed by his cows during milking sometimes seems to be made from smaller repeating rectangular patterns.

Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid, as indicated in the sample input below.

Input

  • Line 1: Two space-separated integers: R and C
  • Lines 2..R+1: The grid that the cows form, with an uppercase letter denoting each cow’s breed. Each of the R input lines has C characters with no space or other intervening character.

Output

  • Line 1: The area of the smallest unit from which the grid is formed

Sample Input

2 5
ABABA
ABABA

Sample Output

2

Hint

The entire milking grid can be constructed from repetitions of the pattern ‘AB’.

Link to problem

Solution below . . .

Read more

Teaching Computer Science: Say Your Ideas Out Loud

[I learned about Scary Ideas from Jim and Michele McCarthy — PE]

I’m volunteering a couple mornings a week in a high school computer science class . . .

“The main thing I wanted to tell you is that you’ve got to say your ideas out loud . . .

Scary ideas

“A scary idea is not an idea that’s going to scare people when they hear it, it’s an idea that you don’t want to say because you’re afraid of how people will react to it. Maybe they’ll think you’re crazy.

“Here’s a couple examples of scary ideas.

“You recognize the speaker in this video?” Everyone does. “Ok, let’s see what he has to say.”

I believe that this nation should commit itself to achieving the goal, before this decade is out, of landing a man on the moon and returning him safely to the earth.

“Keep in mind that he’s saying this in 1961, when the idea of putting a man on the moon was complete science fiction. And bringing him back! Not just putting a man on the moon and leaving him there — which would be hard enough — but actually bringing him back!

“The amazing thing about this video to me is the reaction that he gets, which is no reaction at all. The two guys behind him, the guy on the right is Sam Rayburn, Speaker of the House, and on the left is either Lyndon Johnson or a wax replica of Lyndon Johnson.

“He’s speaking to both houses of Congress, hundreds of people, and the reaction is not “YEAH! WOO-HOO! U-S-A! U-S-A!” It’s complete silence. My theory is that people hearing this are thinking, ‘What a crazy idea. I’m withholding any show of support so people don’t think I’m crazy.’

“Here’s another scary idea: Let’s dig a canal across the continent!

Panama Canal

“It takes a long time to sail from one coast to the other because we’ve got to go all the way down around the tip of South America, so let’s just dig a canal across the continent.

“I don’t know who was the first person to say that out loud but it must have been pretty scary.

“Software development is a creative endeavor. You can’t have too many ideas. You want to generate as many ideas as possible and pick the best ones to work with. So you have to say your ideas out loud.

“Does anyone recognize this person?” No one does. Disappointing!

Martha Graham

“This is Martha Graham. You can’t get as famous as a dancer as you can doing some other things, but as a dancer, she’s about as famous as you can get.

“She said something that I want to share with you:

There is a vitality, a life force, an energy, a quickening that is translated through you into action, and because there is only one of you in all of time, this expression is unique. And if you block it, it will never exist through any other medium, and be lost. The world will not have it.

It is not your business to determine how good it is, nor how valuable, nor how it compares with other expressions. It is your business to keep it yours, clearly and directly, to keep the channel open.

You do not even have to believe in yourself or your work. You have to keep open and aware directly to the urge that motivates you.

Keep the channel open.

“You have to say your ideas out loud. If you don’t, they’re going to be lost, and the world will not have your contribution.”

See You in Hell

Satan

[See You in Hell is a feature by our guest blogger, Satan — PE]

The pope said yesterday that Satan — that’s me — “has been let loose and he’s got it in for the bishops.”

My reaction is that I am proud to be thrown under the bus alongside rape victims, abused unwed mothers and financial whistleblowers for the greater “good” of the church.

By the way, have you noticed that “prophet” and “profit” are homonyms?

See you in Hell!

More Words and Phrases I’m Sick Unto Death Of

Whenever I hear Let’s be clear or Make no mistake, it’s never followed by something clear or unmistakable, but always by some completely unsupportable hallucination . . .

A Close Encounter with Burt Reynolds’ Legacy

I’m having dinner at a Japanese restaurant . . . in the booth behind me are a couple straight out of Sons of Anarchy. The man is about 45, large, with a shaved head, tattoos and a motorcycle jacket. Same description for the woman, except for the shaved head.

Her jacket is emblazoned with PROPERTY OF TROG (or FROG or ????, couldn’t make it out clearly), which I assume is the name of either a motorcycle gang or the gentleman sitting across from her.

Midway through the meal, Trog wonders aloud if Smokey and the Bandit is available on Netflix. To his chagrin, the movie doesn’t seem to register with his girlfriend, so to jog her memory, he pulls up the “Eastbound and Down” song on his phone and plays it loudly enough to be heard by everyone in the vicinity.

He then launches into an analysis of the film in the reverend tones reserved for cinematic masterworks. I can’t hear all of it but it includes Sally Field, Peterbilt trucks and spinning donuts in a Trans Am.

He’s so inspired by the Smokey and the Bandit “one step ahead of the law” ethos that at the end of the meal, as he gets up to leave, his girlfriend reminds him that they didn’t get the check yet, but he gives her an ix-nay gesture and they walk out.

There’s a commotion out in the lobby . . . I hear someone yell “Hey you didn’t pay!” Trog does not return but his girlfriend comes back to take the check and pay it.

Competitive Programming: POJ 1147 – Binary Codes

Description

Consider a binary string (b1…bN) with N binary digits. Given such a string, the matrix of Figure 1 is formed from the rotated versions of the string.

b1 b2 bN-1 bN
b2 b3 bN b1
bN-1 bN bN-3 bN-2
bN b1 bN-2 bN-1

Figure 1. The rotated matrix

Then rows of the matrix are sorted in alphabetical order, where ‘0’ is before ‘1’. You are to write a program which, given the last column of the sorted matrix, finds the first row of the sorted matrix.

As an example, consider the string (00110). The sorted matrix is

0 0 0 1 1
0 0 1 1 0
0 1 1 0 0
1 0 0 0 1
1 1 0 0 0

and the corresponding last column is (1 0 0 1 0). Given this last column your program should determine the first row, which is (0 0 0 1 1).

Input

The first line contains one integer N <= 3000, the number of binary digits in the binary string. The second line contains N integers, the binary digits in the last column from top to bottom.

Output

The first line contains N integers: the binary digits in the first row from left to right.

Sample Input

5
1 0 0 1 0

Sample Output

0 0 0 1 1

Link to problem

Solution below . . .

Read more

Europeans Tired of Tourists?

Jumping Amsterdam

Europeans are tired of tourists?!

I don’t know if they’d qualify as “tourists,” but Europe didn’t object to my dad and a few million of his uncouth American pals showing up in the 1940s to save them from fascism.

Now they’re like, “Put an egg in your shoe and beat it.”

Thomas Jefferson on John McCain

Thomas Jefferson

My fellow Americans –

Like President Trump, I was not invited to any of the John McCain memorial services, so I offer my final thoughts here.

McCain’s service to his country while being held as a POW in Vietnam was admirable beyond measure.

Because his father was commander of all U.S. forces in the Vietnam theater, the Vietnamese offered to release McCain, not as a gesture of mercy, but as a propaganda coup, and to show other POWs that members of the elite were willing to be treated preferentially.

McCain stated that he would only accept the offer if every man captured before him was released as well. This enraged the Vietnamese, and McCain’s subsequent five years as a POW went very badly, as he knew they would.

Liberals have been very kind to McCain this week because 1) he’s dead, and 2) he was an enemy of President Trump. Not mentioned is that when he was running for president in 2008, they compared him with Hitler, just like every other Republican candidate since World War II.

Also not mentioned this week: his first wife, Carol, whom he divorced in 1980.

In 1969, during the time her husband was being held as a POW, the car she was driving skidded off an icy Pennsylvania highway into a telephone pole. She was hospitalized for six months and had 23 reconstructive operations over the next two years.

Her medical care was paid for by Ross Perot, a businessman and POW advocate.

When she and her husband were reunited in 1973, she was four inches shorter, in a wheelchair or on crutches, and substantially heavier than when he had last seen her.

In 1979, John McCain began a relationship with Cindy Lou Hensley, 18 years his junior and heiress to Hensley & Co., the third-largest Anheuser-Busch distributor and one of the largest privately held companies in America.

In 1980, he filed for divorce.

Perot’s assessment: “After he came home, he walked with a limp, she [Carol McCain] walked with a limp. So he threw her over for a poster girl with big money from Arizona and the rest is history.”

One assumes that Carol McCain was on this week’s Do Not Invite list, along with President Trump and Sarah Palin. I didn’t see Ross Perot either.

(For those of you asking “What about Sally Hemings?” in an effort to undercut my credibility on marital fidelity, I remind you that my wife was deceased and I was unmarried at that time.)

Thomas Jefferson

Competitive Programming: POJ 1961 – Period

Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK, that is A concatenated K times, for some string A. Of course, we also want to know the period K.

Input

The input consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1,000,000) – the size of the string S. The second line contains the string S. The input file ends with a line, having the number zero on it.

Output

For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.

Sample Input

3
aaa
12
aabaabaabaab
0

Sample Output

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

Link to problem

Solution below . . .

Read more

Teaching Computer Science: All Are Welcome

Diversity

I’m volunteering a couple mornings a week in a high school computer science class . . .

“Computing,” I tell the class, “is like most professions in that some groups are under-represented and some groups are over-represented. You may have heard that the reason some groups are under-represented is because computing as a profession is more welcoming to some people than others.

“I haven’t found that to be the case and I’ll tell you why.

“My perspective on this is that if you walk through the workplace at a typical technology company, you won’t see people who look like me. I’m too old and I’ve been too old for quite a while now. At this point, I’m usually old enough to be the CEO’s father.

“So to the extent that people want to work with other people who look like them and people who fit into the group, that doesn’t help me because I don’t fit into the group.

“That being said, I find it to be a total non-issue because technology is a knowledge-based profession. The hierarchy is based on knowledge. If you know things that other people don’t know, and you can solve problems that other people can’t solve, you are at the top of the food chain. You are the king or queen of the jungle.

“It doesn’t matter how old or young you are, your genetics or the environment you grew up in. The important thing is what you know and the choices you make, starting with a decision that I’m going to do this and I’m going to be successful at it. I’m going to study hard, I’m going to work hard, I’m going to take on the hard jobs, I’m going to take on the challenges.

“You get to choose who you hang around with and who you want to emulate.

“Where you were and what you went through is not as important as where you’re going and the choices you need to make to get there.”

A student suggests that I’m dismissing a lot of anecdotal evidence regarding bias in computing.

“I’m not dismissing it but I’m according it what I think is an appropriate weight. When I hear or read about groups X, Y and Z facing an uphill battle in technology careers, I find that the author has interviewed a small number of people — usually one or two people, maybe three if they’re really ambitious.

“That’s a very small sample size from which to draw sweeping conclusions about an entire industry, and you could easily find two or three other people to say the exact opposite.

“If that’s our standard of evidence — finding two or three people to provide some supporting quotes — you could make a case for absolutely anything.

“So I encourage you to consider, in this case and others, the number of data points you have and whether that’s enough to support the conclusions you’re trying to draw from them.”

Overheard

“The grass is not always greener.”

“No, but it’s not always not greener either.”

Grass

EppsNet Book Reviews: An Inconvenient Woman by Dominick Dunne

It’s a good murder mystery, but about two-thirds of the way through, I felt like I couldn’t indulge the author’s sexual obsessions any further and just flipped ahead to see whodunit.

Every man has either “a dick like a mule” or “a dick like a Tampax.” No one has ” a dick of average proportions.”

Sexual relationships are either non-existent (with one’s wife) or preposterously frequent and varied (with one’s mistress(es)).

One unlikely plot device is premised on a particular woman’s “most intimate scent.”

I’d suggest that the author have his head examined but he’s been dead for nearly 10 years . . .

Who Listens to Sports Talk?

Bald guy

I had a sports talk station on the car radio this afternoon . . . based on the the advertisements, the target demographic is low-testosterone bald guys whose dicks don’t work . . .

Teaching Computer Science: Don’t Worry About Spelling and Grammar?

The following is part of the Code.org online curriculum, asking students to write a brief reflection on starting a computer science class.

Reflection prompt

That seems like an oddball thing to say in an educational context.

“Let’s talk about the instructions here for a minute,” I said to the class. “One: it doesn’t make sense to me to compartmentalize education like this. Like spelling and grammar are only important in an English class and this is not an English class so don’t worry about it.

“We’ll be taking a holistic view of education here. I hope you’ll learn some things about computer science but I hope you’ll learn some other things as well.

“On a practical note, you may find yourself competing for a job someday, and if it’s a good job, there are likely to be a lot of applicants.

“No one wants to read a large number of resumes, so the recruiter or the hiring manager will be looking for reasons to reject your resume without actually reading it, one obvious reason being bad spelling and grammar.

“Even if you’re applying for a technology job, no one is going to say, ‘Well, he or she is not an English major so I’ll make allowances for the bad spelling and grammar.’ Your resume is going in the trash, along with your job prospects.

“So where it says ‘Don’t worry about spelling and grammar,’ translate that in your mind to ‘Worry about spelling and grammar.'”

Teaching Computer Science: Why Was I Not Consulted?

Numbers

I’m volunteering in a high school computer science class a couple mornings a week . . .

If you’re going to work with computers, you need to be able to move around between different number systems, most commonly base 10, base 2 and base 16.

As a warm-up, I asked students how many ways they could represent the quantity 7. Answers included the word “seven,” roman numerals, seven dots, a septagon, a Chinese symbol, and so on.

“Quantities exist naturally,” I said, “but number systems are man-made. They’re just a set of symbols along with an agreement about how to order them. Why do we use the number system that we do? Who decided that?”

Because I phrased it in a provocative way, some students realized that they hadn’t been consulted.

“Yeah, no one asked me,” one student said.

“Raise your hand in math class,” I suggested, “and ask ‘Why do we use these symbols to represent quantities? Who decided that?'” Maybe it was Donald Trump. “You could do the same thing with the alphabet in your English class.”

Resistance! To the barricades!

Competitive Programming: POJ 2074 – Line of Sight

Description

An architect is very proud of his new home and wants to be sure it can be seen by people passing by his property line along the street. The property contains various trees, shrubs, hedges, and other obstructions that may block the view. For the purpose of this problem, model the house, property line, and obstructions as straight lines parallel to the x axis:

POJ 2074 - Line of Sight

Input

Because each object is a line, it is represented in the input file with a left and right x coordinate followed by a single y coordinate:

<x1> <x2> <y>

where x1, x2, and y are non-negative real numbers, x1 < x2 .

An input file can describe the architecture and landscape of multiple houses. For each house, the first line will have the coordinates of the house. The second line will contain the coordinates of the property line. The third line will have a single integer that represents the number of obstructions, and the following lines will have the coordinates of the obstructions, one per line.

Following the final house, a line “0 0 0” will end the file.

For each house, the house will be above the property line (house y > property line y). No obstruction will overlap with the house or property line, e.g. if obstacle y = house y, you are guaranteed the entire range obstacle[x1, x2] does not intersect with house[x1, x2].

Output

For each house, your program should print a line containing the length of the longest continuous segment of the property line from which the entire house can be to a precision of 2 decimal places. If there is no section of the property line where the entire house can be seen, print “No View”.

Sample Input

2 6 6
0 15 0
3
1 2 1
3 4 1
12 13 1
1 5 5
0 10 0
1
0 15 1
0 0 0

Sample Output

8.80
No View

Link to problem

Solution below . . .

Read more

Company Picnic

Dunk Tank

A highly placed manager at work shows up next to me in the men’s room.

“You going to the company picnic?” he shouts. He’s a boisterous guy.

“Yes!” I reply. “Looking forward to taking a few throws at you in the dunk tank.”

Dunk tank?!” he says. “There’s not going to be any dunk tank.”

“Oh . . . in that case I’m not going.”

“Why Do I Believe What I Believe?”

Thomas Jefferson

My fellow Americans –

About 20 people showed up for Unite the Right last weekend.

That would be a disappointing turnout for a pancake breakfast sponsored by the local softball league, let alone a national rally in Washington, DC.

White supremacy is like the Flat Earth Society, not non-existent, but extremely marginal. It’s a boogeyman to scare people about things that are not real.

A good question to ask is “Why do I believe what I believe?” For example, “Why do I believe in a resurgence of white supremacy when only 20 people in a nation of 300 million can be persuaded to show up at a rally?”

Possible answers include “I saw it on the internet” or “I heard it on TV.” These are perhaps not good answers, in that they open us up to manipulation for political gain, financial gain, and increased readership and viewership.

Thomas Jefferson