Let me introduce you to the following two important functions:
I don’t believe, of course, that this is the first time you may have encountered them. Nor that they are even half as complicated as the definitions above would suggest.
But although they appear rather awkward, what I wanted for those formulations to highlight is one particular way of interpreting the min and max functions as they are used in code. You may think it’s easy enough to read them quite literally (“get me the smallest/largest value”), and in many cases you are absolutely correct:
Often though, we don’t want to get the extreme value from a set, list, vector or other collection of unspecified size. Instead, we call the min/max functions on a few arguments that are known and “hard-coded” upfront. In many cases, this is mostly done to spare us from introducing a verbose if
statement, or a more cryptic ternary operator (?:
).
Or is it? I was recently surprised when discussing some very simple programming exercise on one of the IRC channels I frequent. Someone pointed out how my proposed solution is quite unusual with its (over)use of the max
function. The task goes somewhere along these lines:
You are presented with a device that has n counters (c_{0}, …, c_{n-1}) and n+1 buttons (b_{0}, …, b_{n}). Every counter c_{i} is incremented whenever a corresponding button b_{i} is pressed. Additionally, pressing the extra button b_{n} sets all the counters to the maximum value displayed on any of them (e.g. [1, 4, 3] → [4, 4, 4]).
Find a way to compute the final state of all counters given a sequence of k buttons presses.
Just by reading the above description and implementing it in the most straightforward way, we can trivially arrive at an algorithm which solves the problem in O(nk) time. And since we need to go through the sequence of button presses at least once, the lower bound for complexity of any other solution is therefore O(k).
My version was a simple improvement over the obvious one, scoring O(n+k) at the cost of maintaining a negligible amount of extra data:
The noteworthy application of max
function was responsible for updating one of those values:
If you look closely, you will notice how the first argument serves as a reference point, while only the second one is the actual ‘input’. What this invocation is saying is essentially “make max_state
at least as big as it was before – and possibly bigger”.
Hardly a groundbreaking insight, eh? This approach, however, allows to rapidly parse even complicated applications of min
and max
. If you encounter, for example, an inlined version of a “clamping” function that is written in the following manner:
I’m pretty sure it will take you at least a few moments to grok what it’s doing. The max
–min
compound is puzzling, and the meaningful arguments (a and b) are disconnected from the function names. Had it had more nesting, you might even have needed to *gasp* count the parentheses.
But we know it’s all about trimming a number to the <a; b> interval. Why not express it in a way that readily highlights this fact?
max(a, ...)
means “I want the result to be at least a“.
min(b, ...)
means “I want the result to be at most b“.
Making both thresholds into first arguments to their respective functions is just one of those nice small things that very subtly, almost invisibly, will make your code easier to work with.
Hi Xion,
AFAIU, your solution is incorect. For the following input:
2 3
1 3 2
you output: 1 1
while the correct answer seems to be: 1 2.
Notice that I slightly changed the way I refer to buttons and counters, compared to original exercise. I’m actually surprised it doesn’t blow up with IndexError for your data!
The adjusted input should be:
2 3
0 2 1
and for that you get the expected answer 1 2.
why do you then subtract one in line 28?
presses = [press - 1 # index buttons from 0
for press in map(int, sys.stdin.readline().split())]
2 3
0 2 1
produces “presses = [-1, 1, 0]”
It works only because python accepts negative indexes.
state[-1] and state[1] in this case refers to the same counter.
Input:
2 3
1 3 2
returns wrong answer because pressing 3 should set 2nd counter to 1st counter’s value, but you leave it to your loop with “max(min_state…”(21, 22).
While 2nd is still equal 0, its button is pressed and your “clever solution” fails.
To fix that you only have to compare counter’s value with min_state every time its button is pressed.
18. states[press] = max(min_state,states[press])+1
Also presses_count is unnecessary – you don’t use it anywhere (presses are read by sys.stdin.readline()).