Help || Why greedy doesn't work in problem F

Revision en2, by StellarSpecter, 2024-08-13 21:23:53

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.

Tags thanks

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English StellarSpecter 2024-08-13 21:23:53 15
en1 English StellarSpecter 2024-08-13 21:23:01 1039 Initial revision (published)