|
|
Revision History |
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|