A virus gone viral

Computer Science Level 4

In a laboratory housed in kotebe micro-organisms were arranged in a $n\times n$ grid for studying purpose. By accident one of the laboratory technicians spills an infectious virus on some of the organism.This virus has the ability to infect the organism located immediately (east, west, north and south) of its already infected organism in $3$ microseconds.

How many microseconds does it take for a virus spilled at the center(i=j) of an $11\times 11$ grid to infect all the organisms.

Details and Assumptions

-Explicit example, $0$ means infected and $1$ means normal. If the virus was spilled on the center of a $3\times 3$ grid.

$\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{pmatrix}\overset { 3\mu s }{ \longrightarrow } \begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{pmatrix}\overset { 3\mu s }{ \longrightarrow } \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}$

For a total of $6$ microseconds.

The time between getting infected and infecting others is negligible.

The answer is 30.

1 solution

Thaddeus Abiy
Aug 19, 2015

Notice that the expanding area is a tilted square . After the $n$ th iteration , it will have a side length of size $n$ . The number of iterations until the matrix is filled is thus the size of the largest diagonal of the matrix. For a square matrix $n \times n$ where $n$ is odd, the largest diagonal is equal to $n$ . The total time $T$ it takes for the region to fully fill an odd square matrix with side length $N$ is:

$T = 3 ( N - 1) \mu s$

A virus gone viral

The answer is 30.

1 solution

0 pending reports