My solution to the question BINSTR of November Long Challenge required 2 segment trees and a trie. When I was searching for a better solution, I came across a brute force solution in python which was accepted. I accept the fact that some languages provide built-in functions which can be directly used as compared to coding them in other languages. I also accept the fact that some languages require more execution time and hence, time multipliers are required to restore parity among languages.
But my question is, do the problem setters and others involve make sure that time multipliers are as less as possible? How can a BRUTE FORCE solution get an AC verdict??? Isn’t it unfair on others who code the entire solution?
In fact, in the previous long challenge, the question Coprime Components had a strict time limit of 0.5s when the setters solution had an execution time of 0.45s! So we’ve had two extremes covered in two long challenges.
@smelskiy@vijju123 Please try to come up with a solution to This Long Challenge problem
I have absolutely no complaints against those who’ve solved using brute force and with no offence to the solver, I’m adding the link to the brute force solution which got AC verdict: link
I hope the debate doesn’t end with the statement that “The language and multipliers are for all and its one’s fault if she/he isn’t making the best use of it”.
EDIT: Multiplier for PyPy2 has been reduced to 2. Thanks chef
That’s a good point. Do the multipliers vary from question to question, or are they set globally? I’ve always seen Java as 2x the problem statement time. Surely the execution time ratio between two languages will vary based on the particular algorithm. Coding the optimal algorithm in each language and setting the time limit based on real world benchmarking would be more fair. On the other hand, coding a particular algorithm in ~35 different languages to determine a fair time limit might place undue burden on the problem setters/testers. Has anyone encountered a situation where an optimal solution did not achieve the time standard because of a multiplier that was too low?
Pypy is almost equally faster as compared to c++. I think the time limit of Pypy should be same as that of c++. many time a simple brute force solution written in python get accepted in Pypy https://www.codechef.com/viewsolution/19153170 (another example from July 2018 long challenge)
I agree with you that coding optimal algos in each language and setting time limit is not possible. But, if its possible to use time multipliers for frequently used 4-5 languages, then I believe coding optimal algos in these languages and setting different time multipliers for different questions, something that doesn’t happen currently, seems to be the best way forward. I know that it’s easier said than done, but I hope that some measure is taken
Really surprised to see x5 for PyPy, I tried it once and thought it has same time limit with C++. With Python I struggled for 3 days and in the end I used brute force for TC 12-15. Still feeling a little guilty about it xD https://www.codechef.com/viewsolution/21548200
No offence taken. I absolutely agree with the point raised.
I spent more than a couple of days working on a persistent Radix tree solution and I couldn’t. I came to terms with not being able to solve the problem within the contest duration. And thus it was disheartening to me as well when I saw a brute force solution pass all the test cases. The time limit and the test cases should have been stricter not to allow such solutions to score even a single point.
@meooow - maybe it has, but should it? and x5? in any case, as the links I gave demonstrate, there isn’t a significant speed difference between them. @admin
My bad, I didn’t notice the “3” in your answer’s “PyPy3”.
It seems they forgot to set any multiplier for the newly added PyPy3, whereas PyPy2 gets 5x, which I too agree is way too much.
On a related note, the availability of numpy and scipy in Python is also kinda unbalanced.
According to me, The test cases for the problem were quite weak, There should have been a test case where l=0 and r=len for all queries and any language would have definitely failed for it. the only benefit python had in this question was its ability to handle big no.s and that too only up to a certain limit, so the test cases were definitely missing big no.s as well. pypy is not equivalent to c++ please get your facts correct. In fact it has happened with me many times that my solution works perfectly well in c/c++ and gives TLE pypy/python. python multiplier can be reduced to 3x I guess but not less than that, and if it was an ideal problem, python would have failed for sure but due to lack of good test cases it passed. I personally didn’t implement the python solution as I knew a brute would fail, as I thought the author would have included the worst case test cases.
When you say “python multiplier can be reduced to 3x” you mean Pypy2, right? In BINSTR I’m the only one who passed it with pure Python and I’m planning to put Python on hard problems’ full AC solutions before I die. So don’t make them any harder xD
