Practice makes you perfect, but learning the best practices from some experts may boost your coding performances.
In this page you'll find the solutions to some practical problems that can help you to help you familiarize yourself with the challenge. But before moving on...
Get your own hands dirty with our kickstart training
Put theory into practice in a sandbox mode and try out the problems Code Masters have created for you.
problem 1 _ party
How to maximise the sum of some elements taken from a given array?
This first problem is straightforward.
Of course, every positive element helps us raise the sum, while negative elements can only decrease its value.
Because we can take as many elements as we want, it’s enough to do a complete search over the input array and take only the positive elements to find the solution.
Here’s the full python solution:
<span># Read the number of test cases</span>
T = <span>int</span>(<span>input</span>().strip())
<span># For each test case</span>
<span>for</span> i <span>in</span> <span>range</span>(T):
<span># Read the number of friends</span>
N = <span>int</span>(<span>input</span>().strip())
<span># Read the vector with their friendship rating</span>
V = <span>map</span>(<span>int</span>, <span>input</span>().strip().split(<span>" "</span>))
solution = <span>0</span>
<span># For each friend</span>
<span>for</span> v <span>in</span> V:
<span># If this friend has a positive rating</span>
<span>if</span> v > <span>0</span>:
<span># Add its value to the solution</span>
solution += v
<span># Print the solution</span>
print(<span>f"Case #<span>{i+<span>1</span>}</span>: <span>{solution}</span>"</span>)
problem 2 _ x-ray
Minimise the operation of a range increasing in an initial zero-filled array to reach the desired final values.
Things get more complicated in this second problem.
A simple greedy solution that works is to sum up all the positive differences between an element and its previous one.
This approach guarantees us the minimum number of operations to reach the given values.
Here’s the Python function to solve this test case:
<span># Function to solve a single test case</span>
<span><span>def</span> <span>solve_testcase</span>(<span>t</span>):</span>
<span># Get data from the test case</span>
(N, V) = t
<span># Initial number of operation</span>
solution = V[<span>0</span>]
<span>for</span> k <span>in</span> <span>range</span>(<span>1</span>, N):
<span># If the current value is greater than the previous one</span>
<span>if</span> V[k-<span>1</span>] < V[k]:
<span># Add its difference to the solution</span>
solution += V[k]-V[k-<span>1</span>]
<span># Returning the solution</span>
<span>return</span> solution
problem 3 _ antivirus
Given 4 different strings, find the unique common substring of length K contained in all of them.
To find the solution, we could use the bruteforce approach and try all the possible substrings of the four strings to find the common one. This approach, as mentioned our previous article, always provides the correct solution.
However, it’s not enough to solve all the levels proposed, as the input files in the strings get bigger and bigger.
Here’s the Python bruteforce function to solve a test case
<span># Function to solve a single test case</span>
<span><span>def</span> <span>solve_testcase</span>(<span>t</span>):</span>
<span># Get data from the test case</span>
(N, K, F) = t
<span># For each string of length K in N[0]</span>
<span>for</span> i0 <span>in</span> <span>range</span>(N[<span>0</span>]-K+<span>1</span>):
<span># For each string of length K in N[1]</span>
<span>for</span> i1 <span>in</span> <span>range</span>(N[<span>1</span>]-K+<span>1</span>):
<span># For each string of length K in N[2]</span>
<span>for</span> i2 <span>in</span> <span>range</span>(N[<span>2</span>]-K+<span>1</span>):
<span># For each string of length K in N[3]</span>
<span>for</span> i3 <span>in</span> <span>range</span>(N[<span>3</span>]-K+<span>1</span>):
<span># If all the 4 strings are the same</span>
<span>if</span> F[<span>0</span>][i0:i0+K] == F[<span>1</span>][i1:i1+K] == F[<span>2</span>][i2:i2+K] == F[<span>3</span>][i3:i3+K]:
<span># Returns the solution</span>
<span>return</span> <span>f"<span>{i0}</span> <span>{i1}</span> <span>{i2}</span> <span>{i3}</span>"</span>
We can write a second more efficient solution with a divide and conquer approach: instead of finding the common substring among all the possible four strings, we find the common substrings between the two groups, and then the common substrings among the common substrings.
With this approach, the solution is very similar to the first one except we split the four nested loops into two separate groups and then merge the two solution by finding the unique common substring.
The final Python function to solve a test case is thus:
def solve_testcase(t):
<span># Get data from the test case</span>
(N, K, <span>F</span>) = t
<span># Common strings between N[0] and N[1]</span>
solutions1 = []
<span># Common strings between N[2] and N[3]</span>
solutions2 = []
<span># For each string of length K in N[0]</span>
<span>for</span> i0 <span>in</span> <span>range</span>(N[<span>0</span>]-K+<span>1</span>):
<span># For each string of length K in N[1]</span>
<span>for</span> i1 <span>in</span> <span>range</span>(N[<span>1</span>]-K+<span>1</span>):
<span># If both strings are the same</span>
<span>if</span> <span>F</span>[<span>0</span>][i0:i0+K] == <span>F</span>[<span>1</span>][i1:i1+K]:
solutions1.append( (i0, i1))
<span># For each string of length K in N[2]</span>
<span>for</span> i2 <span>in</span> <span>range</span>(N[<span>2</span>]-K+<span>1</span>):
<span># For each string of length K in N[3]</span>
<span>for</span> i3 <span>in</span> <span>range</span>(N[<span>3</span>]-K+<span>1</span>):
<span># If both strings are the same</span>
<span>if</span> <span>F</span>[<span>2</span>][i2:i2+K] == <span>F</span>[<span>3</span>][i3:i3+K]:
solutions2.append( (i2, i3))
<span># Merge the solutions from the two groups:</span>
<span>for</span> (i0, i1) <span>in</span> solutions1:
<span>for</span> (i2, i3) <span>in</span> solutions2:
<span># If all the 4 strings are the same</span>
<span>if</span> <span>F</span>[<span>0</span>][i0:i0+K] == <span>F</span>[<span>1</span>][i1:i1+K] == <span>F</span>[<span>2</span>][i2:i2+K] == <span>F</span>[<span>3</span>][i3:i3+K]:
<span># Returns the solution</span>
<span>return</span> f<span>"{i0} {i1} {i2} {i3}"</span>