How to solve the problem STANOVI from COCI contest 4 ?
http://hsin.hr/coci/contest4_tasks.pdf It is the 6th problem.
2 Likes
well I know what the states of the dp are but I don’t know how to calculate them efficiently or how to transition between them there are n.m.16 states
consider a cell x,y then it has an edge with x - 1, y, x + 1, y , x, y + 1, x, y - 1 so in total 4 edges and 2^4 possible subsets (think each edge on and off) since there are n.m cells so in total n.m.16 states
I may be wrong though.
upd : editorials will be released in a day or two.