[gcj] Re: IOI 2011
IOI was announced first it seems: http://apps.topcoder.com/forums/?module=Thread&threadID=690423&start=0&mc=19 On May 24, 8:38 am, Bartholomew Furrow wrote: > I wasn't personally aware of that, but there's nothing we can do about it at > this stage. Did they announce their schedule before ours and have us not > take it into account, or vice versa? > > > > > > > > On Sun, May 22, 2011 at 6:35 PM, TripleM wrote: > > Are the Code Jam organisers aware that the GCJ onsite finals are > > scheduled for the last day of the IOI (http://www.ioi2011.or.th/ > > detailed_schedule)? While the 29th is the 'departure day', trying to > > get from Thailand to Japan in a single day, not including a 2 hour > > time difference or time to arrive and get settled, isn't really going > > to be possible. > > > -- > > You received this message because you are subscribed to the Google Groups > > "google-codejam" group. > > To post to this group, send email to google-code@googlegroups.com. > > To unsubscribe from this group, send email to > > google-code+unsubscr...@googlegroups.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-code@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] IOI 2011
Are the Code Jam organisers aware that the GCJ onsite finals are scheduled for the last day of the IOI (http://www.ioi2011.or.th/ detailed_schedule)? While the 29th is the 'departure day', trying to get from Thailand to Japan in a single day, not including a 2 hour time difference or time to arrive and get settled, isn't really going to be possible. -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: Round 2 2010 question D: MUCH simpler solution?
Numerical approaches like the one you suggest are always possible solutions to problems like these, but I'm afraid in this particular case they have absolutely no hope of giving the answer to the required accuracy. You say that 'as a safety margin we may have to go for 10^-7 or so' when deciding when to stop calculating for small boxes. But even if you stop when each box is of size, say, 10^-12, by that point there can be millions/billions of boxes left - multiplying this small error by the number of boxes will never give you an accuracy within 10^-6. I guess the best way of demonstrating this is if you simply try coding it; as you suggest, it is a simple algorithm, but you will quickly see how precision errors will cause it to fail. On Jun 6, 9:05 am, Reinier Zwitserloot wrote: > I'm really kicking myself for deciding to try and finish C-large which > failed, I should have spent the time to read D fully, realize the D- > small is just asking to calculate the intersection of 2 circles 10,000 > times, which is completely trivial - just google around for the > formula if you can't derive it yourself. Stupid, stupid, stupid - B- > complete, C-small (trivial - just emulate the entire grid) and D-small > together is more than enough to finish in the top 500. Blast. Oh well, > better luck for me next time. > > In the post-mortem analysis with a friend, before we read the official > contest analysis, we came up with an interesting alternative solution > for D which seems way simpler. I was wondering if someone could test > our analysis before I try to develop it. > > Here's the basic idea: > > Basically, we divide up the entire field into little square boxes. Per > such box, we check if it is entirely inside of A. If so, it > contributes its entire area to A. If entirely outside of A, it > contributes 0. If the box looks like it contributes only a part of it > to A, we simply divide our box into smaller boxes and recursively > apply this algorithm until we get such tiny boxes that simply taking > half the area of the box will be fine (will not result in a total > absolute error of more than 10^-6). > > There's one big intuitive leap you'd have to make which I'm not 100% > sure about, and it is this: > > Given the square box drawn by [x1,y1] to [x2,y2], then this entire box > lies inside of A if points [x1,y1], [x1,y2], [x2,y1] and [x2,y2] are > ALL inside A. Similarly, the entire box lies outside of A if all those > points lie outside of A. Said differently, if you draw any rectangle > anywhere on the field, if its corners are all either all in or all > outside of A, then the entire square is either all in or all outside > of A. > > This seemed to be intuitively true to me before I read the contest > analysis, but after reading it I'm more sure but still not math-savvy > enough to prove it. All this talk about convex shapes does seem to > point at that being true. > > If I may assume for a moment I'm not wrong there, then this algorithm > should be fast enough: > > Start out with the entire field as the original "root" box - it's 20k > by 20k points in the worst case. We grid this box up by drawing 16 > points inside of it, 4 by 4, evenly spaced. We check for each such > point if that point lies inside of, or outside of, A. This is trivial > - for each point and each goat, check the point against the pole > (center of circle) and the distance from pole to bucket (radius of > circle). Checking if a point is inside a circle is easy. If the point > is outside of any 1 goat-circle, it's outside of A. If it's inside all > goat-circles, it's inside of A. > > If you draw lines through our grid points you end up with 16 little > squares. For all squares where its corners all have the same state, we > can immediately calculate the total contribution to A of that box: If > all points are "out", that box contributes 0 area. If all points are > in, that box contributes (y2-y1)*(x2-x1) area. After this round we're > left with a couple of boxes that didn't have all 4 corners with the > same state. > > We recursively handle each such box by splitting it up into 16 new > smaller boxes. We escape our recursion algorithm like so: If the total > area of our box is less than 10^-6, we don't recurse and instead > return totalArea/2 as approximation of the total area contributed by > this tiny box. As a safety margin we may have to go for 10^-7 or so, > but the algorithm is fast enough for some leeway here to be certain > the error will be acceptable. > > Doing the math, considering that a reasonably modern computer can run > about 3 billion "does this point lie inside this circle" operations > every second, even in the worst case scenario this box-splitting > concept will easily fit: > > 3 billion per second, or, considering 5000 goats and assuming it's the > 3000th goat every time that decides, that's 1m points that can be > checked every second. We've got 1000 buckets to check, and 10 test > cases, so that really boils down to
[gcj] Re: Is there a mistake?
They are text files. You can open it with any text editor, including the ones you mentioned. On Jun 2, 3:22 pm, sam wrote: > hello everyone . best of luck for your competitons. > Can ayone please tell me how open the ".in" extension files(small.in > and large.in) > provided during the competition, I know its really late but still i > want to know. I have tried to open it with gedit,notepad++, notepad > but not gain. > please help if anyone can.. -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: question regarding c++ map implementation
Yes. On May 28, 4:52 pm, Ketan Joshi wrote: > Thanks guys, > > Just one thought though, > > The order of keys is a side-effect of the implementation. Was it really the > specification for maps implementation? > > ~Ketan > > > > On Fri, May 28, 2010 at 12:22 AM, Lev Neiman wrote: > > It is so the keys would be ordered in the map. This is useful in a lot of > > cases. When you iterate through entries in std::map you are iterating in a > > specific order. You can define that order yourself by giving map your own > > custom comparator. This is actually useful in a lot of cases. With hashmap > > there is no order to the entries. Also there is SGI's implementation of > > hash_map that I believe somebody already talked about in this conversation. > > - Lev. > > > On Wed, May 26, 2010 at 2:48 AM, Ketan Joshi wrote: > > >> Hi guys, > > >> This could be a wrong forum for such a question, but I am posting it here > >> anyways. > > >> I read somewhere that c++ maps are implemented using height balanced trees > >> (red black trees specifically). > > >> Why wasn't it implemented using hash tables? wouldn't it have been faster > >> specially since maps dont allow duplicate keys? > > >> ~Ketan > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "google-codejam" group. > >> To post to this group, send email to google-c...@googlegroups.com. > >> To unsubscribe from this group, send email to > >> google-code+unsubscr...@googlegroups.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-c...@googlegroups.com. > > To unsubscribe from this group, send email to > > google-code+unsubscr...@googlegroups.com > > . > > For more options, visit this group at > >http://groups.google.com/group/google-code?hl=en. > > -- > Blog:http://beingkejo.wordpress.com -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: Should large data sets be allowed multiple attemps?
The point of the time limit for the large is to prevent people from trying to submit slow solutions and then improve them, so there's no way they'd increase the time limit for that purpose. You should be 100% sure of your solution before downloading the input. On May 24, 8:38 am, ShayEr wrote: > The problem is that you can't really limit attempts, once the user > have the large set in hand he is free to improve its algorithm until > it solve the set in reasonable time. Once the user finish optimizing > it he can run the algorithm on the small set and check that he gets > the same result as the original (slow) one. > > I do thing however that there is room for improvement, for once I > would increase the time limit to 10 or even 12 minutes, this would > give me enough time to improve slow solutions and I would give a > penalty of 3 minutes per each minute the user has taken to submit the > solutions this will give a big advantage for fast solutions > > On May 21, 10:06 am, Dhruva Sagar 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 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 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 google-c...@googlegroups.com. > > > > To unsubscribe from this group, send email to > > > google-code+unsubscr...@googlegroups.com > > 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 google-c...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > google-code+unsubscr...@googlegroups.com > > 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 google-c...@googlegroups.com. > > To unsubscribe from this group, send email to > > google-code+unsubscr...@googlegroups.com. > > For more options, visit this group > > athttp:/
[gcj] Re: Arbitrary number of input
'11' is definitely happy in base 2. The square of the digits add to '10' in base 2; the squares of those digits add to 1. On May 25, 8:11 pm, maverick gugu wrote: > Hi, > i think i'm misinterpreting this question from that time. In the test > cases given in the question: > > The first one are bases 2 and 3. > The output for this input is given as 3. > But 3 when written in base 2 is 11 which is not a happy number. > > According to my code: I'm getting the smallest happy number > 1 for bases 2 > and 3 is 128. > > Can you please help me out with this? Is my understanding wrong? > > Thanks, > Maverick > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: GCJ 2010 R1A Problem B -- wata's code for small practice input ??
I should just point out that it is perfectly possible/likely wata's solution gave the correct answers to the small input he was provided with. A friend of mine failed to solve B-small despite 5 submissions; when he sent me his code it gave perfect results on the first small input I downloaded. On May 23, 7:57 am, "Eduardo T. Cardoso" wrote: > Hello, > > On Sat, May 22, 2010 at 10:23 AM, 김민현 wrote: > > Q) Do we need to submit a perfect code? > > As far as I understood, any method can be used to generate correct output > > within a given time. > > i.e.) editing by hands, using excel script, etc. > > Well, the rules say (or used to, I haven't checked for it this year, > but it's probably there still) that if you solve by hand (which is/was > allowed), you should submit a .txt or similar explaining the process > used to solve them. > > I'd say if you manually check and correct examples, you should > probably add comments to your source code stating what you did (or > rather, what needs to be done in case the answer is negative, for > example) or add a .txt explaining what you did and in which cases (and > probably why aswell). Of course fixing your code would be better, and > probably MUCH faster than checking and writing what you did, but > still, should be possible. > > I believe all they want is a way to replicate results (which is why > they require free compilers and stuff), but they won't be able to if > you don't tell them how you did what you did. A source code is > self-explanatory, but manual changes to the output are not. > > With all the information necessary to replicate, my guess is you're > free to do whatever you want. > > Friendly, > Eduardo > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: Small A Submission "Correct" highlighted
Nope. On May 22, 4:15 pm, Mark Hurd wrote: > In the end I only submitted small and large Problem A for Round 1A. > Both have been marked as Correct (and I took too long so I wasn't in > the top 1000). > > For me the small Correct is highlighted (background) in green. Does > that mean something? > > User: MarkHurd > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: The small and large input file
I don't think you quite understood what I meant. You said: "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." The test cases are deliberately designed so that this is never the case. A simple algorithm which performs badly on the worst possible input will not be good enough to solve the problem. On May 21, 9:26 pm, Abdelrhman Abotaleb 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 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 > > 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 google-c...@googlegroups.com. > > > To unsubscribe from this group, send email to > > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. > > To unsubscribe from this group, send email to > > google-code+unsubscr...@googlegroups.com > > . > > 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 google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: The small and large input file
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 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 google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: Should large data sets be allowed multiple attemps?
Also, 'large' isn't necessarily just about efficiency. There was a problem in an earlier contest which had a particular special small boundary case only tested in the large input. Plus very often you may not be able to solve the problem at all, but can write a completely different algorithm to solve the small case only, allowing for lots of strategy as to whether to attempt the large input at all. That sort of strategy is crucial in the next few rounds. On May 21, 6:57 pm, TripleM 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 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 google-c...@googlegroups.com. > > To unsubscribe from this group, send email to > > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: - application to find cheaters in gcj
It's pretty silly of you to say that GOOGLE IS NOT DOING JUSTICE when you don't even have a clue what they are doing. If you do not cheat, you will not get picked up for cheating, regardless of whether your algorithm is very similar to someone else's. If you do cheat, you will be caught. It is as simple as that. On May 19, 5:28 pm, Wasif Hossain wrote: > After the Qual. Round, I found that My logic (and the code also almost > similar) for SNAPPER problem is SAME as Neal.wu who is in 1st position. Then > what about this case? will I or Neal.wu be both SUSPENDED or not? Moreover, > I am from Bangladesh and he is from USA or some other country. If anyone of > us is suspended, then I think that Google IS NOT DOING JUSTICE because > nobody of us know each other. Again, if we both proceed to Round 1, then I > think that only SIMILAR CODE CHECKING is not done by google but something > else!!! My opinion is that, google checks the SAME IP Address first. If it > is so, then checks for the next criterion (Similar Code) , and only when > this is also proved, then the contestant is eliminated. Please let us know > your opinion. > > Thanks a lot. > > On Wed, May 19, 2010 at 3:20 AM, Muntasir Azam Khan > > > > wrote: > > > Isn't a smart cheater an oxymoron? What incentive does somebody have for > > > cheating in smart way? Is it like when a unskilled programmer pays a > > > skilled one to get them high rank in an algorithm competition or > > something? > > > > > There is lot more to do when it comes to identify the cheaters. > > > > > What if we just add a line trying to just print something or introduce > > > > some no op codes like > > > > i = i + 0 ; > > > > > what should we actually compare. at source, or assembly or binary > > itself. > > > > Basically how do we catch the smart cheaters. > > > > > let us not go by probability numbers here saying only 10% of code is > > > > similar hence the code is not copied as 90% of code is still original > > > > becuase it is often this 10% which is the real trick needed to solve > > > > the problem. > > > Actually, last year there were some lists of cheaters put up by users. > > These were generated using something much simpler than the approaches > > suggested here - mostly checked whether two submissions were exact > > matches or had an edit distance less than some small number. You can > > find lists of cheaters from last year in this forum thread at > > TopCoder: > >http://forums.topcoder.com/?module=Thread&threadID=650760&start=0&mc=41. > > The interesting thing is that even such simple checks found a huge > > number of cheaters in the Qual round. > > > But these were made by contestants, the GCJ admins will likely be > > employing different methods. > > > -- > > You received this message because you are subscribed to the Google Groups > > "google-codejam" group. > > To post to this group, send email to google-c...@googlegroups.com. > > To unsubscribe from this group, send email to > > google-code+unsubscr...@googlegroups.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-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: Should large data sets be allowed multiple attemps?
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 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 google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: Error in my C++ code
While using fmod(k+1,pow(2,n)) will work in this case, it is most
definitely not a good idea. Suppose the bounds were a bit bigger so
that 64 bit integers were required, rather than just 32-bit ones.
Then pow(2,60) is equal to 1152921504606847000, while 1LL<<60 is
1152921504606846976.
You should get in the habit of never using floating point arithmetic
when only integers are involved.
On May 17, 11:19 pm, Manish kumar Singh wrote:
> tonka,
>
> is using this statement a good idea?
> if (fmod(k + 1, pow(2, n)) == 0)...
> It worked.
>
>
>
> On Sat, May 15, 2010 at 11:45 PM, tonka wrote:
> > why the heck will you write such a clumsy and lengthy code??? take a
> > look at my code:
> > #include
> > #include
> > #include
> > #include
> > #include
> > #include
>
> > void main()
> > {
> > int t,flag=0,n;
> > long int k;
> > ifstream fi("A-large.in",ios::binary|ios::in);
> > ofstream fo("outputlar.out",ios::out);
> > fi>>t;
> > for(int t_c=0;t_c > {
> > fi>>n>>k;
> > if(((k+1)%(long int)pow(2,n))==0)
> > fo<<"Case #"<<(t_c+1)<<": "<<"ON"< > else
> > fo<<"Case #"<<(t_c+1)<<": "<<"OFF"< > }
> > fi.close();
> > fo.close();
> > getch();
> > }
>
> > This works for the large input also.
>
> > On May 14, 7:49 pm, Bharath Raghavendran wrote:
> > > I found one mistake : If b < PD, you are returning 0. Why is that?
> > > Lets say you have 4 switches, PD = 16. If b = 15, the answer should be
> > ON.
>
> > > Other than that, there are many ways you can improve your code.
> > > 1.
> > > dont use double. It will remove accuracy in many places. 10^8 will come
> > > within 4 bytes (usually int suffices this. else use long int).
>
> > > 2.
> > > To calculate 2^n, you can use the left shift operator. "int PD = 1< > will
> > > put 2^n into PD.
>
> > > 3.
> > > To check if b gives reminder PD -1, you don't need to run a loop. You can
> > do
> > > "if (b%PD == PD-1)"
>
> > > On 13 May 2010 10:47, Aamir Khan wrote:
>
> > > > #include
> > > > #include
> > > > #include
> > > > using namespace std;
>
> > > > #define _CRT_SECURE_NO_WARNINGS
> > > > #define For(i,a,b) for (long i(a),_b(b); i <= _b; ++i)
>
> > > > char buf[1024*1024];
>
> > > > bool isEven(long a,long b)
> > > > { bool result=0;
> > > > if(b%2==0)
> > > > result=0;
> > > > else
> > > > {
> > > > double ad=0.00;
> > > > for(int j=0;j<=30;j++)
> > > > {
> > > > if(int(ad)==a)
> > > > { break;}
> > > > ad=ad+1.00;
> > > > }
> > > > long PD=long(pow(2.00,ad));
> > > > if(b > > > result=0;
>
> > > > else
> > > > {
> > > > for(long i=PD;i<=1;i+=PD)
> > > > {
> > > > if(b==i-1)
> > > > {
> > > > result=1;
> > > > break;
> > > > }
> > > > }
> > > > }
> > > > }
> > > > return result;
> > > > }
>
> > > > int main() {
> > > > freopen("A-large.in", "rt", stdin);
> > > > freopen("output_Snapper_Chain.txt", "wt", stdout);
>
> > > > gets(buf);
> > > > long size=atoi(buf);
>
> > > > For(test, 1, size)
> > > > {
> > > > // cout<<"No. of loops"< > > > long N;
> > > > long K;
>
> > > > scanf("%d%d", &N, &K);
> > > > // cout<<"N"<
> > > > bool res=isEven(N,K);
> > > > if(res)
> > > > printf("Case #%d: ON\n", test);
> > > > else
> > > > printf("Case #%d: OFF\n", test);
> > > > }
> > > > exit(0);
> > > > }
>
> > ---
> >
> > > > SNAPPER CHAIN:
> > > > Can anybody tell me the errors in the code.i have done this
> > > > problem using the simple concept which i knowit is not giving
> > > > right output
>
> > > > Brief explanation of code:
> > > > i have first converted the long taken from file into the double using
> > > > for loop..then using pow function i have found 2^N and then found
> > > > whether k==2^N-1;
>
> > > > _
> > > > Aamir
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > Groups
> > > > "google-codejam" group.
> > > > To post to this group, send email to google-c...@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > google-code+unsubscr...@googlegroups.com
> >
> > > > .
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/google-code?hl=en.
>
> > > --
> >
[gcj] Re: Advancement notices
You will get an email once the first round scoreboard has been finalised. Which isn't yet, with the huge number of submissions. On May 16, 2:18 pm, tonka wrote: > i guess we just show up...i didn't get any invitation yet... > > On May 16, 1:01 am, Brian Watkins wrote: > > > Are we supposed to get invitations to the round ones at some point, or > > do we just show up at the one we want? > > > -B > > > -- > > You received this message because you are subscribed to the Google Groups > > "google-codejam" group. > > To post to this group, send email to google-c...@googlegroups.com. > > To unsubscribe from this group, send email to > > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
[gcj] Re: Fair handicap
While you're at it, take the competition at 5am. The same day daylight savings hits and you're meant to move the clock forward one hour at 2am the same morning. On Sep 23, 3:48 pm, Brian Watkins wrote: > Well, my favorite computer died this past weekend. And it'll take > another week to get my next one in the mail. > > In order to make Round 2 fair for everyone, I am requesting that all > of you, like me, borrow a machine from a friend or head out to an > internet cafe. > > Pick a new machine with a less or more responsive keyboard than you're > used to (bonus points for having some other language on the keycaps). > Use an operating system you're not familiar with. Deal with funny > settings on the ide or editor. Read the problems in a funny looking > font. Sit in a chair with uneven legs so that you feel like you're on > a slant. > > Just make it uncomfortable for yourself. It doesn't have to be a real > pain. A little nagging annoyance should make things nice and even so > as to give unfortunates like me a chance. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Contest analysis for 1A,1B and 1C are published
Anything to 7 decimal places is still within a precision of 10^-6, so the analysis is correct, and it won't be a typo. It is common to allow for much higher precision than asked for just in case you had an off- by-one error somewhere. On Sep 15, 9:01 pm, Matteo Landi wrote: > Round 1B, problem A: it seems the precision required would be 10^-6 > but the solution > shows 'print "%.7f" % Evaluate(tree, features)'. I suppose it to be a > typo error. > > Anyway, very nice analysis. > > On Tue, Sep 15, 2009 at 10:12 AM, ulzha wrote: > > > A minor glitch in 1C-C: // Start the computation. int r = 0; > > -- > m...@http://matteolandi.altervista.org/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Round 1C - All your Base pow function
pow is a floating point function, not an integer function, and doubles can not always store integers exactly. It is quite possible that it returns xxx.999 rather than an exact integer, and that will round down to the wrong value. You will also get in trouble comparing doubles for the same reason. On Sep 14, 5:19 pm, vaibhav wrote: > In this problem I used the pow function (present in math.h library of > c++).It got accepted for small test case but gave me wrong answer for > the large test case.When I later changed the program and used the > iterative method and calculated powers iteartively rather then using > the inbuilt pow function the answer was correct.when I compared the > files the difference between the answers varied from 1-20. I couldnt > qualify only due to this error. > > Can someone please through some light on this working of pow function. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: View contestants' source code?
I'm afraid you can't. Not many people will want their email addresses given out publicly. On Sep 14, 4:24 pm, LeMyPhuong wrote: > > I'm Java beginner and I'm new to codejam. I 've downloaded some solutions > > written in Java but I cannot understand clearly the source code. I'd like > > to contact directly with the contestants by email and I'd like to know how > > can I contact with them / or got their email addresses? > > Sorry if this is a silly question. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Ugly Numbers - 2008 Round 1C part B
1. The provided solution does do the opposite of that which is mentioned in the analysis, but that makes no difference whatsoever. dyn [i][x] will end up counting things equal to -x mod 210, which is exactly the same when x=0 which is the only one you want. 2. Because if x=3, cur=5, and sgn=-1, (x + sgn*cur)%MOD = -2. Adding an extra MOD makes it always positive. On Sep 12, 5:07 am, Bey wrote: > Hi, > I was trying to follow the solution to the 2008 problem Ugly Numbers > in Round 1C. I understand that it ought to be a Dynamic Programming > solution. Also, x % 210 and y % 210 tell you (x+y)%210 and (x-y) % > 210. However, I hope someone can help me with the following: > > 1. If the operation before character 'j' was '+', shouldn't the update > be dyn[j-1][(x-d)%210] rather than the other way round? > > 2. Why is there a +MOD in the line > dyn[j+1][(x+sgn*cur+MOD)%MOD] += dyn[i][x]; > > Note: I am following the solution from the Contect analysis > athttp://code.google.com/codejam/contest/dashboard?c=32015#s=a&a=1 > > Thanks! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: EMEA local onsites -- Bus Stops Problem
The problem says: 'At the end of the day all the buses must be in the last K bus stops (one bus per stop)' This is not true for the case you mentioned. On Aug 30, 8:56 pm, pos wrote: > Hello, > About the problem bus stops, for the second sample answer I think > there is a missing > schedule.http://code.google.com/codejam/contest/dashboard?c=32010#s=p3 > > the sample: > Input: > 3 > 10 3 3 > 5 2 3 > 40 4 8 > > Output: > Case #1: 1 > Case #2: 3 > Case #3: 7380 > > your explanation for the second case is: > For the second case the possible ways of planning are: > (A → 1,3,5. B → 2,4), > (A → 1,3,4. B → 2,5), > (A → 1,4. B → 2,3,5). > > I thin there is a missing schedule, > (A → 1,3. B → 2,4,5) > > What do you think? > Many thanks in advanced --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
[gcj] Re: Contest scoring question(s)?
Quoting from the rules: Penalty Time = Submission time of the last input you correctly solve (time is measured from start of contest) + four minutes for each incorrect small submission (only for small inputs you eventually solve) In particular, the first part isn't the time you solved the last small input; it's the time you last solved anything. If you're expecting to solve a large input, it makes no difference whether you've rushed through all the small inputs or not. You have to upload the problem code at the same time you submit your solution. Comments are completely meaningless in contests like this, all you're doing is disadvantaging yourself :P On Aug 26, 3:20 pm, Ken Corbin wrote: > Hello everyone, > > It appears that the base penalty time is the time elapsed from the official > start of the contest until you submit the answers to all of the small dataset > problems. Add 4 minutes for each resubmitted small dataset answer. You have > until the end of the allotted contest time to submit answers to the large > dataset problems, those do not appear to count against your base penalty > time. > > Consequently, the top programmers appear to be writing something quick and > dirty to solve the small dataset problems, then go back and solve all of the > large dataset problems. > > I'm also wondering how long we have to upload the problem code used to solve > the problem. Largely because I am rather appalled at the quality of the code > I find myself writing under extreme time pressure. Would be nice to go back > and add some decent comments before actually uploading it. > > Thanks a bunch, > -Ken --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~--~~~~--~~--~--~---
