Question 5 - Cheapest Insertion Algorithm

A Flamengo fan living in Campinas made a promise that if their team reached the final of the 2025 Copa Libertadores championship, they would visit all the stadiums where Flamengo played during the knockout stages. Now that Flamengo has indeed made it to the final against Palmeiras, the fan must fulfill this promise before returning home to Campinas to catch a flight to Lima for the final.

To plan the most efficient route, the fan created a simplified map in the form of a graph, where each node represents a stadium and each edge is weighted by the distance between stadiums. Using the Cheapest Insertion heuristic, they determined their optimal itinerary.




What was the total distance covered on this journey?
A) 4085 Km
B) 4135 Km
C) 4140 Km
D) 5815 Km
E) None of the above

Original idea by: Eduardo Bouhid

Comentários

  1. Joao Meidanis2 de novembro de 2025 às 12:37

    Boa questão. Fiquei com ela, mas mudei um pouco a redação para simplificar, omitindo alguns detalhes não relevantes à solução. Também mexi no nome da competição, achei que fica melhor do jeito que coloquei.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Question 3 – Network Flow

Imagem
 The contractors for the new " Alphaville Barão Geraldo " luxury allotment have hired the brilliant students of the MO412 class to design a high-capacity water distribution network. The project's goal is to pump water from the campus lake (Node Lago ) through a series of seven interconnected retention dams (Nodes  A through G ) to the development site (Node Alpha) . The contract specifies that the network  must be able to deliver a minimum of 30,000 liters of water per minute . The students have produced the following design, with pipe capacities also measured in thousands of liters per minute: Analyze the following propositions regarding the network's performance and limitations. I.  Suppose that, to budget cuts, the pipe from  Dam E to Dam G  must be downgraded to a capacity of 5,000 L/min. With this hypothetical change, the contractual minimum delivery of 30,000 liters/minute would  still be met . II.  To improve performance, a proposal is mad...
Leia mais

Question 4 - Avg. next neighbor degree

Imagem
Consider the following example of a standard fully-connected Multilayer Perceptron (MLP), a type of artificial neural network. It has an input layer, a single hidden layer, and an output layer. In this architecture, neurons in one layer are connected to all neurons in the immediately following layer, but there are no connections within a layer or connections that skip layers. Here, the input and output layers have 5 neurons each, while the hidden layer has 10 neurons. Based on this description, would you expect the correlation exponent,  μ, to be: a) µ > 0 b) µ < 0 c) µ = 0 d) µ > 1 e) None of the above Original idea by: Eduardo Bouhid
Leia mais

Question 2 - Strongly Connected Components

Imagem
Barabasi's  Network Science   book describes the World Wide Web as a directed network where nodes are web pages and links are URLs. Imagine a small portion of this network for a university department: A Homepage (H) links to an About page (A) and a Research page (R).  The About page (A) links back to the Homepage (H). The Research page (R) links to three specific Publication pages (P1, P2, P3). Each Publication page (P1, P2, P3) links back to the main Research page (R). Based on the concept of Strongly Connected Components (SCCs) and the Kosaraju-Sharir algorithm, consider the following propositions: Propositions: I. An SCC is any set of nodes where every node is mutually reachable from every other. Therefore, because a path exists from R to P1 and back, the set {R, P1} is a valid SCC. II. In the context of the World Wide Web, an SCC represents a maximal set of web pages where a user can navigate between any pair of pages within that set. Based on this, the set {H, A} is...
Leia mais