Invitation to CodeChef February Long Challenge 2021

I guess that the constraints are extremely tight for the sumxor2 problem to pass with python/pypy in the time limit. I don’t see any complete AC submission for this problem with python in any division.

Wouldn’t relatively smaller constraints be better so that the problem can be solvable with any language with optimal algorithm ? I don’t think this would lead to permitting suboptimal algorithms to pass. Problems on codeforces keep somewhat relatively smaller constraints on all their problems(for same time complexity questions compared to codechef) and most of the time all the problems can be solved in any language with the optimal algorithm without requiring any time multiplier as well(and sub optimal algorithm in any language fails as well).

In your division only, there is an AC submission in python and is fast enough for it.
If I had to reduce the constraints, I would have also reduced the time limit. So, it won’t matter.
Also, how do you know your algorithm is optimal?

Oh my bad I overlooked it. I’m not saying my algorithm is necessarily optimal, just based on the submissions. Also I didn’t mean to just point out this one problem, most of the problems on codechef follow this trend.

Pretty interesting, because I and most others have the opposite experience that Codeforces does not give any multiplier, so the chance of bad solutions passing is higher in C++ compared to Python there, but not here. I even had a case where I just read input in python and did nothing and it still TLEd on Codeforces in hacking phase because i was using input() function.

It is perfectly possible that your algorithm is optimal asymptotically and can still fail some test case because of some constant factor. That constant factor can come in from the data structures you are using, the times you are copying objects, etc. etc. Some things in Python are proven to be very slow way beyond the 5x factor and Codechef, Codeforces or anything will not help if you are having that.

Suggestions:

  1. If problem has a limit if size N, try to find some K such that the code for N/K runs without a TLE. (you can find this by actually ignoring the input and solving a smaller problem), then depending on the value of K you can judge if you need to optimize your algorithm or implementation. (you can do this during Long as there is no penalty for wrong answer)
  2. Of course, if you are confident, it might also be wise to just learn basic c++ syntax and rewrite it in c++
4 Likes

Thanks for the suggestions!

This post was flagged by the community and is temporarily hidden.

Can someone recheck the scoring of CUTCAKE? It’s mentioned that the minimum score attainable is 6e8 (600000000) after modified judge but someone has a score lower than that.

You should ask such questions in the comments section of the concerned problem

I did there as well. There was no response so just posted here for more visibliity. It’s reasonable to say that with less than 44 hours left for the contest, how this is resolved will determine the strategy how people approach the problem with the remaining time. Many won’t even try if they get 0 regardless of what they submit

1 Like

The minimum score is indeed 6e8 for the public test files.

The checker looks fine. We are looking into the issue.

3 Likes

I think the tasks are very interesting! Thanks for the amazing contest!

(UPD: My favorite tasks are Cell Shell and Bash Matrix. The tasks are quite beautiful!)

2 Likes

Key to AC to both the game theory problems- write recursive brute force with caching - observe the pattern.

2 Likes

I would like to bring to your attention that the issue has surfaced again for Div2.

Thanks again for all your work

Correct. The submission belongs to me.

It has been written to get partial points in the challenge.
Where I flip the first edge and remove the next (M-R) edges.

As testcases are randomly generated, I am not randomly removing the edges. And only the first (M-R) edges.

The output should not be 12. At best, 10^8 should have been added. And please correct it.

Also, would like if Codechef makes better checker in next contests. As after seeing full AC, I stopped working on the problem and did not have time at the end of contest. Might have actually done something to get better solution if error was not at checker’s end. And maybe would have gotten some points.

1 Like

when rating will be updated?

It is a weird error, your implementation doesn’t print a valid output. Also it has an undefined behaviour. When I run it in the testing page it always gives wrong answer.

I didn’t find bugs in the checker. My guess is that under some circunstances one of the SPOJ servers is not running the spoj_asserts. We’ll rejudge submissions and update ratings in div2.

1 Like

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

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

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.

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