Cheating teams

[Shanethe13]

I guess I got really lucky with question 4. Literally a week or two ago I wrote my own graphing calculator, using my own variation of the Shunting Yard algorithm. I had spent so many hours refining it, that I simply had to code from memory when I saw problem 4

[Unnamed.t]

A.J wrote:

#4 was the annoying one. I used Turing for #4, but I confess that I did predict that a bedmas question would be on and that probably gave me an advantage

Wowwww, I'm going to admit, it is pretty hard doing something like problem 4 inside Turing. I saw a reasonable solution in Java and started to rip my hair off (not literally) on why I hadn't used simplification methods in the program (e.g. replacing - with +- and " " with ""). I spent about 30 minutes trying to make a program but totally gave up. And just to know, other than Turing, what other languages do you use for DWITE competitions?

[A.J]

Oh, I mostly always code in C++. I occasionally use Turing for certain questions (though I should stop doing that...). I can PM you my programs from the past DWITE if you want.

[Unnamed.t]

Oh no no that's alright. I just wanted to see the programming capability of the language you use (the fact that it brought you in first place twice) Personally I would argue that Python actually fits best in the Dwite programming competition. The speed of Python in a good IDE is like the speed of a mclaren F1. Usually The first two problems of DWITE are always about speed.

[A.J]

Well, I personally feel that all the questions on DWITE are about speed. Usually, the questions are trivial algorithmically, so speed (and good luck) determines the top few spots. I include good luck, as I know of some teams whom have submitted solutions to the wrong questions, regardless of being on of the first teams to submit a solution.

I am just happy that for once in all of my highschool life I actually managed to do well in a contest (1st place overall for this DWITE season ). Those who know me know that I usually perform poorly in contests even though I usually don't lack the knowledge required to do well.

[Shanethe13]

A.J @ Fri Jun 04, 2010 11:33 pm wrote:

I am just happy that for once in all of my highschool life I actually managed to do well in a contest (1st place overall for this DWITE season ). Those who know me know that I usually perform poorly in contests even though I usually don't lack the knowledge required to do well.

Well, congratulations! If this season is anything to go by, you definitely do know what you're doing

[Unnamed.t]

You've got a pretty good point in saying that every problem is about speed. I guess that is up to your mathematical ability. Most of the time, problems 3 and 5 need a lot of thinking or "figure outing". This just goes to show that these competitions are about math just as much as programming.

Oh yeah, I forgot to ask, is there a setting you put on your dwite team to stop your code to be downloaded or is it something else? I'm not asking to see your code I just want to know if I'm able to do the same thing as to stop people from dowloading my code.

[A.J]

oh...right, I forgot to turn that off. Basically, at the TeamCP page click "Edit profile and roster", and at the bottom of your profile description there should be a checkbox "Show Team's Code For Past Contests:".

Well, I don't think it is much of mathematical ability as it is algorithmic knowledge that helps. If you have a basic understanding of some fundamental algorithms (such as determining the shortest path between two points on a graph) and if you can code them with sufficient speed, then you should be good. I should also mention that a lot of the questions (well, not a lot, but some) on DWITE tend to be ad hoc (as in you have to come up with an algorithm that suits the question). For these type of questions, I believe that it just comes down to speed (and maybe experience).

[Unnamed.t]

Right I totally agree with you. You just need the write experience with algorithms and be able to understand the question properly. Like which questions need recursion, which question needs an ASCII string function etc. Yeah and Thanks a lot for showing me how to change the settings for the ability to show ur code.

[A.J]

Hey, no problem. I have been giving this talk to newcomers to our CS club for 2 years now

[chili5]

Hey, AJ any chance you can explain #4? It was the only one that I had no idea how to approach. Well the weird thing is I got perfect on #1 and hardly understood what it was asking.

Then #5 was odd... got 5/5 but I still don't get it. I just checked if k % 2 = 0 or not. I dunno what told me to try that but it got perfect.

So really the only questions I actually understood how to do was 2 and 3.

[A.J]

Sure, I'll briefly explain the solutions to the problem set:

#1 - Basically, they are asking you for the xth significant bit of the binary representation of a number y. I believe the shortest way of doing it would be:

c++:

cout << (((1<<y)&x)==(1<<y)) << endl; //basically performs the bitwise 'and' operation on 1 followed by y 0's and the number x. If it is a 1, it should return 1 followed by y 0's. Otherwise, it is a 0.

#2 - Trivially checking for primes using the 'check up to sqrt' method works in time.

#3 - Performing a floodfill at point 'A' after changing it to an oil '#' suffices.

#4 - Now for this problem, it is just one big recursive (or iterative) function. Following the rules of BEDMAS and some ad hoc optimizations (which is not necessary for this problem at all, but efficiency does help) you can code it up. The use of stacks is quite helpful for this problem. I believe team 'Kuro's solution is quite compact, if you want an example. My code, on the other hand, rambles on and on, so I rather not use it as an example. Basically looking initially for matching brackets and evaluating the expression inside them following the order of operations is your safest bet. I am sorry that I couldn't be of more help, as one can only learn by looking at examples (being an ad hoc problem, examples do help quite a bit).

#5 - I guess the added story masks the simplicity of this problem. If we were to represent the snappers' state as a giant binary number (with '1' being on and '0' being off), realizing that snapping one's fingers is equivalent to adding 1 to this binary number is the essence of this problem (try working with a few examples to see what I am saying). From here it is easy to see that basically the answer is ON iff (with two f's!) the rightmost N bits of K are 1. @chili5 I guess you got lucky with assuming that k%2 works, as all the input values with an odd 'k' was one less than a power of 2, making the rightmost N bits 1's . But you were right in assuming that k can't be even.

I hope this cleared up any confusion