2000F - Color Rows and Columns
Greedy: First we find which dimension is the smallest say it's x (and it's partner dimension is y), we keep colouring x until x=y-1, now we can colour y-1 twice for y-1 cost each and we will have (x-1,x) as resulting dimension. We keep doing it until we get to say (0,1) which means we have one row/column coloured for no extra cost!
We can implement this strategy by using some visited array to keep marking indices etc. I have done the implementation but it's failing on some random testcase. I can't even dry run why is it not working. Can anyone help me with it by providing a testcase where greedy fails and why DP is the way to go.
Tagging my fav ppl (if you're free, please respond)
Fav. LGM neal. (sorry, tourist doesn't count)
Fav. IGM Shayan
Fav. IM aryanc403
Fav. CM stefdasca
Fav. Expert jatrophalouvre
Thanks for your time for reading it.