JOIN
Get Time

Member Search

SEARCH
forums  Revision History
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)

vexorian
3710 posts
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)

vexorian
3710 posts
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)

vexorian
3710 posts
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)

vexorian
3710 posts
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)

vexorian
3710 posts
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)

vexorian
3710 posts
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)

vexorian
3710 posts
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.