We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
i) if the array has no positive elements:
for an array of N zeroes, always taking the first valid split yields a score of N-1, which is the best possible
ii) otherwise the array has some positive elements.
claim: any two such arrays differing only by leading/trailing zeroes have the same score. eg score(00110) = score(11) , score(0012003400) = score(120034), etc.
proof: (use induction on length of array) given arrays A and B that differ only by leading/trailing zeroes. any valid splits break them into strictly smaller arrays L(A),R(A) and L(B),R(B). we can show that L(A) and L(B) can now differ only by leading/trailing zeroes (*). so their scores are the same, by induction hypothesis. likewise for R(A), R(B). it follows that score(A) = score(B). QED
from (*) any two splits of an array A that is not all zeroes, differ only in leading/trailing zeroes, and therefore their score is the same, by Claim.
so to sum up, in case (i) the first split is the best, and in case (ii) it doesnt matter which split we choose anyway.
Nikita and the Game
You are viewing a single comment's thread. Return to all comments →
i) if the array has no positive elements: for an array of N zeroes, always taking the first valid split yields a score of N-1, which is the best possible
ii) otherwise the array has some positive elements.
claim: any two such arrays differing only by leading/trailing zeroes have the same score. eg score(00110) = score(11) , score(0012003400) = score(120034), etc.
proof: (use induction on length of array) given arrays A and B that differ only by leading/trailing zeroes. any valid splits break them into strictly smaller arrays L(A),R(A) and L(B),R(B). we can show that L(A) and L(B) can now differ only by leading/trailing zeroes (*). so their scores are the same, by induction hypothesis. likewise for R(A), R(B). it follows that score(A) = score(B). QED
from (*) any two splits of an array A that is not all zeroes, differ only in leading/trailing zeroes, and therefore their score is the same, by Claim.
so to sum up, in case (i) the first split is the best, and in case (ii) it doesnt matter which split we choose anyway.