Competitive Programming: CodeSignal – footballGroupStatictics (A World Cup SQL Challenge)

Description

You are creating a website that will help you and your friends keep track of the results of soccer games from all around the world. You store all results of one group in a table, results. You want to sort the teams in a complex way – first by points, then by total goal differences, and then by total goals. If all of these parameters are equal, sort the teams alphabetically.

The results table contains the following columns:

  • first_team – the name of the first team;
  • second_team – the name of the second team;
  • first_team_score – the number of goals scored by the first team;
  • second_team_score – the number of goals scored by the second team.

Here the primary key is the pair (first_team, second_team). Return the list of team names sorted in the way described above.

Note: see three points for a win to understand how points are calculated.

Example

For given table results

first_team second_team first_team_score second_team_score
Preachers Blackflies 2 1
Preachers Razorbacks 3 2
Blackflies Razorbacks 1 1

the output should be

team_name
Preachers
Razorbacks
Blackflies
  • Preachers have 6 points (from winning two games), 2 is the total goal difference (2 - 1 = 1 from the first game, and 3 - 2 = 1 from the second game), and the total goal count is 5 (2 from the first game, plus 3 from the second game).
  • Razorbacks have 1 point (from their draw game with the Blackflies), a goal difference of -1 (2 - 3 = -1 from their first game, and 1 - 1 = 0 from their second game), and a total goal count of 3.
  • Blackflies also have 1 point and -1 goal difference, but their total goal count is 2.

Solution below . . .

Read more

A Tolerant and Diverse Society

Taxes

11,000 New Computer Science Teachers Considered Harmful?

Here’s the start of an email I got from Code.org:

We’re kicking off our summer workshops to prepare 11,000 new CS teachers. Last month we welcomed over 600 teachers, facilitators, and Regional Partners to Atlanta, GA for our largest TeacherCon ever.

On top of TeacherCon, we also have 350 K-5 workshops and 167 workshops for middle and high school teachers planned this summer, where we expect an additional 10,000 teachers who plan to begin teaching computer science for the first time this fall!

This is heralded with an exclamation point, like it’s exciting news, but as a computer science person, I can’t get excited about it. Why do we want kids to be taught computer science by 11,000 teachers who know little or nothing about computer science?

How can someone teach something that they themselves don’t do?

See if you can get excited about any of the following possibilities:

  • 11,000 math teachers who know little or nothing about math!
  • 11,000 music teachers who have never listened to a piece of music!
  • 11,000 French teachers who don’t speak French!
  • 11,000 journalism teachers who have never written for publication!

What is it about computer science that we accept teachers who have never created an original piece of software, know nothing of the history and philosophy of the subject (e.g., don’t get “considered harmful” jokes), nothing about recent developments?

When I teach computer science, I’m not relying on committees of educators and elected officials to know if what I’m teaching is valuable and how well I’m teaching it. I’m teaching something that is part of my life. I’m passing on my own insights and experience and trying to convey a way of thinking that seems valuable to me.

Can a teacher convey a way of thinking if he doesn’t genuinely think that way?

Thus spoke The Programmer.

Competitive Programming: CodeSignal – canScore (A World Cup Challenge)

Description

Your friend is a soccer fan and you were watching some World Cup matches with him. You liked this game, but the rules are very complicated for you, so you decided just to try to guess whether the given attack will end with a goal or not.

In the beginning, the ball is in the attacking team’s goalkeeper’s hands. On the attacking team, there’s a very talented goalscorer, who is waiting for his chance at the other end of the field. His teammates want to give him the ball so he can score. They can move the ball by passing it one to another along a straight line, but the defender can steal the pass if he is closer than d to the ball at any point throughout the pass. Now you want to know if the attacking team can score or not.

Formally, you are given the coordinates of all attacking players in an array attackingPlayers (where the player at index 0 is the goalkeeper and the player at the final index is the goalscorer), the coordinates of all defending players in an array defendingPlayers, and an integer d (representing how far each defending player can reach in order to intercept a pass). You need to find out whether it is possible to score a goal by passing the ball to the best scorer without any passes being intercepted.

Example

For attackingPlayers = [[0, 0], [1, 2], [3, 1]], defendingPlayers = [[2, 1]] and d = 1, the output should be canScore(attackingPlayers, defendingPlayers, d) = false.

Example 1

Attacking player 0 can pass to attacking player 1 without the pass being intercepted, but neither attacking player 0 nor attacking player 1 can pass to attacking player 2 (the goal scorer), so the goal cannot be completed.

For attackingPlayers = [[0, 0], [1, 2], [3, 3], [3, 1]], defendingPlayers = [[2, 1]] and d = 1, the output should be canScore(attackingPlayers, defendingPlayers, d) = true.

Example 2

The goal can be scored if the ball is passed from attacking players 0 to 1 to 2 to 3.

For attackingPlayers = [[1, 2], [5, 3], [4, -2], [8, 0], [8, 6]], defendingPlayers = [[4, 4], [1, -1], [9, 2]] and d = 2, the output should be canScore(attackingPlayers, defendingPlayers, d) = true.

Example 3

The goal can be scored if the ball is passed from attacking players 0 to 3 to 2 to 4.

Input/Output

  • [execution time limit] 3 seconds (java)
  • [input] array.array.integer attackingPlayers

    An array of coordinates of all players from the attacking team. The first one is the goalkeeper’s coordinates and the last one is the best goalscorer’s coordinates.

    Guaranteed constraints:
    2 <= attackingPlayers.length <= 100
    attackingPlayers[i].length = 2
    104 <= attackingPlayers[i][j] <= 104

  • [input] array.array.integer defendingPlayers

    An array of coordinates of all players from the defending team.

    Guaranteed constraints:
    1 <= defendingPlayers.length <= 100
    defendingPlayers[i].length = 2
    -104 <= defendingPlayers[i][j] <= 104

  • [input] integer d

    The distance that each defending player can reach in intercepting a pass.

    Guaranteed constraints:
    0 <= d <= 104

  • [output] boolean

    True if attacking team can score a goal, False otherwise.

Solution below . . .

Read more

We’ll All Go Together When We Go

I’m afraid that there are people who, given a choice between a Trump success story and a nuclear war, would choose the war.

Thomas Jefferson: Why I Don’t Wear a MAGA Hat

Thomas Jefferson

My fellow Americans —

This is why we fought a war to get away from the goddamn Brits.

I would personally not wear a MAGA hat in public for the reason cited, i.e., Trump opponents seem to be violent and easily triggered.

That said, if your idea of a good time is to steal a kid’s hat and throw a soda in his face, you should probably shut up about the tolerance and mental stability of others until you get your own shit together.

As for lessons in personal responsibility, the drink thrower is now in jail. He who laughs last, etc.

Thomas Jefferson

Thomas Jefferson: Separating Babies and Mothers

Thomas Jefferson

My fellow Americans —

Separation of families at the border was going to be a great election issue for Democrats until fate intervened in the form of Justice Kennedy announcing his retirement from the Supreme Court.

Most of the people outraged by border separations are also afraid of losing a key Supreme Court swing vote, particularly on the issue of abortion.

Unfortunately, Democrats have standardized on a needlessly violent metaphor — “ripping” — to talk about family separations.

A representative example:

Now that abortion has again become a leading national issue, the Republican talking points re “ripping babies from their mother” write themselves.

Footnote: In apprehending and prosecuting people who committed crimes, one assumes that Ms. Harris separated them from their children.

Thomas Jefferson

End of the World Poll

Bomb

Musical question: What is a good song to play when the nukes start falling?

  • We’ll Meet Again
  • What a Wonderful World
  • Eve of Destruction
  • We’ll All Go Together When We Go
  • Always Look on the Bright Side of Life
  • Clair de Lune
  • Something short

Doesn’t Tell Me What I Need to Know

A co-worker is telling another co-worker that you have to make sure day care providers are insured and bonded.

Actually, being insured and bonded is no guarantee that I want you taking care of my child . . .

“Mr. So-and-so, your son wouldn’t stop crying so we taped his mouth shut. The bad news is: he died. The good news is we’re insured and bonded!”

Competitive Programming: POJ 3281- Dining

Description

Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.

Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a complete meal of both food and drink to as many cows as possible.

Farmer John has cooked F (1 <= F <= 100) types of foods and prepared D (1 <= D <= 100) types of drinks. Each of his N (1 <= N <= 100) cows has decided whether she is willing to eat a particular food or drink a particular drink. Farmer John must assign a food type and a drink type to each cow to maximize the number of cows who get both.

Each dish or drink can only be consumed by one cow (i.e., once food type 2 is assigned to a cow, no other cow can be assigned food type 2).

Input

Line 1: Three space-separated integers: N, F, and D

Lines 2..N+1: Each line i starts with a two integers Fi and Di, the number of dishes that cow i likes and the number of drinks that cow i likes. The next Fi integers denote the dishes that cow i will eat, and the Di integers following that denote the drinks that cow i will drink.

Output

Line 1: A single integer that is the maximum number of cows that can be fed both food and drink that conform to their wishes.

Sample Input

4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3

Sample Output

3

Hint

One way to satisfy three cows is:

Cow 1: no meal
Cow 2: Food #2, Drink #2
Cow 3: Food #1, Drink #1
Cow 4: Food #3, Drink #3

The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.

Link to problem

Solution below . . .

Read more

A Prescription for Peace of Mind

If I don’t believe that I’m the prime cause of my life being the way it is, I’m doomed to a joyless existence in the victim position.

Any prescription for peace of mind has got to include owning your own shit.

Overheard: “As a . . .”

“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

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

7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3

Sample Output

5

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

Read more

Thomas Jefferson Explains Family Separations

Thomas Jefferson

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?

Cats With Hands

Decisions Are Not “Right” or “Wrong”

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

Thomas Jefferson

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

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

Read more

Separation of Families Considered Harmful?

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 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?

“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