You can assume, that whatever they are using, worst case is at least added on purpose. When I create a test case, using your 10000 cases example, let's say there is some value 0 <= MIN_N <= N <= MAX_N, and my algorithm is O(N^something). And there some other values in the problem that have their own ranges, but don't affect the order of my solution.
I would create groups along this lines: 1) 500 random cases choosing N uniformly in [MIN_N, MAX_N] , other variables are chosen uniformly. 2) 500 random cases choosing N uniformly in [MAX_N / 2, MAX_N] , other variables are chosen uniformly. 3) 2000 random where N == MAX_N, other variables are chosen uniformly. 4) 2000 which I consider worst case possible. Many times, groups 3 and 4 are practically the same, so I just create 4000 of group 3. However, that's only 5000 cases, what I do is now repeat those 5000 again in the input file, and I check if the second half of the output is the same as the first half, this has been very useful to find initialization (or lack of) bugs. Carlos Guía On Fri, May 21, 2010 at 5:26 AM, Abdelrhman Abotaleb < [email protected]> wrote: > @TripleM > No;My question is not to test my source code over the possible different > conditions. > [In this case I suggest as you say the boundary conditions for the problem > and a general case] > But I want to make the input files generator. > > i.e. generating a long input file in my PC to make sure that my code will > behave efficiently and in the > specified time and without any memory bugs. > > So to make such generator I should know the P.d.F they used > as if for example all the cases are the worst case in the input file then > may be simple algorithm take long time > but if the cases behave with a certain P.d.F then simple algorithm may > succeed. > > > Thanks a lot > > > > > On Fri, May 21, 2010 at 10:50 AM, TripleM <[email protected]>wrote: > >> Your code should always be able to work in the worst possible case. >> Namely, take the input that your code takes the longest to solve, and >> repeat that 10,000 times. >> >> On May 21, 7:00 pm, Abdelrhman Abotaleb <[email protected]> >> wrote: >> > I'm wondering about the probability density function used to generate >> > numbers in the input files >> > for example in the snappers chain [Codejam Qualification stage 2010] >> number >> > of test cases T >> > >> > 1 ≤ *T* ≤ 10,000. >> > >> > So What's the P.d.f of T !? >> > >> > and if you don't know ; what's the best P.d.f to simulate the input >> file!? >> > >> > Uniform ,Bernoulli ,Gaussian !? oe what? >> > >> > Thanks >> > >> > -- >> > Regards, >> > Abdelrhman.M. Abotaleb >> > >> > IEEE 2010 Student Chapter, >> > AC Active member >> > SPE 2009 Well Services Moderator >> > cairo.spe.org >> > >> > Major: Electronics & Communications >> > Minor: Computer Engineering >> > >> > -- >> > 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%[email protected]> >> . >> > 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%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. >> >> > > > -- > Regards, > Abdelrhman.M. Abotaleb > > IEEE 2010 Student Chapter, > AC Active member > SPE 2009 Well Services Moderator > cairo.spe.org > > > Major: Electronics & Communications > Minor: Computer Engineering > > -- > 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%[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.
