Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### flamestorm's blog

By flamestorm, 2 months ago, 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.  Comments (14)
 » 2 months ago, # | ← Rev. 2 →   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  » 2 months ago, # | ← Rev. 2 → 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. •  » » 2 months ago, # ^ | ← Rev. 2 → 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 orzTo 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   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)
•  » » » Ok.Thanks for the response.
 » 7 weeks ago, # | ← Rev. 2 →   I'm confusedIf 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 0 ans=0 for (int i = l; i < r; i++) { // if h[i] divisible by h[i + 1], add 1 to ans } 
•  » » for(auto i = l; i < r; ++ i) { if(h[i] is not divisible by h[i + 1]){ goto IGNORE_THIS_SUBARRAY; } } // Do stuffs with this subarray here. IGNORE_THIS_SUBARRAY:; 
•  » » And how exactly are you going to use that ans variable 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 ans by the condition.I'm not trying to troll you, I genuinely want you to understand.
•  » » » » » 7 weeks ago, # ^ | ← Rev. 4 →   Um_nik,'preciate this :)From the problem statement: such that for each i(l≤il, or 0
•  » » ans = true; for (int i = l; i < r; i++) { if (h[i] NOT divisible by h[i + 1]) { ans = false; break; } }