EppsNet

Overheard: “As a . . .”

by Hostile Witness on 27 Jun 2018

“As a member of the queer community and a trans woman of color . . .”

“Are you the official spokesperson for the queer community and/or trans women of color? If not, that’s not a good lead-in to whatever you’re going to say.”

It’s going to get ponderous if we all have to begin sentences by announcing all of the labels we’re currently assigning to ourselves.

“As a white male heterosexual . . .”

“As a Gen-X Albanian bisexual . . .”

“As an LGBT with PTSD . . .”

“As a differently-abled libertarian woman with AIDS . . .”

Just say your piece!

Some people would say at this point that queer trans women of color should be recognized and celebrated. Would they say the same about a guy wearing a MAGA hat and an NRA t-shirt? Would they want to make sure that he feels safe and comfortable about his choices in life? Probably not.

Tolerance and inclusion are good but there are limits. Nobody loves everybody.

If diversity means we can all come together on an equal footing, and defer to the choices others make about their own lives, even if we wouldn’t make the same choices ourselves, it seems like a good thing.

If it means expecting everyone to recognize and celebrate all of our choices, I hate to say it but we are doomed.

Competitive Programming: POJ 2455 – Secret Milking Machine

by Paul Epps on 27 Jun 2018

Description

Farmer John is constructing a new milking machine and wishes to keep it secret as long as possible. He has hidden in it deep within his farm and needs to be able to get to the machine without being detected. He must make a total of T (1 <= T <= 200) trips to the machine during its construction. He has a secret tunnel that he uses only for the return trips.

The farm comprises N (2 <= N <= 200) landmarks (numbered 1..N) connected by P (1 <= P <= 40,000) bidirectional trails (numbered 1..P) and with a positive length that does not exceed 1,000,000. Multiple trails might join a pair of landmarks.

To minimize his chances of detection, FJ knows he cannot use any trail on the farm more than once and that he should try to use the shortest trails.

Help FJ get from the barn (landmark 1) to the secret milking machine (landmark N) a total of T times. Find the minimum possible length of the longest single trail that he will have to use, subject to the constraint that he use no trail more than once. (Note well: The goal is to minimize the length of the longest trail, not the sum of the trail lengths.)

It is guaranteed that FJ can make all T trips without reusing a trail.

Input

Line 1: Three space-separated integers: N, P, and T
Lines 2..P+1: Line i+1 contains three space-separated integers, A_i, B_i, and L_i, indicating that a trail connects landmark A_i to landmark B_i with length L_i.

Output

Line 1: A single integer that is the minimum possible length of the longest segment of Farmer John’s route.

Sample Input

Sample Output

Hint

Farmer John can travel trails 1 – 2 – 3 – 7 and 1 – 6 – 7. None of the trails travelled exceeds 5 units in length. It is impossible for Farmer John to travel from 1 to 7 twice without using at least one trail of length 5.

Huge input data, scanf is recommended.

Link to problem

Solution below . . .

Thomas Jefferson Explains Family Separations

by Thomas Jefferson on 26 Jun 2018

My fellow Americans —

The reason families are separated at the border is that the United States, like many countries, has laws governing border crossings by non-residents.

When an adult is apprehended crossing our border illegally, they go into the criminal justice system and are placed in a detention center.

Keep in mind that an American citizen apprehended in the commission of a crime is not processed any differently. If you are placed in a detention center, I assure you that your children will not be in there with you.

A note on rhetoric: A strong line of argument should not require violent metaphors and manufactured hysteria — families “ripped apart,” children “torn from their mother’s arms” — to be persuasive.

Read the Declaration of Independence, for example.

Thomas Jefferson

Exactly the Same?

by Paul Epps on 24 Jun 2018

Cats With Hands

Decisions Are Not “Right” or “Wrong”

by Paul Epps on 24 Jun 2018

Decisions are bets on the future, and they aren’t “right” or “wrong” based on whether they turn out well on any particular iteration. An unwanted result doesn’t make our decision wrong if we thought about the alternatives and probabilities in advance and allocated our resources accordingly. . . . It would be absurd for me, after making a big bet on the best possible starting hand (a pair of aces) and losing, to spend a lot of time thinking I was wrong to make the decision to play the hand in the first place. . . .

When we think probabilistically, we are less likely to use adverse results alone as proof that we made a decision error, because we recognize the possibility that the decision might have been good but luck and/or incomplete information (and a sample size of one) intervened.

Maybe we made the best decision from a set of unappealing choices, none of which were likely to turn out well.

Maybe we committed our resources on a long shot because the payout more than compensated for the risk, but the long shot didn’t come in this time.

Maybe we made the best choice based on the available information, but decisive information was hidden and we could not have known about it.

Maybe we chose a path with a very high likelihood of success and got unlucky.

Maybe there were other choices that might have been better and the one we made wasn’t wrong or right but somewhere in between. The second-best choice isn’t wrong. By definition, it’s more right (or less wrong) than the third-best or fourth-best choice. . . .

Being right feels really good. “I was right,” “I knew it,” “I told you so” — those are all things that we say, and they all feel very good to us. Should we be willing to give up the good feeling of “right” to get rid of the anguish of “wrong”? Yes. . . .

The world is structured to give us lots of opportunities to feel bad about being wrong if we measure ourselves by outcomes. Don’t fall for it!

— Annie Duke, Thinking in Bets

You Can’t Tell the Nazis Without a Scorecard

by Thomas Jefferson on 24 Jun 2018

If you see anybody from that Cabinet in a restaurant, in a department store, at a gasoline station, you get out and you create a crowd and you push back on them, and you tell them they’re not welcome anymore, anywhere.

— Maxine Waters

And they should be made to wear armbands so they’re easier to identify!

It’s getting to where you can’t tell the Nazis without a scorecard.

Thomas Jefferson

Competitive Programming: POJ 2195 – Going Home

by Paul Epps on 22 Jun 2018

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.

POJ 2195

You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.

Input

There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of ‘H’s and ‘m’s on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.

Output

For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.

Sample Input

2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0

Sample Output

2
10
28

Link to problem

Solution below . . .

Separation of Families Considered Harmful?

by Hostile Witness on 21 Jun 2018

Here’s a photo showing two girls in a “cage” watching a World Cup match, amongst dozens of other kids who are for some reason wrapped in foil.

Kids in holding facility

I’ve seen this photo and others widely circulated online recently as evidence of the Trumpenfuhrer’s crimes against humanity.

But guess what? The photos were taken in 2014, when some other guy was president.

Many people have a single standard for evaluating political activity: Is it being carried out by Team Red or Team Blue. Nothing is good or bad on its own merits.

I don’t remember anyone on Team Blue being outraged about kids in “cages” in 2014, but in 2018 it’s a humanitarian crisis that has to be denounced mercilessly, even if the evidence has to be faked.

I haven’t heard anyone propose a viable alternative to separating parents and children at the border. I’m not sure Team Blue wants to find a viable alternative since it’s such a great election-year issue.

Is the outrage real or manufactured?

What is the number one priority for American parents? More daycare! Forced separation! For parents who can’t afford daycare, the government makes other people pay for it. That’s how essential it is. It’s a national priority for parents to be able to put their kids in holding facilities.

For parents who don’t want to be with their kids even on nights and weekend, boarding schools are available for 24/7 separation.

When school lets out — summer camps! Or more daycare!

I never hear kids say that they want to spend more time with their parents. I’ve heard parents say they want to spend more time with their kids, but they don’t rearrange their lives in any way to make that happen.

Saying that you want something implies that you’re willing to change to get it. Otherwise, you really don’t want the thing.

The average daycare worker makes $11.42 per hour, less than, for example, baggage porters and bellhops ($12.55/hr), who perform a similar service, i.e., taking custody of possessions that you don’t want to be bothered with.

You Think I’m Inept?

by Paul Epps on 19 Jun 2018

“You think I’m inept? You think I’m inadequate? If I’m inadequate, where are you going to get people who are adequate . . . if I’m . . . do you understand what I’m saying? What am I supposed to be? What are other people if I am inadequate?”

— Philip Roth, American Pastoral

Sorrow Without Limits

by Paul Epps on 18 Jun 2018

The whole order of things fills me with a sense of anguish, from the gnat to the mysteries of incarnation; all is entirely unintelligible to me, and particularly my own person. Great is my sorrow, without limits. None knows of it, except God in Heaven, and He cannot have pity.

— Sören Kierkegaard

Philistinism

by Paul Epps on 17 Jun 2018

Philistinism tranquilizes itself in the trivial — Kierkegaard

— Paul Epps (@paulepps) June 17, 2018

It Is Just Too Shaking and Wearing

by Paul Epps on 17 Jun 2018

We are just not strong enough to endure more! It is just too shaking and wearing. So often people in . . . ecstatic moments say, “It’s too much,” or “I can’t stand it,” or “I could die” . . . Delirious happiness cannot be borne for long. Our organisms are just too weak for any large doses of greatness.

— Abraham Maslow

Non ridere, non lugere, neque detestari, sed intelligere. (Not to laugh, not to curse, not to lament, but to understand.) — Spinoza

Competitive Programming: POJ 3169 – Layout

by Paul Epps on 15 Jun 2018

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 each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.

Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.

Input

Line 1: Three space-separated integers: N, ML, and MD.

Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.

Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.

Output

Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.

Sample Input

Sample Output

Hint

Explanation of the sample:

There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units apart.

The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.

Link to problem

Solution below . . .

Competitive Programming: POJ 1125 – Stockbroker Grapevine

by Paul Epps on 13 Jun 2018

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 the information.

Input

Your program will input data for different sets of stockbrokers. Each set starts with a line with the number of stockbrokers. Following this is a line for each stockbroker which contains the number of people who they have contact with, who these people are, and the time taken for them to pass the message to each person. The format of each stockbroker line is as follows: The line starts with the number of contacts (n), followed by n pairs of integers, one pair for each contact. Each pair lists first a number referring to the contact (e.g. a ‘1’ means person number one in the set), followed by the time in minutes taken to pass a message to that person. There are no special punctuation symbols or spacing rules.

Each person is numbered 1 through to the number of stockbrokers. The time taken to pass the message on will be between 1 and 10 minutes (inclusive), and the number of contacts will range between 0 and one less than the number of stockbrokers. The number of stockbrokers will range from 1 to 100. The input is terminated by a set of stockbrokers containing 0 (zero) people.

Output

For each set of data, your program must output a single line containing the person who results in the fastest message transmission, and how long before the last person will receive any given message after you give it to this person, measured in integer minutes.

It is possible that your program will receive a network of connections that excludes some persons, i.e. some people may be unreachable. If your program detects such a broken network, simply output the message “disjoint”. Note that the time taken to pass the message from person A to person B is not necessarily the same as the time taken to pass it from B to A, if such transmission is possible at all.

Sample Input

3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2
5
3 4 4 2 8 5 3
1 5 8
4 1 6 4 10 2 7 5 2
0
2 2 5 1 5
0

Sample Output

3 2
3 10

Link to problem

Solution below . . .

USC’s Unreal Finish to Win Track and Field Championship

by Paul Epps on 10 Jun 2018

I’ve never seen a come-from-behind finish like this!

The male announcer says twice in the home stretch that Purdue is going to win the race.

Female announcer: “Here comes USC.”

Male announcer: “Not gonna catch Purdue . . . oh my god . . .”

The @usc_track_field Women of Troy had to win the 4x400m to win the national championship.

WATCH WHAT #FIGHTON LOOKS LIKE! pic.twitter.com/BOrISxUXXq

— USC Trojans (@USC_Athletics) June 10, 2018

More People I’m Sick Unto Death Of: Grads

by Paul Epps on 8 Jun 2018

Why is it always “Dads and Grads”? Mothers get the whole month of May to themselves — despite the fact that a lot of graduations take place in May — but June is always Dads and Grads.

Granted, Moms and Grads doesn’t rhyme like Dads and Grads or Highways and Byways . . . but why not Moms and Proms? Flowers for everyone!

Anyway, Happy Fathers Day, guys.

Anthony Bourdain, 1956-2018

by Paul Epps on 8 Jun 2018

I think of Anthony Bourdain as the guy who started the whole “bad-boy chef” industry, which has been, in my view, bad for society.

Or maybe it was Gordon Ramsay. Is Gordon Ramsay still alive?

RIP Anthony Bourdain

I Feared That the Dam Might Break So I Loosed the River

by Paul Epps on 3 Jun 2018

I can never remake the thing I have destroyed;
  I brushed the golden dust from the moth’s bright wing,
I called down wind to shatter the cherry-blossoms,
  I did a terrible thing.

I feared that the cup might fall, so I flung it from me;
  I feared that the bird might fly, so I set it free;
I feared that the dam might break, so I loosed the river:
  May its waters cover me.

— Aline Murray Kilmer, “Shards”

Competitive Programming: POJ 2488 – A Knight’s Journey

by Paul Epps on 1 Jun 2018

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 that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.

Sample Input

Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

Link to problem

Solution below . . .

Related Posts

Description

Input

Output

Sample Input

Sample Output

Hint

Related Posts

Related Posts

Related Posts

Related Posts

Related Posts

Description

Input

Output

Sample Input

Sample Output

Related Posts

Related Posts

Related Posts

Related Posts

Related Posts

Related Posts

Description

Input

Output

Sample Input

Sample Output

Hint

Related Posts

Description

Input

Output

Sample Input

Sample Output

Related Posts

Related Posts

Related Posts

Related Posts

Related Posts

Description

Background

Problem

Input

Output

Sample Input

Sample Output

Related Posts