You should not think of small input and large input as two different
things. They are both input for the same problem and you are not
supposed to solve the problem twice. Unless you realize you can't
solve the large set in 8 minutes at all you should code a solution
that runs for the values given in the problem for both sets. Since
you know the largest case limits you should be able to choose a
solution with time complexity good enough for the large input, solve
the small input to check the correctness and, after you have the
confirmation that your algorithm solves the problem, run it with the
large input that can be considered the "real" problem you want to
solve.
In a nutshell, the test cases are not separate things, they
complement each other. You should evaluate the time complexity of
your solution before you begin to code. Only after you come up with
a fast enough solution or after you give up on getting to it you
should actually write your program.
Best regards,
Igor Ramos
On Fri, May 21, 2010 at 06:58, Dhruva Sagar <[email protected]>
wrote:
I'd like to point out one fact Paul. In real life, everyone gets
another chance :).
Life doesn't end there if you fail at any stage. You do not loose if
you made a mistake.
And most of all, in real life you do not have 4/8 minute deadlines
to make you realize that what you are doing is inefficient. Often
(at least for most of us mortals including me) it is only when the
'8' minutes are over that we realize we need to improve things.
That being said, I have no problems in particular with the GCJ rules
or the contests format, I simply accept it as it is.
But personally, just like Mr. Roy pointed out, I would like to get
'another chance' for large input in the scenario where my algorithm
proved inefficient to give a result in the stipulated time.
On Fri, May 21, 2010 at 14:47, Paul Smith <[email protected]>
wrote:
No, you're wrong - the large set to some problems last year contained
boundary cases that were not tested by the small input for one
problem. It's not a matter of whether the small input should be
enough, last year it explicitly was not.
And yes, you could cut the resubmission of small inputs and make the
competition a lot harder. If you did, you would cut off a lot of
amateur problem solvers from having fun in the CodeJam. You will
never win the CodeJam without solving a large input case, but there's
a lot of fun to be had solving the small input cases.
My real life scenario is not about interviews, they're as far from
real life as you can get! In real life a customer pays you to do a
job, at some point the job is finished or the money runs out. If the
money runs out without you finishing the job that is very bad indeed.
If you finish the job but you don't know whether your code is fast
enough to handle the environment it will be used in, that can you
really say you finished the job?
In the real world you would never give code to a customer and say
"Here you go, I hope it is good enough". You would say "Here you go,
I know it is good enough because I tested it under these conditions
which match the given requirements".
Paul Smith
[email protected]
On Fri, May 21, 2010 at 10:07 AM, r_debashis
<[email protected]> wrote:
> Hi TripleM,
>
> I differ from your view of large dataset. Large * is necessarily *
> about efficiency, otherwise small should be good enough for all
> boundary cases.
>
> Hi Paul,
> I am not sure which real life you are referring to. In my real life,
> if I implement one algorithm today during the course of my work and
> think of a more efficient way of doing it while going to bed tonight
> or a week or a month later, I can go back and implement that with no
> hassle at all. Looks like by real life you are mentioning a typical
> interview scenario, where somebody has to derive some algorithm in a
> period of half n hour to one hour. There also, if somebody comes up
> with a solution to begin with and a better solution 15 mins later,
as
> an interviewer I will be happy to accept that. I don't think any
> interviewer will be stubborn enough to say "hey you said that first,
> and hence I am going to stick to what you said first and not
listen to
> what you have to say now".
>
> My point is not about giving or not giving multiple attempts for
large
> set. It is about "if we give multiple chances to correct logical
flaws
> we should also give multiple attempts to correct efficiency flaws".
> Testing it with my own dataset is not to the point here, since we
can
> test the small data set for accuracy using our own test cases as
well,
> and hence we should not need multiple attempts for small data set as
> well.
> Like we have penalties for multiple submissions in small data set we
> can have penalties for timeouts for large data set as well. Which
will
> make things fair by giving more credit to the person who came up
with
> a better algorithm in the first shot as compared to the one who took
> multiple tries, exactly the same way as we credit the person who
comes
> up with the accurate solution in the first shot.
>
> Hi Lego,
>
> I was not referring to getting the result before the end and
reducing
> the suspense, I was mentioning about multiple submissions in case of
> timeouts. The result continues to remain unknown (for the sake of
> suspense or whatever :)).
>
> Thanks,
> Debashis
>
> On May 21, 1:26 pm, Lego Haryanto <[email protected]> wrote:
>> I totally agree with Paul ... we should test this on our own, not
relying on
>> the result of our attempt.
>>
>> Furthermore, it is more tense this way, ... not knowing the
result until end
>> of contest.
>>
>> Best,
>> -Lego
>>
>>
>>
>>
>>
>> On Fri, May 21, 2010 at 1:19 AM, Vinay Julme
<[email protected]> wrote:
>> > Well I guess we can resubmit in those 8 mins. So if you want to
improve
>> > your algorithm you can use the remaining mins when you feel
that your code
>> > won't run in given 8 mins.
>>
>> > Its very tough but still its possible.
>>
>> > Vinay Julme
>> > **************
>>
>> > On Fri, May 21, 2010 at 1:32 PM, Paul Smith
<[email protected]>wrote:
>>
>> >> In real life, when someone asks you for an algorithm to solve
a given
>> >> problem, do you think they have a judge program to check your
results?
>>
>> >> No! In the real world your answers will be used as if they are
>> >> correct, you will do testing to satisfy yourself that your
answer is
>> >> correct. And if your algorithm goes wrong you will get at best
bug
>> >> reports that hurt your reputation, at worst you will crash the
space
>> >> shuttle :-)
>>
>> >> If you think your algorithm might be wrong or too slow, test it.
>> >> Randomly create your own worst case large input, either from
scratch
>> >> or by pertirbing the small input, does it run in 6 minutes or
not?
>> >> Identify corner cases that might trip your algorithm up, and
run them
>> >> in tests.
>>
>> >> You talk like your destiny is not in your own hands!
>>
>> >> On Friday, May 21, 2010, Dhruva Sagar <[email protected]>
wrote:
>> >> > I happen to agree with Deebashis Roy here.I would like to be
able to
>> >> attempt for the large input several times as well.I am fine
with having a
>> >> maximum limit on that though, like if you can allow only 5
attempts or
>> >> something of that sort, that would be fine too.
>>
>> >> > But overall considering the fact that I am not one of the
top coders out
>> >> there :), I would really like to get more chances to try the
large input
>> >> once I know that my algorithm isn't great and there is scope
of improvement,
>> >> or if I know that I have to convert my algorithm to a faster
language like
>> >> C/C++.
>>
>> >> > On Fri, May 21, 2010 at 12:27, TripleM
<[email protected]>
>> >> wrote:
>>
>> >> > I wouldn't interpret it that way at all. It makes perfect
sense to me
>> >> > - it is extremely easy to have a tiny bug in your algorithm
that
>> >> > invalidates your entire effort. These tiny mistakes are
picked up in
>> >> > the small submissions; once you have got that correct you
are expected
>> >> > to be able to solve the large input without any further help.
>>
>> >> > On May 21, 5:25 pm, Debashis Roy <[email protected]>
wrote:
>> >> >> Hi,
>>
>> >> >> The format of the contest doesn't look very fair, given the
fact that a
>> >> person can submit the small data set multiple times in case of
incorrect
>> >> result but cannot re-submit the large data set in case of time
outs.
>>
>> >> >> To me, the small data set is more to check the accuracy of
the
>> >> algorithm whereas the large data set is to check the
efficiency of the
>> >> algorithm.
>>
>> >> >> If that is true then what gcj is saying translates to "we
will allow
>> >> you to correct your algorithm if you have an incorrect
algorithm, but we
>> >> will not allow you to improve upon your algorithm if you have
an inefficient
>> >> algorithm!!!"
>>
>> >> >> Any particular reason for this? :-)
>>
>> >> >> Thanks,
>>
>> >> >> Debashis
>>
>> >> >>
_________________________________________________________________
>> >> >> Climate, controversies and the changing signatures of
naturehttp://
>> >> green.in.msn.com/
>>
>> >> >> --
>> >> >> You received this message because you are subscribed to the
Google
>> >> Groups "google-codejam" group.
>> >> >> To post to this group, send email to [email protected]
.
>> >> >> To unsubscribe from this group, send email to
>> >> [email protected]<google-code
%2bunsubscr...@googlegr oups.com>
>> >> .
>> >> >> For more options, visit this group athttp://
>> >> groups.google.com/group/google-code?hl=en.
>>
>> >> > --
>> >> > You received this message because you are subscribed to the
Google
>> >> Groups "google-codejam" group.
>> >> > To post to this group, send email to [email protected]
.
>> >> > To unsubscribe from this group, send email to
>> >> [email protected]<google-code
%2bunsubscr...@googlegr oups.com>
>> >> .
>> >> > For more options, visit this group at
>> >>http://groups.google.com/group/google-code?hl=en.
>>
>> >> > --
>>
>> >> > Thanks & Regards,
>> >> > Dhruva Sagar.
>>
>> >> > --
>> >> > You received this message because you are subscribed to the
Google
>> >> Groups "google-codejam" group.
>> >> > To post to this group, send email to [email protected]
.
>> >> > To unsubscribe from this group, send email to
>> >> [email protected]<google-code
%2bunsubscr...@googlegr oups.com>
>> >> .
>> >> > For more options, visit this group at
>> >>http://groups.google.com/group/google-code?hl=en.
>>
>> >> --
>> >> Paul Smith
>>
>> >> [email protected]
>>
>> >> --
>> >> You received this message because you are subscribed to the
Google Groups
>> >> "google-codejam" group.
>> >> To post to this group, send email to [email protected]
.
>> >> To unsubscribe from this group, send email to
>> >> [email protected]<google-code
%2bunsubscr...@googlegr oups.com>
>> >> .
>> >> For more options, visit this group at
>> >>http://groups.google.com/group/google-code?hl=en.
>>
>> > --
>> > You received this message because you are subscribed to the
Google Groups
>> > "google-codejam" group.
>> > To post to this group, send email to google-
[email protected].
>> > To unsubscribe from this group, send email to
>> > [email protected]<google-code
%2bunsubscr...@googlegr oups.com>
>> > .
>> > For more options, visit this group at
>> >http://groups.google.com/group/google-code?hl=en.
>>
>> --
>> Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
>>
>> --
>> You received this message because you are subscribed to the
Google Groups "google-codejam" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to [email protected]
.
>> For more options, visit this group athttp://groups.google.com/
group/google-code?hl=en.- Hide quoted text -
>>
>> - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google
Groups "google-codejam" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to [email protected]
.
> For more options, visit this group at http://groups.google.com/group/google-code?hl=en
.
>
>
--
You received this message because you are subscribed to the Google
Groups "google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to [email protected]
.
For more options, visit this group at http://groups.google.com/group/google-code?hl=en
.
--
Thanks & Regards,
Dhruva Sagar.
--
You received this message because you are subscribed to the Google
Groups "google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to [email protected]
.
For more options, visit this group at http://groups.google.com/group/google-code?hl=en
.
--
You received this message because you are subscribed to the Google
Groups "google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to [email protected]
.
For more options, visit this group at http://groups.google.com/group/google-code?hl=en
.
