JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Algorithm Matches SRM 534 Re: Proof of the following solution for div2-500/div1-250 Revision History (6 edits)
 Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) Mine was a response to vasja_p's post mostly. I haven't answered your post because I am not even sure it is correct yet. If it is correct, it is probably indirectly for the same property as the super easy solution. But I am not sure yet.Edit: It is correct, according to bruteforce through all possible states at least.Edit: If dp[i-1] is true, then we can tell the sum of distances between all checkers smaller than i-1 and cell (i-1) is odd. If we add a new cell, then for each cell we add 1 to the distance. If the number of cells before i (note that there was a typo here) is odd, then we will add an odd number to the sum of distances (We will toggle its parity). If the number of cells is even, then we will add an even number (parity stays the same). If dp[i-1] is false, then we can tell the sum of distances to (i-1) was even, and the same logic applies.Note that if a cell in cell (i-1) exists, its distance to (i-1) will be 0. That's the reason that when calculating dp[i] we don't need to care about how dp[i-1] didn't consider it.
 Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) Mine was a response to vasja_p's post mostly. I haven't answered your post because I am not even sure it is correct yet. If it is correct, it is probably indirectly for the same property as the super easy solution. But I am not sure yet.Edit: It is correct, according to bruteforce through all possible states at least.Edit: If dp[i-1] is true, then we can tell the sum of distances between all checkers smaller than i-1 and cell (i-1) is odd. If we add a new cell, then for each cell we add 1 to the distance. If the number of cells before i (note that there was a typo here) is odd, then we will add an odd number to the sum of distances (We will toggle its parity). If the number of cells is even, then we will add an even number (parity stays the same). Note that if a cell in cell (i-1) exists, its distance to (i-1) will be 0. That's the reason that when calculating dp[i] we don't need to care about how dp[i-1] didn't consider it.
 Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) Mine was a response to vasja_p's post mostly. I haven't answered your post because I am not even sure it is correct yet. If it is correct, it is probably indirectly for the same property as the super easy solution. But I am not sure yet.Edit: It is correct, according to bruteforce through all possible states at least.Edit: If dp[i-1] is true, then we can tell the sum of distances between all checkers smaller than i-1 and cell (i-1) is odd. If we add a new cell, then for each cell we add 1 to the distance. If the number of cells before i (note that there was a typo here) is odd, then we will add an odd number to the sum of distances (We will toggle its parity). If the number of cells is even, then we will add an even number (parity stays the same). Note that if a cell in cell (i-1) exists, its distance to (i-1) will be 0. That's the reason that when calculating dp[i] we don't need to care about how dp[i-1] didn't consider it.
 Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) Mine was a response to vasja_p's post mostly. I haven't answered your post because I am not even sure it is correct yet. If it is correct, it is probably indirectly for the same property as the super easy solution. But I am not sure yet.Edit: It is correct, according to bruteforce through all possible states at least.Edit: If dp[i-1] is true, then we can tell the sum of distances between all checkers smaller than i-1 and cell (i-1) is odd. If we add a new cell, then for each cell we add 1 to the distance. If the number of cells before (i-1) is odd, then we will add an odd number to the distance (toggle). If the number is even, then we will add an even number (parity stays the same). Note that if a cell in cell (i-1) exists, its distance to (i-1) will be 0. That's the reason that when calculating dp[i] we don't need to care about how dp[i-1] didn't consider it.
 Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) Mine was a response to vasja_p's post mostly. I haven't answered your post because I am not even sure it is correct yet. If it is correct, it is probably indirectly for the same property as the super easy solution. But I am not sure yet.Edit: It is correct, according to bruteforce through all possible states at least.
 Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) Mine was a response to vasja_p's post mostly. I haven't answered your post because I am not even sure it is correct yet. If it is correct, it is probably indirectly for the same property as the super easy solution. But I am not sure yet.
 Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) Mine was a response to vasja_p's post mostly. I haven't answered your post because I am not even sure it is correct yet. If it is correct, it is probably for the same property as the super easy solution. But I am not sure yet.