BLMWT #3 – SOHN

This is a guy I fount at Spotify (I find a lot of great musicians trough Spotify, and  I’m very thankful for this, xoxo Spotify <3), his name is SOHN, actually is Christopher Taylor, he is a british musician and released his first album in 2014. I don’t have a clue what music gender he plays, its electronic music mixed with the sense of life, the universe and everything 42. It’s different then everything I ever listened to, and that’s why I’m telling you guys: go listen to his music!!

SOHN – Artifice
Tremors Live
Advertisements
BLMWT #3 – SOHN

A graph? What is it?

Introduction

 

Hello, in this article we’ll discuss a little bit about graphs. This is one of the main topics that turns a newbie into an intermediate competitor in programming contests (of course in my opinion).

When I didn’t know much about graphs, or when I didn’t know to code some classic graph problems, people talked or asked questions about this topic and I just thought that:

“Graphs are a really hard topic (mainly to code),  that sometimes appear in coding competitions, and when it does I can notice it’s a graph problem, but I don’t know anything about how to implement it.”

After this article (and a bit of practice) I hope you can have a more structured thought about graphs, like:

“Graphs aren’t in general difficult, this is just something new and more advanced, and that’s why it needs previous knowledge and may take some time to get used to the idea. A lot of problems are related to graphs, almost all competitions have some graph problem.  And when you get the idea of the classic graph algorithms, most of them are simple to understand why it works and to code”.

Ps: I tough the sentence was gonna be shorter, but that is it haha.

This article has the following structure:

  • Previous knowledge required
  • Graphs, a definition
  • How to represent a graph in a computational way?
  • Bibliography and suggested readings


Previous Knowledge Required

So, here we go! Before talking about graphs, some important topics to study are:

  1. Recursion
  2. Basic Data Structures (queue, stack, priority queue)
  3. Feel comfortable in your programming language (libraries, syntax)
    PS: I plan to talk about these topics, when I do I’ll put the link here :).

If you never heard about these topics, or feel like you should know more about them, I really suggest you study it. The major troubles with graph implementations are due to not enough experiences in the topics above.

Graphs, a definition

For programming competitions the following definition is “enough” : a graph is a data-structure, a way to organize the data, defined by a set of vertices/nodes and a set of edges that are used to connect 2 vertices.
 
Graph 1
Graph 2
Graph 3
 

Okay… but why use this model? There are many situations where a graph is a great structural model, the most common examples are: roads and avenues, social networks, friend network, dependencies relations.

An example of a problem evolving graphs is the problem Toll from Brazilian Programming Olympics(OBI) of 2002:

John was the fist place at OBI and as a prize he and his family won a trip to South Korea. They rented a car to get to know the country better. The roads(1) are well maintained; all of them are two-way street(2), and two cities may be connected directly by more than one road(3). But in all of them there is a fixed value Toll(4). The father of John doesn’t have a lot of money to spend, so the car trips must be well planed.

Task: Write a program that, with the cities(5) and the roads in the country, and the city where John and his family are, find each city(don’t count the one where they already are) that can be visited, given the restriction that the father of John wishes to pay at most P Tolls(6).

 

Ok, so it’s a graph problem right? And where is the graph? Well, it’s a classic example! The roads are the edges and the cities are the vertices.
Graph represented by roads example

In the problem explanation there are some interesting words and expressions that say a lot to us about how is the graph. How so? Well, there are a lot of graph classifications and types of graphs. And it will interfere in our solution and in the graph representation.

The mainly graph characteristics

Connected graph: there is a path from each vertex to any other.
Unconnected graph: there is one or more vertices that we can’t reach from some other vertex.
Sparse graph: if the number of edges is much less than the number of vertices (if is less of  the square of the number of vertices it can be considered  sparse).
Dense graph: if the number of edges is close to the number of vertices.
Directed graph: the edges have directions. In other words, if there is an edge from A to B (A and B are vertices) it doesn’t implies in the existence of an edge from B to A.
Undirected graph: edges have no direction. In other words, if there is an edge from A to B (A and B are vertices) it implies in the existence of an edge from B to A.
Weighted graph: the edges have a weight associated to them.
Unweighted graph: the edges doesn’t have a weight associated to them. Other way to see it is that all edges have the same weight.

Some important graphs expressions

Path: sequence of vertices such that for each vertex there is only one edge for the next one.
Shortest path: shortest path that connects a vertex to another.
Degree: the degree is a vertex feature, the vertex degree is the number os edges that goes from the vertex to any other vertex.
Loops: an edge that connects a vertex to it self.
Articulation point: It’s a vertex that if removed will disconnect the graph.
neighbours: 2 vertices with an edge between them.
Bridge: edge that if removed will disconnect the graph.
Cycle: path that starts and end at the same vertex.
Component: a connected part of a graph (if a graph is connected then it has only a component).

Types of graph

Tree: a graph with no cycles and connected.
Forest: a graph with no cycles.

Simple graph: a graph undirected, with no loops and no more than one edge between 2 vertices.
Regular graph: every edge of the graph has the same degree.
Bipartite graph: a graph in which is possible to define two groups of vertices such that every edge of the graph connects vertices of different groups.
Complete graph: a simple graph in which for each vertex there is an edge connecting the vertex to every other vertex of the graph. This graph has n(n-1)/2 edges, where n is the number of vertices.I know that’s a looot to take and there is still a looooot more of graph information to know. But don’t worry about it, don’t memorize the types, you will be more familiarized with them over the time, so… Take it easy!But okay, back to the example, let’s try a challenge!! What every indexed expression in the text says about the graph (Come back to the problem explanation)?

 

 

(1) – edges
(2) – undirected graph
(3) – not simple
(4) – unweighted graph

(5) – vertices of the graph
(6) – What is the question? What is the number of vertices which the minimum path from a vertex v is equal or less to P.

How to represent a graph in a computational way?

There are 2 basic ways to do it: adjacency matrix and adjacency list. Each has some benefits and situations where it is more advantageous, in the end will see each in a more objective point of view trying to focus in when to use one instead of the other. But before let’s talk about how is these representations.

We know we must represent vertices and edges. But how to do it?

 

 Adjacency Matrix

An adjacency matrix consists of a matrix N x N, where N is the number or vertices of the graph and the lines represents the vertex from the edge goes, and the column represents the vertex to the edges ends. In a more practical way, the value 1  in  the line i, column is used to represent the existence of the edge from  to j, if such an edge doesn’t exists we use the value 0. If the graph is weighted we use an infinity value to represent the absence and the weight it self to represent the existence of an edge.

 

Graph VS Adjacency Matrix – 1

Adjacency List

 

The adjacency list represents each vertex and it’s connections in a list of vertices. If there is a connections between a vertex A and a vertex B, so in A list there will be B. In other words, we keep a neighbours list of each vertex. If the graph is weighted we also store the weight of the edge.
Graph VS Adjacency List – 1
Graph VS Adjacency List- 2
Comparing: adjacency list VS adjacency matrix
List VS Matrix
Matrix: in general it occupies less in the memory and if the graph is dense it’s the better choice, easy and efficient to verify existence of an edge between 2 vertices.
List: in general it’s more efficient in time, easier and efficient to verify who are the neighbours of some vertex.
Bibliography

 

A graph? What is it?

BLMWT #2 – Alessia Cara

Today I’ll talk about Alessia Cara. I knew her through Spotify and the moment I listened to her single, I started to show it all over my all social networks. Anyway, It’s an R & B sound, with some pop reference and a voice that reminds Amy Whinehouse voice’s, so… nice pop + nice R & B + talented girl with awesome voice = SUCCESS! She has some YouTube videos doing some covers and has just released a lot of authorial songs, including Here, that made me scream to the world that Alessia Cara is just awesome!

A little of Alessia Cara for you guys:

Here – Alessia Cara
BLMWT #2 – Alessia Cara

BLMWT #1 – The Expendables

I’ll try once in a while a band/singer that isn’t so famous as it should be, and I think it really worths it to listen to the music :D! The tag will be called BLMWT – Band that I love the most in the World Today.

This week’s band is The Expendables, the band is excellent and the sound is a mix of reggae with skate rock/hard rock that worths at least to hear an album.
And today I found out that they released a new album this year ❤ ❤ <3.
AND THE ALBUM IS GREAT!
Ps 1: They sound amazing live!
Listen to a bit of The Expendables! Hope you enjoy.

Ps 2: I listened their music for the first time because of Guitar Hero Warrios of Rock, their song was at a free patch of reggae music, right from the unbelievable. I download it with no expectations just to have more songs to play haha.

Lesson of the day: you never know where you’re going to find something awesome!

Guitar Hero song’s – Sacrifice
Down Down Down
New album 😀 – Sand in the Sky
BLMWT #1 – The Expendables

#Random Code 1 – Books Catalog/Catálogo de Livros 1802 (URI)

Hi! In this article we’ll discuss the Books Catalog from URI.
It’s a nice question that’s involves the following concepts: algorithm efficiency, think a bit, and Brute force.

So, talking about the problem! In summary we have different set of books, where each set defined by a subject (portuguese, math, physics, chemistry and biology). We know that each book of a certain subject has a value associated and we want to make a set composed by one book of each subject. Given a number K we want to know the sum of the K most valuable sets.

If is not clear, try to understand with the example bellow:

The input is composed by 6 lines, the 5 first are defining  the values of the books of a certain subject where the first number is how many books of this subject there is (1 <= n <= 5). Then there is n numbers, (v1,v2,v3,…vi, where i <= n and 1 <= vi <= 1000), these are the values of each book in the set. The next line is just K.  Sample:

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


In this case what is the answer? Well, K = 1 so we want to know the most valuable set possible. In this case a greedy solution works, we get the most valuable book of each subject and the sum is the answer  of the most valuable set possible.
Bellow in green there are the elements we are present in the set, and the answer would be 42.

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

8 + 9 + 8 + 9 + 8 = 42.

If K was equal to 2. We would be looking for the sum of the most valuable set + the second one. The second most valuable set, that is represented bellow in yellow, that sums up 41, so the answer is 42 + 41 = 83.
 
5 2 5 6 3 8
9 6 3 1 5
5 4 8 5 2 6
5 3 2 4 9 5
7 8 5 1 4
1
8 + 9 + 8 + 9 + 7 = 41.

Ok, nice… But when K > 1 we’ll have to choose some book to be removed and another one to be inserted in the set… that seems a hard choice…

So, how to use this idea in a simpler way?
Tip: always look at the input size.

 
 (number of books of each different set) is <= 5. That’s a pretty small number, and we can implement a “not so efficient” solution. We also know that K is less than P*M*Q*F*B

This make sense because we have to compose a set of (p, m, q, f, b),  p is portuguese book, m is a math book, …, so P*M*Q*F*B possibilities exists.

 

With these information we know that in the worst case P = M = Q = F = B = 5, so K5*5*5*5*5 = 5⁵ = 3125.

So…we can try all the possibilities!

 

for p in portuguese:
   for m in math:
      for f in physics:
          for q in chemistry:
             for b in biology:
                 (p + m + f + q + b) is a value of a possible set!

So if you put these possible values in a list, sort the list, and you’ll get your answer, right?

https://gist.github.com/mari-linhares/f4455cdf1115041d723c.js

#Random Code 1 – Books Catalog/Catálogo de Livros 1802 (URI)