You are not logged in. Please login at www.codechef.com to post your questions!

×

Unfairness of Time Multipliers

12
3

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 :P

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 :D

asked 13 Nov '18, 02:56

harshmmodi's gravatar image

6★harshmmodi
243110
accept rate: 0%

edited 01 Dec '18, 00:03

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

(13 Nov '18, 14:47) tieros4★

@tieros and now you come to know that all the TC can be solved using brute force xDD

(13 Nov '18, 17:36) harshmmodi6★

Well, we will see what we can do. Its very dicey to say the least...

(13 Nov '18, 20:20) vijju123 ♦♦4★

okay.. Thanks. The test cases, too, might've been weak. So, alternatively, that could also have been the issue.

(13 Nov '18, 22:19) harshmmodi6★

There's some mistake with the multiplier there. PyPy shouldn't get x5, only (interpreted) Python. Certainly PyPy3 didn't get x5.

link

answered 13 Nov '18, 04:35

joffan's gravatar image

5★joffan
9338
accept rate: 12%

edited 13 Nov '18, 05:31

Apparently PyPy2 has a much larger time limit than PyPy3.

(13 Nov '18, 14:45) meooow ♦6★

@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

(13 Nov '18, 17:59) joffan5★
1

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.

(13 Nov '18, 18:43) meooow ♦6★

Yes, they're not standard library modules and I feel should not be included.

(13 Nov '18, 22:02) joffan5★

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.

link

answered 13 Nov '18, 17:02

trijeet's gravatar image

6★trijeet
2355
accept rate: 25%

"Not even a single point".. bro, let people breathe :P :P

Completely agree with you though

(13 Nov '18, 17:25) harshmmodi6★

Completely agreed! I spent two days thinking about how to solve the problem, a day to debug, still got TLE (using two segment trees and tries), replaced a segment tree with sparse table and finally got AC. Now finding the fact that brute force in PyPy2 worked, I don't feel screwed just a little disappointed. Multipliers should be based on individual problems if possible, otherwise as close to optimal requirements for each language (I know that is a tough thing to decide) but PyPy is nearly as fast as C++, it shouldn't need a multiplier of 5. I think a multiplier of 2 is reasonable (correct me, if I'm wrong).

link

answered 16 Nov '18, 22:53

gkashish's gravatar image

5★gkashish
111
accept rate: 0%

lol, we got screwed !

link

answered 13 Nov '18, 03:52

shravank's gravatar image

2★shravank
1
accept rate: 0%

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?

link

answered 13 Nov '18, 05:00

jlewis200's gravatar image

5★jlewis200
222
accept rate: 0%

1

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

(13 Nov '18, 12:39) harshmmodi6★

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)

link

answered 13 Nov '18, 06:37

vipin1407's gravatar image

5★vipin1407
2045
accept rate: 13%

edited 13 Nov '18, 09:16

1

For PyPy the memory consumed is certainly much more than C++, so probably they should not be the same. But the concerned admins should look into this.

(13 Nov '18, 11:46) amitrajit_bose3★

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.

link

answered 13 Nov '18, 19:14

panik's gravatar image

5★panik
1127
accept rate: 7%

1

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

(13 Nov '18, 23:48) tieros4★

yeah I meant pypy2

(16 Nov '18, 20:31) panik5★

The language and multipliers are for all and its one's fault if she/he isn't making the best use of it

link

answered 17 Nov '18, 09:12

brainstorm_1's gravatar image

2★brainstorm_1
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×154
×128
×31

question asked: 13 Nov '18, 02:56

question was seen: 1,907 times

last updated: 01 Dec '18, 00:03