Invitation to CodeChef February Long Challenge 2021

announcement
23

Sure, no issues. Might have happened with rest as well. Do update for them as well.

Also, as I have barely solved the question. I would like to know why one of the solutions is WA.

I am flipping 0 edges and just removing the first (m-r) edges. It is not supposed to give any best answer and neither did I try for 100 points.
But it will still be a solution. Maybe give you a random sum of (A-B[r]), completely unoptimized.

This is what I saw on sample cases

24

Yes, all submissions are rejudged.

Just in case you are interested in some issues of your code:

  • midx can overflow the array, so it is like an undefined behaviour
  • you can’t flip edges randomly, it must be the diagonal of a convex quadrilateral
  • you can’t remove edges randomly, each removal should decrease the number of connected regions by one.
  • in your first submission, that somehow got accepted (before rejudge) you printed only M-R-1 removals, that suggests that there is an issue in one of the spoj servers, because there is an assert that checks that F flips are performed and M - R edges removals are printed.
1 Like
25

Hmm, as I said I barely solved or read the question. Will try to practice on it. Anyways, I was talking about flip=0 and the solution of mine where overflow problem wasn’t there.

But again, as I said I am yet to work on the question.

Thanks. Can close the chat.

26

Since you are not convinced, let me give you a simple example for flip=0 to give you a flavour.
Consider the example in the question:
M=7. Suppose R=2
Try to remove the 5 edges BF, DF, EF, GF, HF
Do you get 2 regions? You actually get 3, because when you remove HF, you actually disconnect a vertex F and it does not reduce the number of connected regions.

More generally, Number of regions = Number of initial regions - number of connected components +1 can be proved (so M-R edges removal only works if the whole graph remains connected after removing M-R edges, and that is a guarantee we don’t have if wee take random M-R edges)

1 Like
27

Agreed with you that regions should decrease by 1. I haven’t given a thought on this question and only spent 30 mins. If the solution wasn’t AC, I would have tried.

Let’s close the chat. I will try to solve in practice later on.

1 Like