Practice makes you perfect, but learning the best practices from some experts may boost your coding performances.
This page contains the last three problems from the 2020 Reply Code Challenge - Teen Edition. Let’s take a look at them...
Train with the 2020 Reply Code Challenge problems!
Get your own hands dirty and test your skills, trying out the problems of past editions in sandbox mode.
problem 1 _ scoreboard
Managing a real-time scoreboard with lots of participants
The solution to the first problem is straightforward. It only requires implementing the real algorithm used to generate the Challenge scoreboard.
To find the final scoreboard, we just need to evaluate each of the valid input platform logs as described in the problem statement.
Source code of a test-case solution:
<span>def</span> solve_testcase(t):
<span>N</span> = t[<span>0</span>]
<span>L</span> = t[<span>1</span>]
<span>logs</span> = t[<span>2</span>]
<span>scored</span> =<span> [[[0,0,0,0,0] for _ in range(5)] for _ in range(N)]</span>
<span>penalty</span> =<span> [0 for _ in range(N)]</span>
<span>score</span> =<span> [0 for _ in range(N)]</span>
<span>for</span> (ts, t, p, i, s) in logs:
<span>t</span> -= <span>1</span>
<span>p</span> -= <span>1</span>
<span>i</span> -= <span>1</span>
<span>if</span> s == <span>0</span>:
<span>continue</span>
<span>if</span> scored[t][p][i] == <span>1</span>:
<span>continue</span>
<span>scored</span>[t][p][i] = <span>1</span>
<span>penalty</span>[t] += ts
<span>score</span>[t] += (i+<span>1</span>)*<span>100</span>
<span>ranking</span> =<span> [ (-score[i], penalty[i], i+1) for i in range(N)]</span>
<span>ranking</span> = list(sorted(ranking))
<span>ranking</span> =<span> [r[2] for r in ranking]</span>
<span>return</span> <span>" "</span>.join(map(str, ranking))
problem 2 _ cloud server
From the software to the hardware
The second problem asks you to find a range of servers in a list who’s total power sum is at least the required amount.
The first level of the problem can be solved easily, using a brute force approach. Try all the possible subsequences, sum the value of the servers, and check if it’s the best solution so far.
Source code:
<span><span>def</span> <span>solve</span>(<span><span>input</span></span>):</span>
<span># read input</span>
[N, P] = <span>list</span>(<span>map</span>(<span>int</span>, <span>input</span>.readline().strip().split()))
V = <span>list</span>(<span>map</span>(<span>int</span>, <span>input</span>.readline().strip().split()))
l = <span>0</span>
r = <span>0</span>
best = <span>2</span>**<span>63</span>
<span>for</span> i <span>in</span> <span>range</span>(N):
<span>for</span> j <span>in</span> <span>range</span>(i, N):
s = <span>sum</span>(V[i:j+<span>1</span>])
<span>if</span> P <= s < best:
best = s
l = i
r = j
<span>return</span> <span>" "</span>.join(<span>map</span>(<span>str</span>, [l, r]))
This approach is very slow for big numbers, but you can optimise it a little by constructing the subsequences step by step and using their values.
Source code:
<span><span>def</span> <span>solve</span>(<span><span>input</span></span>):</span>
<span># read input</span>
[N, P] = <span>list</span>(<span>map</span>(<span>int</span>, <span>input</span>.readline().strip().split()))
V = <span>list</span>(<span>map</span>(<span>int</span>, <span>input</span>.readline().strip().split()))
prefix = [<span>0</span> <span>for</span> _ <span>in</span> <span>range</span>(N)]
prefix[<span>0</span>] = V[<span>0</span>]
<span>for</span> i <span>in</span> <span>range</span>(<span>1</span>, N):
prefix[i] = prefix[i-<span>1</span>] + V[i]
l = <span>0</span>
r = <span>0</span>
best = <span>2</span>**<span>63</span>
<span>for</span> i <span>in</span> <span>range</span>(N):
<span>for</span> j <span>in</span> <span>range</span>(i, N):
s = prefix[j]
<span>if</span> i > <span>0</span>:
s -= prefix[i-<span>1</span>]
<span>if</span> P <= s < best:
best = s
l = i
r = j
<span>return</span> <span>" "</span>.join(<span>map</span>(<span>str</span>, [l, r]))
Unfortunately, this solution is still not enough as it requires a lot of time in the last levels. To solve the problem completely, we have to use a sliding window algorithm: we keep in mind a range of valid servers.
At each step, we’re going to add new values in front of the range and remove all the unnecessary values from the back of the range. Again, the solution is the best value found in all the steps we’ve performed.
Source code of a test-case solution:
<span>def</span> solve_testcase(t):
<span>N</span> = t[<span>0</span>]
<span>P</span> = t[<span>1</span>]
<span>V</span> = t[<span>2</span>]
<span>l</span> = <span>0</span>
<span>r</span> = <span>0</span>
<span>best</span> = <span>2</span>**<span>63</span>
<span>att</span> = <span>0</span>
<span>i</span> = <span>0</span>
<span>for</span> j in range(N):
<span>att</span> += V[j]
<span>while</span> att >= P and i < j:
<span>if</span> att < best:
<span>best</span> = att
<span>l</span> = i
<span>r</span> = j
<span>att</span> -= V[i]
<span>i</span> += <span>1</span>
<span>return</span> <span>" "</span>.join(map(str,<span> [l, r]))
</span>
problem 3 _ scheduler
How to to find the minimum time required to execute all the tasks by choosing a limited amount of servers?
To solve this problem, it’s important to know if we choose an amount of time that we can easily find how many tasks a single server can do:
number of task = (available time - startup time)/(time for a task)
With this formula it’s also easy to find out if it’s possible to execute all the required tasks in the available time, just by summing up all the biggest K numbers of tasks.
The following function returns true if the amount of time given is enough to solve the problem. Otherwise, it’s false.
<span><span>def</span> <span>can</span>(<span>x</span>):</span>
<span># How many tasks a server can do in x time?</span>
<span># | (x-startup)/(time for task) |</span>
t = []
<span>for</span> [s,p] <span>in</span> C:
<span>if</span> x >= s:
t.append( <span>int</span>((x-s)/p) )
t.sort()
<span># Biggest K sum up to M?</span>
<span>return</span> <span>sum</span>(t[-K:]) >= M
We can use this function to find the solution efficiently.
Thanks a to binary search over all the possible values of time, we can find the minimum required time to solve the problem.
Source code of a test-case solution:
<span><span>def</span> <span>solve_testcase</span>(<span>t</span>):</span>
N = t[<span>0</span>]
K = t[<span>1</span>]
M = t[<span>2</span>]
C = t[<span>3</span>] <span># Computer [startup, time for task]</span>
<span><span>def</span> <span>can</span>(<span>x</span>):</span>
<span># How many tasks a server can do in x time?</span>
<span># | (x-startup)/(time for task) |</span>
t = []
<span>for</span> [s,p] <span>in</span> C:
<span>if</span> x >= s:
t.append( <span>int</span>((x-s)/p) )
t.sort()
<span># Biggest K sum up to M?</span>
<span>return</span> <span>sum</span>(t[-K:]) >= M
<span># Binary search of time</span>
l = <span>1</span>
r = <span>2</span>**<span>60</span>
<span>while</span> r-l > <span>1</span>:
mid = <span>int</span>((l+r)/<span>2</span>)
<span>if</span> <span>not</span> can(mid):
l = mid
<span>else</span>:
r = mid
<span>return</span> l+<span>1</span>