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.
You should've tagged Psychotic_D
What about this test?
Yeah thanks for this, It helped!
For me it became clear when the last sample testcase for the question did not work. I always got 36 instead of 35. Upon dry-testing, the greedy subroutine fails.
I cheesed the last sample testcase by setting each value as the last and sorting by min a,b, however that failed on testcase 3
Yeah I too did that, apparently greedy wasn't the way to go
That was the approach I also implemented during the contest, but it failed on the last test case from test 1. I tried to write it step by step on a paper, and it really wasn't correct, because greedy here won't make optimal decision everytime
The real reason why it doesn't work is because you can't prove it works.
You can prove that given $$$n = 1$$$, its optimal to just color as much as you can of the row/column that is closest to completion.
We will show that given any optimal answer for $$$n = 1$$$, there will also be an optimal answer that covers the row/column that is closest to completion. Assume that there is a optimal answer where we don't do that. Let's do some casework.
If the first row/column you eventually complete is the one that is the closest to completion, but you end up coloring squares that arent part of the row/column before completing it, you could've just completed the row/column first and then completed the rest. That will surely be optimal compared to the hypothetical solution.
If the first row/column you eventually complete is the one that is the longest from completion but you eventually fill the row/column that is the longest to complete, you could just fill the one that its closest to complete first and then repeat the rest of the answer. That will surely be optimal compared to the hypothetical solution.
If you never fill the row/column that is closest to complete, you can simply make an answer that only fills the row/column that is closest to complete intially. That will surely be optimal compared to the hypothetical solution.
That way, if we have any optimal answer, we have an optimal answer where we use the row/column that is closest to completion.
Technically we just proved that for the first row/column we complete but as you pointed out when we fill a row/column we just reduce to the initial problem of having an empty rectangle but with one less row/column, so we can keep applying this argument (if you want to be rigorous you would use induction)
However you cant prove that amongst all rectangles its always optimal to start from the one where its closest to complete a row/column. If you cant find a reasoning aside from "it makes sense" you shouldn't expect it to work.
in order to be sure, though, shouldn't you prove that it doesn't work?
To prove it doesn't work you need a counter example, he already has that. The thing I was trying to get across is that in a competition you need to find a strong reason why your algorithm works, not just implementing if you can't find a reason why it doesn't.
Of course, you can get away with guessing on easy problems, but they're easy because they are easy to guess. For harder problems you are likely to be guessing something wrong and be wasting a bunch of time trying to figure out whether the idea or the code is wrong.
oh I see what you're saying, thanks
in a competition you need to find a strong reason why your algorithm works, not just implementing if you can't find a reason why it doesn't.
I'll remember that, Also thanks for your insights!
Intuition/Guessing for <=C
Strong Reasoning for >=D
Agreed!