If worried about Time Limit Exceeded... [Contest Strategy]


  • 6

    There are only 15 possible inputs, so if you're worried about your solution being too slow or if your solution is too slow, you can just precompute all answers and submit an O(1) solution. If your precomputation is so slow that it takes minutes, you can even let it run in the background while you're solving the next problem(s). Remember that your contest ranking doesn't depend on the sum of your problem times but on the largest one.

    def countArrangement(self, N):
        return (1, 2, 3, 8, 10, 36, 41, 132, 250, 700, 750, 4010, 4237, 10680, 24679)[N - 1]

  • 0
    V

    I think that it's a fair observation on how the contest can be cheated. It would be better if the problem, for this particular case, does not specify a limit, and, have a higher limit. We could also check that the run-time is not 0 ms for a large input, but it can be countered by input-related delays.

    @administrators On a related note, is it possible to reveal the next content problem only after the previous problem has been accepted (may be allowing to give up)? It should discourage teamwork (to up the trust in the results, not to blame anyone). Since problems are in the order of difficulty, and we have a good number of people who solve all problems, I do not think this should create problems.


  • 3

    @votrubac I don't think it's cheating at all. I think it's a legitimate strategy. Even in the real world. And even in an interview I think it would be good to mention that this could be used.

    I'm strongly against your proposal. If someone gets stuck with the first problem, they shouldn't be forced to give up on it for good or to give up on the entire contest. I think it would be awful.


  • 1
    V

    @StefanPochmann Any strategy is good if it works. I think that, specifically for contests, it's better if such strategies do not work. If the true goal is a reasonably fast generic algorithm, we should not penalize people who spent time and came up with such an algorithm. There are times when a person gets an insight and comes up with a really simple solution, but I do not think that it's the case here.

    With respect to my proposal. I overheard from my offshore contractor that they have an "interest group", which is cracking contest problems with 4 groups of 2-3 people (1-2 pair programming, 1 googling), each working in parallel. True or not, but now I am wondering how lucky one should be to solve 4 problems in 14 minutes two contests in a row.


  • 0
    V

    Another idea - you can skip the problem with 600 seconds penalty. This may be sufficient. Either way - I think that this issue needs to be addressed, and a reasonable trade-off could be found.


  • 0

    @votrubac said in If worried about Time Limit Exceeded... [Contest Strategy]:

    I am wondering how lucky one should be to solve 4 problems in 14 minutes two contests in a row.

    Did someone achieve that? I couldn't find it.


  • 0
    V

    Look at first place in #19 (0:14:15), #18 B (0:22:11), #16 B (0:21:45). It's the same person, a student from China. I looked at the winners for contest #15 and earlier, and the time ranges from 36 minutes to an hour, which makes more sense.


  • 0

    @votrubac Ah, so not really 14 minutes twice. And it does look at least reasonable. Used 3, 3, 4 and 4 minutes for the problems, and used C++ with the same block-bracket style for all four problems. And #16B only had three problems.

    Anyway, I don't think your penalty idea would work. People could still use one account to read all problems at once and then use another to submit solutions.


  • 0

    This question is relatively easy, I mean getting a right answer is relatively easier and faster for me to calculate precompute all answers... Trying this kind of strategy is not a practical idea I think.


  • 0

    @zhugejunwei Well I've already seen a solution posted that was too slow for getting accepted but easily fast enough to make the precomputation approach feasible.


  • 1
    V

    @StefanPochmann For a hard problem, it would typically take more than 4 minutes to read the description and type the code (assuming you remembered the exact solution right away). Plus, few more minutes to check for edge cases and run a few times. You can get that lucky once in a while, but unlikely 11 times in a row.

    I got your point regarding multiple accounts. But in this case penalty won't work for submissions as well - I can automatically minimize and obfuscate my code (or use a different language, e.g. C# vs. Java), and submit it first using another account. I never tried it myself, but I think that this should fool the plagiarism checker.

    Another idea: we can show the next problem after the previous was accepted or after a timeout. E.g., the second problem is revealed at 6:45 PM, third - 7 PM, and so on.


  • 0
    Y

    @votrubac I agree with the concept of identifying the teams versus the individuals. There are several cases of the top "people" submitting solutions less than 60 seconds after the previous question. There is nothing to stop a team working in parallel and it's not against any rules as far as I can tell.
    However I understand that it can be frustrating for an individual to get a disappointing contest ranking because they are working alone in series competing against groups working on the questions in parallel. I don't have a great way to stop it.
    As a first step I think when joining a contest we could be asked whether to sign up as either a group or an individual and the results are split accordingly. Yes people can still cheat if they really want to but it an individual who consistently submits multiple questions within seconds will stand out.


  • 0
    V

    @yorkshire @administrators Why can't we reveal the next problem after the previous one was accepted, or after a time period (say, 10 minutes) for those who got stuck. This should not affect the experience, but equalize a bit groups and individuals. As a related topic, I don't think cash prizes is a good idea in the environment where a cheating team work is possible and make economical sense. I believe points/premium subscription of equal value can be used instead, and the rank itself is a sufficient motivator for passionate programmers.


  • 0
    Y

    @votrubac
    I did some analysis on this and posted it here ... in new thread, hope you find it interesting
    https://discuss.leetcode.com/topic/83860/teamwork-in-contests


  • 0

    If there is only one problem in the contest, teamwork will not work any more.

    Or we could use time frame for each problem instead of showing them at the beginning of the contest. For example, The 1st problem shows when the contest begins. After 10 minutes the 2nd problem shows, then after 20 minutes show the 3rd one, after 20 minutes show the 4th one. This method could benefit those who do the problems sequentially and quickly. @1337c0d3r @administrators


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.