In 1873F - Money Trees in the statement it is written:
- ...choose a contiguous subarray of the array $$$[h_l, \dots, h_r]$$$ such that for each $$$i$$$ ($$$l \leq i < r$$$), $$$h_i$$$ is divisible by $$$h_{i+1}$$$....
We received many clarifications from many people of the form "if $$$l \leq i < r$$$, then $$$l < r$$$, so how can $$$l=r$$$ in the sample?" Since this is an important concept, I just wanted to explain it in a bit more detail here.
First thing to note: the statement $$$l \leq i < r$$$ is not a constraint on $$$l$$$ and $$$r$$$. The only constraints on $$$l$$$ are $$$r$$$ will be written in the input section. $$$l \leq i < r$$$ is just so we can establish the values of $$$i$$$ for which we care about the divisibility condition.
Think of it like this: this is equivalent to the for loop below.
for (int i = l; i < r; i++) {
// check h[i] divisible by h[i + 1]
}
In particular, what will happen if $$$l = r$$$? The for loop will simply not run, meaning that if $$$l=r$$$ there is nothing to check, so the statement is vacuously true, and so any subarray of size one satisfies the divisibility condition (there is another condition that we need to satisfy, but that's besides the point).
Consider another example: suppose we said we want to find the longest subarray so that all elements of the subarray are equal. More formally, this can be written as: for each $$$i$$$ ($$$l \leq i < r$$$) we need $$$a_i = a_{i+1}$$$. For instance, the answer for $$$[1,2,3,3]$$$ is the subarray with $$$l=3,r=4$$$. What's the answer for array $$$[1,2,3]$$$? It should be any array of length one, because in an array of length one the only element is of course equal to itself.
So this is why we usually take vacuous truth! Since there is nothing to prove, we say it is true.
To be honest, I always used to find the idea of vacuous truth both fascinating and weird. Anyways, it is more intuitive if one thinks like this: If there exists a single $$$i$$$ such that $$$h[i]$$$ is not a multiple of $$$h[i+1]$$$ ($$$l \le i<r$$$),then the subarray doesn't satisfy the condition, in the subarray of length $$$1$$$ no such $$$i$$$ exists, so it satisfies the condition ;)
I think it would have better to represent this condition as i ∈ [l, r] because the condition above definitely implies that l is less than r in my opinion.
Actually on closer checking, i disagree (tho your version wud be better)
The statement says for all i, such that l <= i < r, if no such i exists, then l < r need not hold anyways since the inequality itself is not invoked.
flamestorm orz
To clarify why $$$l \le i < r$$$ is not a constraint on $$$l$$$ and $$$r$$$, reword it as "For each integer $$$i$$$ such that $$$l \le i < r$$$ is true..." or "For each integer $$$i$$$, if $$$l \le i < r$$$ is true, then..."; the second rewording in particular makes it clear why vacuous truth holds.
In Div 4 Is the first AC solution taken as final.If i submit another during in contest should'nt the last ac be considered.If i feel first AC might get hacked and i should be able to submit another soln during contest.Please look into this and clarify.
If your first ac gets hacked, the second one counts (if it doesnt get hacked too) otherwise the first one. (This is for div4/div3/edu rounds with icpc style not div1/div2)
I'm confused
If we think of it as the for loop that you gave. "In particular, what will happen if
l=r?The for loop will simply not run" => so, ans will be equal to 0And how exactly are you going to use that
ansvariable to check if the condition is satisfied?I meant if the array is of size 1, there is no h[i+1], so, the rule is broken.
What rule? Explain what rule is imposed on
ansby the condition.I'm not trying to troll you, I genuinely want you to understand.