flamestorm's blog

On vacuous truth
By flamestorm, 15 months ago, In English

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.

  • Vote: I like it
  • +219
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
15 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ;)

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

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.

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
15 months ago, # |
  Vote: I like it +48 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it -10 Vote: I do not like it

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.

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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)

    → Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 0

ans=0
for (int i = l; i < r; i++) {
    // if h[i] divisible by h[i + 1], add 1 to ans
}
→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it 
    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:;
    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    And how exactly are you going to use that ans variable to check if the condition is satisfied?

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I meant if the array is of size 1, there is no h[i+1], so, the rule is broken.

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    ans = true;
for (int i = l; i < r; i++) {
    if (h[i] NOT divisible by h[i + 1]) {
        ans = false;
        break;
    }
}
    → Reply