In [1]:
import numpy
import numpy as np
In [4]:
sample_input_arr = np.array([5,10,2,4,3,2,1],dtype=np.int32)
In [6]:
f = np.savetxt("sample_input.txt", sample_input_arr, fmt='%i',delimiter="\n")
In [11]:
N_H = 10 # <= 10000
C_max = 5 # <= 1000
c_low = 0
c_high = 10
filename = "sample_input_1.txt"
homes = np.random.randint(low=c_low,high=c_high, size=N_H)
input_arr = np.insert(homes,0,C_max,axis=0)
input_arr = np.insert(input_arr,0,N_H,axis=0)
In [13]:
np.savetxt(filename, input_arr , fmt='%i', delimiter="\n")
In [20]:
N_H = 500 # <= 10000
C_max = 1000 # <= 1000
c_low = 0
c_high = 1000
filename = "sample_input_2.txt"
homes = np.random.randint(low=c_low,high=c_high, size=N_H)
input_arr = np.insert(homes,0,C_max,axis=0)
input_arr = np.insert(input_arr,0,N_H,axis=0)
In [21]:
np.savetxt(filename, input_arr , fmt='%i', delimiter="\n")
In [95]:
N_H = 8000 # <= 10000
C_max = 800 # <= 1000
c_low = 0
c_high = 1000
filename = "sample_input_3.txt"
homes = np.random.randint(low=c_low,high=c_high, size=N_H)
input_arr1 = np.insert(homes,0,C_max,axis=0)
input_arr1 = np.insert(input_arr1,0,N_H,axis=0)
In [96]:
np.savetxt(filename, input_arr1 , fmt='%i', delimiter="\n")
In [99]:
N_H = 8000 # <= 10000
C_max = 800 # <= 1000
c_low = 0
c_high = 100
filename = "sample_input_4.txt"
homes = np.random.randint(low=c_low,high=c_high, size=N_H)
input_arr2 = np.insert(homes,0,C_max,axis=0)
input_arr2 = np.insert(input_arr2,0,N_H,axis=0)
In [100]:
np.savetxt(filename, input_arr2 , fmt='%i', delimiter="\n")
Make an artificial case where we expect to not go to any of the houses (too much candy from each home, as each home gives more than the maximum alloted pieces of candy)
In [25]:
case0_input_arr = np.arange(10,16)
case0_input_arr = np.insert( case0_input_arr,0,case0_input_arr.size-1,axis=0)
In [27]:
np.savetxt("case0_input.txt", case0_input_arr , fmt='%i', delimiter="\n")
Let $C_{\text{max}} = $ maximum pieces of candy a child can have (upper bound). The problem stipulated that $0\leq C_{\text{max}} \leq 1000$.
Let $N_H = $ total number of homes in the 1 neighborhood. The problem stipulated that $0 < N_H \leq 10000$.
Thus, there are $N_H$ homes, ordered consecutively; denote a particular home $h$ s.t. $h\in \lbrace 1,2,\dots N_H\rbrace$.
Let
$$
\begin{aligned} & c:\lbrace 1,2,\dots N_H \rbrace \to \mathbb{Z}^+ \\
& c: h\mapsto c(h) = \text{ number of pieces of candy given at home $h$, i.e. $h$th home } \end{aligned}
$$
For some $h_0,h_1$, s.t. $1 \leq h_0 \leq h_1 \leq N_H$, define $c_{\text{tot}}$:
$$
c_{\text{tot}} := \sum_{i=h_0}^{h_1} c(i) = c_{\text{tot}}(h_0,h_1,c)
$$
i.e. $c_{\text{tot}} : \mathbb{Z}^+ \times \mathbb{Z}^+ \times (\lbrace 1,2,\dots N_H \rbrace \to \mathbb{Z}^+ ) \to \mathbb{Z}^+$.
We want to find
$$
\max_{ h_0,h_1} c_{\text{tot}}(h_0,h_1,c)
$$
with $1 \leq h_0 \leq h_1 \leq N_H$,
and if there happened to be more than 1 $h_0$ that yields the maximum amount of candy of all possible (consecutive) sequence of homes from $\lbrace 1,2,\dots N_H \rbrace$, then select the lowest numbered first home $h_0$. This could be denoted (but this prior explanation makes it crystal clear what it means)
$$
\min_{h_0} \max_{h_0,h_1} c_{\text{tot}}(h_0,h_1,c)
$$
One possible iterative approach could be considered from the following line of thought:
Let (initially) $\begin{aligned} & h_{\text{start}} =0 \\ & h_{\text{end}} = 0 \\ & c_{\text{sum}}=0 \end{aligned}$
Then
$\forall \, h_0 \in \lbrace 1,2, \dots N_H \rbrace$, and
$\phantom{ \forall \, } \forall \, h_1 \in \lbrace h_0, h_0+1 \dots N_H \rbrace$,
consider $c_{\text{tot}}(h_0,h_1,c)$.
If $c_{\text{tot}}(h_0,h_1,c) > C_{\text{max}}$, we stop.
If $c_{\text{tot}}(h_0,h_1,c) = C_{\text{max}}$ and $c_{\text{tot}}(h_0,h_1,c) > c_{\text{sum}}$, then let $c_{\text{sum}} = c_{\text{tot}}(h_0,h_1,c)$ and stop, since we want the lowest numbered first home. Record the $h_0,h_1$ pair of integers where this occurred, in $h_{\text{start}}, h_{\text{end}}$.
If $c_{\text{tot}}(h_0,h_1,c) < C_{\text{max}}$, and if $c_{\text{tot}}(h_0,h_1,c) > c_{\text{sum}}$, then let $c_{\text{sum}} = c_{\text{tot}}(h_0,h_1,c)$. Record the $h_0,h_1$ pair of integers where this occurred, in $h_{\text{start}}, h_{\text{end}}$. We continue.
In [59]:
def main_loop_draft(input_arr):
N_H = input_arr[0]
C_max = input_arr[1]
homes_arr = input_arr[2:]
result = np.zeros(3,dtype=int)
for h_0 in range(1, N_H +1):
for h_1 in range(h_0, N_H +1):
c_sum = homes_arr[h_0-1:h_1].sum() # be aware of 0-based counting, i.e. counting from 0, of Python and C/C++
if (c_sum > C_max):
break
elif (c_sum == C_max): # obtained (abs.) max. pieces of candy allowed
if (c_sum > result[2]):
result[0] = h_0
result[1] = h_1
result[2] = c_sum
break;
elif (c_sum < C_max):
if (c_sum > result[2]):
result[0] = h_0
result[1] = h_1
result[2] = c_sum
if (result[2] == C_max): # obtained both (abs.) max pieces of candy allowed and lowest numbered 1st home
break
return result
We really shouldn't need to do the summation each time. Indeed, notice the relationship:
$$
c_{\text{tot}}(h_0,h_1,c) = c_{\text{tot}}(h_0,h_1-1,c) + c(h_1)
$$
so that $\forall \, h_0$, keep a "running sum" for the $c$'s.
So we have function main_loop, a serial implementation in Python.
In [90]:
def main_loop(input_arr):
N_H = input_arr[0]
C_max = input_arr[1]
homes_arr = input_arr[2:]
result = np.zeros(3,dtype=int)
for h_0 in range(1, N_H +1):
c_sum = homes_arr[h_0-1] # be aware of 0-based counting, i.e. counting from 0, of Python and C/C++
if (c_sum > C_max):
continue
elif (c_sum == C_max): # obtained (abs.) max. pieces of candy allowed
if (c_sum > result[2]):
result[0] = h_0
result[1] = h_0
result[2] = c_sum
break
elif (c_sum < C_max):
if (c_sum > result[2]):
result[0] = h_0
result[1] = h_0
result[2] = c_sum
for h_1 in range(h_0+1, N_H +1):
c_sum += homes_arr[h_1-1]
if (c_sum > C_max):
break
elif (c_sum == C_max): # obtained (abs.) max. pieces of candy allowed
if (c_sum > result[2]):
result[0] = h_0
result[1] = h_1
result[2] = c_sum
break
elif (c_sum < C_max):
if (c_sum > result[2]):
result[0] = h_0
result[1] = h_1
result[2] = c_sum
if (result[2] == C_max): # obtained both (abs.) max pieces of candy allowed and lowest numbered 1st home
break
return result
In [91]:
result_example = main_loop(input_arr)
In [92]:
print(result_example, input_arr[2:][result_example[0]-1:result_example[1]] )
In [97]:
%time result_example1 = main_loop(input_arr1)
In [98]:
print(result_example1, input_arr1[2:][result_example1[0]-1:result_example1[1]] )
In [101]:
%time result_example2 = main_loop(input_arr2)
In [102]:
print(result_example2, input_arr2[2:][result_example2[0]-1:result_example2[1]] )
In [ ]: