JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Cookbook update (new prizes!) | Reply
We keep writing recipes for Algorithm and Marathon chapters, and to provide a bit of extra motivation for you, we're adding short-term rewards.

The first 12 contributors to deliver an approved recipe for one of these chapters, will win a TopCoder t-shirt. The t-shirt will be shipped out as soon as the review board approves the recipe - no waiting for the book to be published!

Each of the eligible recipes must be done by only one person from start to finish; with optional comments from other members. This means that you have either to finish a recipe you have already submitted in round 1 or 2, or write a recipe nobody has started yet. If you want to write a recipe but are unsure what it should look like, check the accepted recipes and/or contact me for comments on the specific recipe.

We also want to remind you that the top 60 contributors on the Cookbook project receive a free copy of the Cookbook once it is published. So far it is virtually every competitor, so hurry up to grab your freebies!

Next posts in this thread will provide the list of recipes with notes on their status. "accepted" means that it is approved (and is getting a t-shirt ASAP); "started by" means that there is a draft of this recipe somewhere so its author can finish it; "not started" means that anybody can write it; "needs some thought" means that I still have to invent some way to fit the material of this recipe in actual recipe format and welcome any suggestions.

Also note that comments on existing recipes are welcome, however, minuses without explanation are not. If you minus a post because you dislike the poster, it's ok (from process point of view); but if you think the recipe is somehow flawed, please comment this, so that we can improve it (and honor your contribution appropriately).
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
1. Algorithm Competition

1.1. Getting Started
Understanding SRM competition format accepted (mart0258, Nickolas)
Submitting Your Solution accepted (mingshun)
Setting up your environment for an SRM started by vijay03
Writing Template not started
Using and Understanding C++ Macros accepted (Eryx)
Using Prewritten Code accepted (it4.kp, Nickolas)
Understanding Your Rating and Why It Changes accepted (bmerry)

1.2. Approaching the Problem
Dissecting Problem Statement accepted (antimatter, Nickolas)
Planning an Approach to the Problem not started
Recognizing Problem Types started by StevieT
Solving Problems Using Alternative Bruteforce Solution accepted (Nickolas)
Practicing & Improving Your Style needs some thought (momtchil)
Choosing Best Programming Language not started

1.3. Finding and Avoiding Mistakes
Understanding the Importance of Testing accepted (Nickolas)
Avoiding Common Coding Mistakes started by maker2807
Testing for Correctness accepted (Nickolas)
Testing for Efficiency not started
Choosing Correct Data Types accepted (dttri, Nickolas)
Using Rational Arithmetic to Avoid Floating Point Imprecision accepted (Nemui, Nickolas)
Testing Using Alternative Brute-Force Solution accepted (it4.kp, Nickolas)
Finding Common Challenge Opportunities started by muxecoid


2. Common Algorithmic Problems

2.1. Main Data Types, Data Structures and Related Problems
Working with Numbers not started
Working with Strings started by dimkadimon
Working with Fixed-length Arrays started by caustique
Working with Variable-length Arrays (Vectors) not started
Working with Maps and Sets not started
Representing Sets with Bitfields accepted (bmerry)
Converting between Numbers and Strings accepted (Nickolas)
Parsing String Input accepted (Nickolas)
Iterating Over All Subsets of a Set accepted (dimkadimon)
Iterating Over All Permutations of an Array accepted (quimey, Ferlon)

2.2. Math and Geometry
Performing Calculations Modulo p started by Nemui
Handling Prime Numbers started by caustique
Using Euclid's Algorithm started by dimkadimon
Understanding Combinatorics accepted (Ferlon)
Using Inclusion-Exclusion Principle accepted (Ferlon)
Using Recurrent Relations for Calculations started by Ferlon
Defining Probabilities not started
Using Vector Operations accepted (bmerry, Nickolas)
Working with Lines and Segments started by Radheya
Working with Multiple Points not started

2.3. Graphs
Recognizing and Representing a Graph started by dragoon
Understanding Properties of Graphs not started
Handling Grid-Represented Graphs started by eraserhd
Searching a Graph Breadth-First started by pszemsza_
Searching a Graph Depth-First not started
Finding the Best Path Using Dijkstra's Algorithm started by Ferlon
Finding the Best Path Using Bellman-Ford Algorithm started by dragoon
Finding all Best Paths Using Floyd-Warshall Algorithm started by dragoon
Finding Maximum Flow Using Ford-Fulkerson Algorithm started by Ferlon
Solving Minimum Cost Flow Problem started by Ferlon
Solving Maximum Bipartite Matching Problem started by ibra
Recognizing the Algorithm to Use started by Nemui

2.4. Recursive Problems
Recognizing Recursive Problems accepted (Ferlon)
Solving Recursive Problems accepted (Ferlon)
Optimizing Recursive Solution started by jmzero
Solving Two-Person Games with Perfect Information started by rasto6sk
Introducing Dynamic Programming started by Dumitru
Optimizing DP Solution started by Nemui

2.5. Miscellaneous Problems
Using Greedy Algorithms TBD by supernova
Using Binary Search accepted - examples (Eryx)
Using Ternary Search accepted - examples (Eryx)
Using Backtracking started by martin-g
Using Linesweep Algorithm accepted (bmerry)
Constructing Combinatorial Objects started by ntmquan
Finding the lexicographically K-th combinatorial object accepted (rrpai, Ferlon)
Using Regular Expressions not started


3. Marathon Competition

3.1. Getting Started
Understanding Marathon Competition Format accepted (Nickolas)
Dissecting Problem Statement accepted (amiune)
Submitting Your Solution not started
Understanding Absolute and Relative Scoring Systems accepted (Nickolas)
Understanding Specific Marathon Matches started by kit1980

3.2. Working on the Problem
Measuring Time accepted (cant_dance, Nickolas)
Running Visualizer with Your Solution accepted (Nickolas)
Setting Up Your Environment/Keeping Track of Your Progress not started
Rewriting the Visualizer started by eraserhd
Implementing the Limitations Locally TBD by Nickolas
Comparing Solutions started by eraserhd
Deciding How to Improve Your Solution started by paranoia
Improving Your Solution in the Home Stretch started by eraserhd
Fine-tuning Your Solution not started
Choosing Best Programming Language not started

3.3. Methods of Solving the Problem
Identifying Principal Types of Problems accepted (nhzp339, Nickolas)
Generating Ideas for Your Solution accepted (Nickolas)
Approaching Single-Player Game-Based Problems accepted (Nickolas)
Using Hill Climbing Techniques accepted (Nickolas)
Using Simulated Annealing Techniques not started
Using Genetic Algorithms not started
Using SSE not started
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
I want to write about submitting the solution how can I do that ?
Re: Cookbook update (new prizes!) (response to post by TeCNoYoTTa) | Reply
Just write the recipe and post it as a separate thread to http://forums.topcoder.com/?module=ThreadList&forumID=534587 (assuming that you're going to write about Algo).

This recipe should describe the required structure of the solution, with limitations that apply to submitting it - memory and time limits, allowed languages and their compilers/versions, allowed libraries etc.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
i have a recipe but i think it's not so difficult !
given n which is an integer
and an array contains n-1 element "Random Arrangement" which is all numbers between 0 and n except one number how can i get this number using a program which its complexity is O(N).
example :
n = 7
Array[] = {0,3,5,2,7,4,6}
the output should be 1
Re: Cookbook update (new prizes!) (response to post by Seddik) | Reply
I think this task is too simple, too specific and not common enough to be included. Cookbook should contain generic things which are not evident, and this is a one-liner.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Hi Nickolas, I have post my ideas about solving maximum bipartite matching problem, but I wonder why the status is still Not started ..
Re: Cookbook update (new prizes!) (response to post by acerwei) | Reply
The status is updated not automatically but by hand. I'll be updating the statuses after I read the recipes thoughtfully and post comments to them.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Is there a way to put code snippets like these ones

http://forums.topcoder.com/?module=Thread&threadID=332780&start=0
http://forums.topcoder.com/wiki/display/tc/Algorithm+Overview?module=Thread&threadID=328725&start=0

in the book as an appendix or something or they don't fit into the book style?
Re: Cookbook update (new prizes!) (response to post by amiune) | Reply
If you need them in your recipe, you can put them there, no problem, we're going to have a lot of code in recipes. Not sure about appendix though.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Is it still possible to suggest recipes that are not yet in the structure?
If yes, I'd want to suggest and write "Choosing programming language" (for both Algo and Marathon): for example, if some problem uses long arithmetics, it's may be beneficial to use Java. Similarly for regular expressions, CSV parsing and for different time constraints.
Re: Cookbook update (new prizes!) (response to post by kit1980) | Reply
Sure, I'll be adding them to the list. Just make sure to cover a lot of detail in these recipes.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Huh, and now we see three different recipes about using Dijkstra's algorithm! That's no good. Maybe it would be better if coders must notify in advance in this thread that they start some recipe or ask one of copilots via e-mail about actually free ones?
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
I see more than 12 accepted on the list.
Does it mean that there are no TC t-shirts left?
Re: Cookbook update (new prizes!) (response to post by T.Issam) | Reply
If you check the actual recipes, you'll see that most of the accepted recipes are done by the same people, and t-shirts are awarded per person, not per recipe. I'll post the list of t-shirt winners soon and will be updating it as well as the list of recipes statuses.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
first off, thanks for your quick reply.

However, I think I missed something since on the list you posted names of authors are only shown for the "started" sections and not for the "accepted".

I thought I would find them here: http://forums.topcoder.com/?module=ThreadList&forumID=534587 but I found only the new posts.
Re: Cookbook update (new prizes!) (response to post by T.Issam) | Reply
I didn't show authors of "accepted" recipes, since 1) some of them are written by several people, so they don't affect t-shirts, and 2) they all can be found in Cookbook forums - Algo New Recipes, Algo Rewriting Phase and same pair for Marathon.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
.
Re: Cookbook update (new prizes!) (response to post by T.Issam) | Reply
Thanks Nickolas for the explanations and for adding the names to accepted sections.
Re: Cookbook update (new prizes!) (response to post by T.Issam) | Reply
Hello,

Even though maybe it is a dummy question. If a recipe has been already accepted can I submit my version of it?

Maybe there are another point of view or approach for the same issue.

Regards,

Devwebcl
Re: Cookbook update (new prizes!) (response to post by devwebcl) | Reply
You can try, but note that to be included in the final book, it will probably have to be mixed with another one. Which recipe is it?
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
It is : "Iterating Over All Permutations of an Array", I can see two names there already.
Re: Cookbook update (new prizes!) (response to post by devwebcl) | Reply
If you mean "Using next_permutation() (C++)" by quimey and "Iterating Over All Permutations of an Array" by Ferlon, the first one is Round 1 draft, and the second one is its rewrite. I wonder what can you add to it :-)
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Regarding the permutations Recipe, the issue is that I have a couple ideas (based on research) of the permutations because depending of the taxonomy of the problem, different algorithm to get all the permutation would be better or faster.

Even using the next_permutation may be not the first solution when using permutations in C++

I know if already there are two recipes, mine would be worthless for the editors.

Devwebcl
Re: Cookbook update (new prizes!) (response to post by devwebcl) | Reply
An algorithm for generating all permutations with time complexity better than O(n!*n) or at least with better constant than while using next_permutation function? Wikipedia doesn't know anything about this, so it's quite amazing. I suppose you could just leave a comment to my recipe with this algorithm's description, and if it is really correct, it will be counted as your nonzero contribution.
Re: Cookbook update (new prizes!) (response to post by Ferlon) | Reply
Using next_permutation to iterate through all permutations is O(n!).
Re: Cookbook update (new prizes!) (response to post by it4.kp) | Reply
Oh, numerical experiment says you are right, but I don't know how to prove this.
Re: Cookbook update (new prizes!) (response to post by Ferlon) | Reply
The next_permutation works like this:

it looks for a longest decreasing sequence in the end ant then does a swap and reverse.

For example, if the current permutation ends in 2,4,3,1 then the longest
decreasing sequence is 4,3,1. It swaps 2 and the smallest element that is bigger than it, in our case it's 3. So we have 3,4,2,1. And then reverse the last (still decreasing) sequence, so we have 3, 1, 2, 3. In other words for each decreasing sequence of length K it does O(K) operations.

How many permutations with the longest decreasing sequence in the end with length 1? It's n!/2. With length 2? It's n!/6 and so on...

So, we have a sum n! * ( 1/2! + 2/3! + ... + (n-1)/n! ) which is easily evaluated to n! * (1 - 1/n!), which is O(n!).
Re: Cookbook update (new prizes!) (response to post by Ferlon) | Reply
Hi,

I think there are better approach in special cases than using next_permutation, also that method is only for C++ and I work only with Java therefore could be a more generic writing for this permutation article ?

On the same track, I wonder if I try to write for algorithm how can I speak for implementations in different languages. Actually I'd like to try for Regular Expressions, but this is very tied to the libraries of each language, unless we were going to use tools as Lex, but I think that kind of tools i out of book's scope.

Regards,

Devwebcl
Re: Cookbook update (new prizes!) (response to post by devwebcl) | Reply
If a task allows several approaches - one using language libraries, and another language-independent - the recipe should cover both. Check Iterating Over All Permutations of an Array one - it shows both C++ next_permutation and generalized algorithm for other languages.

The recipes should use only libraries and tool available during SRMs.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Thanks for the clarification.

I wonder if still there is a chance to write a recipe for Regular Expression, I have a draft that I need to work to be a more cookbook type recipe. I read that the deadline is January 15th. Is this right ?

Do I have only to submit in the forum the recipe ?
then it can participate in the process to be chosen ?

Regards,

--Devwebcl
Re: Cookbook update (new prizes!) (response to post by devwebcl) | Reply
This recipe hasn't been attempted yet, so sure you can write it. Right, January 15th is the deadline. Yes, you just post the recipe to "Algorithm Competitions - New Recipes" forum.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
As soon as the deadline is January 15-th and today is 23-th January, I want to ask 2 questions:
1)Why my name isn't mentioned as a coauthor of article "Finding Maximum Flow Using Ford-Fulkerson Method"? Will it be?
2)Will my article "Solving Minimal Cut Problem" be placed to CookBook?

I appreciate your speedy answer :)
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Hi!
I have a question. How can I place images in my article?
What else can I do you to be able to add me to "started by"?
Thank you.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Hi!
I want to be a second author of article of Ferlon Finding Maximum Flow Using Ford-Fulkerson Method I can add some information and example. Can I do that? If yes, where should I post it? Maybe in Ferlon's Finding Maximum Flow Using Ford-Fulkerson Method post?
Re: Cookbook update (new prizes!) (response to post by ibra) | Reply
Hi,

I'm really sorry for the delay - I've forwarded your recipe and a few others (including the Ford-Fulkerson one) to reviewers, and will need their verdict to proceed.

As for the images, the only way to include them so far is to place them elsewhere and add a link to them to the recipe.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Thank you.

And what about being a second author of Ferlon's Finding Maximum Flow Using Ford-Fulkerson Method article? Should I speak to him about it? Should I post it in his post?

Thank you.
Re: Cookbook update (new prizes!) (response to post by ibra) | Reply
What's a matter? You are welcome to leave any comments to any recipe with additional relevant information.
Re: Cookbook update (new prizes!) (response to post by Ferlon) | Reply
ok
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
what is deadline for posting articles(I have one more)?
Re: Cookbook update (new prizes!) (response to post by ibra) | Reply
The deadline is when we have the book ready.

To everybody: I've been away for quite some time due to unexpected surgery, but now I'm recovering and will be able to devote more time to Cookbook project. Thanks everybody for your patience!
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
I am really sorry to hear that. I wish you a good and quick recovery.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
I am disappointed and surprised because of not being announced as author of the article I created with Ferlon:

"Finding Maximum Flow Using Ford-Fulkerson Algorithm started by Ferlon"
Re: Cookbook update (new prizes!) (response to post by ibra) | Reply
Once again, please be patient. I've already mentioned that graph recipes have to be processed and commented by reviewers before we can say something final about them, and that I have health problems which make me less efficient on this project than I'd like to be. This means that the comments on some recipes will probably be delayed till after TCO. I have every recipe we still have to comment noted down, so there's really no need to remind me about them separately.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Wait, so this Cookbook won't be free? :( I thought it was going to be more of a free/open source/member driven project with the goal of writing a giant guide full of general programming information/algorithms. Similar to the tutorial section but more organized. I guess I was mistaken...

*sigh* any idea how much it's going to cost?

Edit1: I guess I could try contributing to get a free copy, I gotta allocate some time for it first lol

Edit2: nevertheless, it feels weird having TopCoder milk our collective knowledge like that and sell it back to us for a profit...
Re: Cookbook update (new prizes!) (response to post by frank44) | Reply
Don't really know why you've had this idea - it was clearly stated from the start that we write the book, and O'Reilly sells it. You do buy algorithm books written by other people, don't you?

The draft version of the book is going to stay in the wiki, I think. As for the price of the book, I think we haven't set the price yet.

Well, people who are "milked" are paid for their milk, what's so weird about it? People who wrote educational content were paid as well. TopCoder isn't taking any of writer's payment, all profit from the book will be distributed between O'Reilly and book's authors.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
about the backtracking recipe , do you mean talking about the chronological backtracking and the dependency-directed backtracking ?
Re: Cookbook update (new prizes!) (response to post by melegy) | Reply
The one that is doing a brute-force depth-first search of every possibility, and when you hit the dead end, you backtrack to the last state whose children states you haven't exhausted.
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
Introducing prizes was a great idea - the interest and turnout has increased substantially!
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
What should the recipes be like?
Is it more like "Topcoder competitions for dummies" or more like "Best practices in topcoder competitions"? In other words, what is better: simple overview for beginners or detailed advice which can really help all the competitors? Or something in the middle?
Sorry if this question was already answered somewhere...

I'd like to write Marathon recipe for "Using SSE".
I think it'll be large.
Are there any requirements for recipe size?
I can cut some performance advice which I think is required.
Also I can add more code samples (but SSE samples are usually big!).
Re: Cookbook update (new prizes!) (response to post by syg96) | Reply
They should be both. Recipes closer to the start of the book should be "for dummies" kind - to help someone really unfamiliar with the topic start competing. The recipes on actual algorithms should be closer to "best practices" - at least that's what I'm trying to make them. I don't think we can really make the book thrilling for targets, but having recipes useful for yellows is definitely great. Actually, if you can think of some topic you'd like to cover that is not present in the structure so far, feel free to post it here, and I'll include it.

I'd be absolutely happy to have you write this recipe! Large is ok, since that's the specifics of the topic - don't cut anything! :-)
Re: Cookbook update (new prizes!) (response to post by Nickolas) | Reply
When the book will release ?
Re: Cookbook update (new prizes!) (response to post by Darkstalker_mdy) | Reply
July 2012
RSS