Codeforces 661 div 3

Round 661 was for div 3, supposedly all tasks were too easy for my rating, but I experienced troubles with 4 of them.


Task E sounds trivial, but I spent a lot of time trying to code it to no avail.


So we have people at integer coordinates from 1 to N, and they have to perform exactly one step. A step could be either changing their position by -1, 1 or not moving. We need to calculate the minimum and maximum possible number of occupied cells.


The idea is simple, a person only have 3 possible moves and the resulting state only depends on state of 3 previous cells, so we can do dynamics by position and state of last 3 cells (for that position).


d[i][state].mn = minimum amount of cells occupied for person at position i where last 3 cells look like state after he's put.
d[i][state].mx = maximum amount of cells occupied for person at position i where last 3 cells look like state after he's put.


But it turned out I didn't figure the transition out exactly.



To Be Continued...