



We keep writing recipes for Algorithm and Marathon chapters, and to provide a bit of extra motivation for you, we're adding shortterm rewards.
The first 12 contributors to deliver an approved recipe for one of these chapters, will win a TopCoder tshirt. The tshirt 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 tshirt 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). 

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 BruteForce 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 Fixedlength Arrays started by caustique Working with Variablelength 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 InclusionExclusion 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 GridRepresented Graphs started by eraserhd Searching a Graph BreadthFirst started by pszemsza_ Searching a Graph DepthFirst not started Finding the Best Path Using Dijkstra's Algorithm started by Ferlon Finding the Best Path Using BellmanFord Algorithm started by dragoon Finding all Best Paths Using FloydWarshall Algorithm started by dragoon Finding Maximum Flow Using FordFulkerson 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 TwoPerson 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 marting Using Linesweep Algorithm accepted (bmerry) Constructing Combinatorial Objects started by ntmquan Finding the lexicographically Kth 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 Finetuning 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 SinglePlayer GameBased Problems accepted (Nickolas) Using Hill Climbing Techniques accepted (Nickolas) Using Simulated Annealing Techniques not started Using Genetic Algorithms not started Using SSE not started 

I want to write about submitting the solution how can I do that ? 

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. 

i have a recipe but i think it's not so difficult ! given n which is an integer and an array contains n1 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 

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 oneliner. 

Hi Nickolas, I have post my ideas about solving maximum bipartite matching problem, but I wonder why the status is still Not started .. 

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. 

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. 

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. 

Sure, I'll be adding them to the list. Just make sure to cover a lot of detail in these recipes. 

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 email about actually free ones? 

I see more than 12 accepted on the list. Does it mean that there are no TC tshirts left? 

If you check the actual recipes, you'll see that most of the accepted recipes are done by the same people, and tshirts are awarded per person, not per recipe. I'll post the list of tshirt winners soon and will be updating it as well as the list of recipes statuses. 

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. 

I didn't show authors of "accepted" recipes, since 1) some of them are written by several people, so they don't affect tshirts, and 2) they all can be found in Cookbook forums  Algo New Recipes, Algo Rewriting Phase and same pair for Marathon. 

Thanks Nickolas for the explanations and for adding the names to accepted sections. 

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 

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? 

It is : "Iterating Over All Permutations of an Array", I can see two names there already. 

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 :) 

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 

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. 

Using next_permutation to iterate through all permutations is O(n!). 

Oh, numerical experiment says you are right, but I don't know how to prove this. 

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! + ... + (n1)/n! ) which is easily evaluated to n! * (1  1/n!), which is O(n!). 

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 

If a task allows several approaches  one using language libraries, and another languageindependent  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. 

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 

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. 

As soon as the deadline is January 15th and today is 23th January, I want to ask 2 questions: 1)Why my name isn't mentioned as a coauthor of article "Finding Maximum Flow Using FordFulkerson Method"? Will it be? 2)Will my article "Solving Minimal Cut Problem" be placed to CookBook?
I appreciate your speedy answer :) 

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. 

Hi! I want to be a second author of article of Ferlon Finding Maximum Flow Using FordFulkerson 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 FordFulkerson Method post? 

Hi,
I'm really sorry for the delay  I've forwarded your recipe and a few others (including the FordFulkerson 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. 

Thank you.
And what about being a second author of Ferlon's Finding Maximum Flow Using FordFulkerson Method article? Should I speak to him about it? Should I post it in his post?
Thank you. 

What's a matter? You are welcome to leave any comments to any recipe with additional relevant information. 

what is deadline for posting articles(I have one more)? 

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! 

I am really sorry to hear that. I wish you a good and quick recovery. 

I am disappointed and surprised because of not being announced as author of the article I created with Ferlon:
"Finding Maximum Flow Using FordFulkerson Algorithm started by Ferlon" 

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. 

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... 

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. 

about the backtracking recipe , do you mean talking about the chronological backtracking and the dependencydirected backtracking ? 

The one that is doing a bruteforce depthfirst search of every possibility, and when you hit the dead end, you backtrack to the last state whose children states you haven't exhausted. 

Introducing prizes was a great idea  the interest and turnout has increased substantially! 

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!). 

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! :) 

When the book will release ? 
