FitProgrammer@Work

Tuesday, May 12, 2015

List of Topics for programming Competitions

1. Basic Geometry/Euclidean Geometry/Coordinate Geometry/ [3-D variants of everything].

2. Computational Geometry.

a. Graham Scan algorithm for Convex Hull O(n * log(n)).

b. Online construction of 3-D convex hull in O(n^2).

c. Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn).

■ Suggested Reading -

1. http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm

d. Rotating Calipers Technique.

■ Suggested Reading - http://cgm.cs.mcgill.ca/~orm/rotcal.html

■ Problems - Refer the article for a list of problems which can be solved using Rotating Calipers technique.

e. Line Sweep/Plane Sweep algorithms -

■ Area/Perimeter of Union of Rectangles.

■ Closest pair of points.

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep

■ Problems - Follow the tutorial for list of problems.

f. Area of Union of Circles.

g. Delayunay Triangulation of n points in O(n * logn).

h. Voronoi Diagrams of n points in O(n * logn) using Fortunes algorithm.

i. Point in a polygon problem -

■ O(n) solution without preprocessing.

■ O(logn) algorithm with O(n * logn) preprocessing for convex polygons.

j. Problems on computational geometry -

■ BSHEEP, BULK, SEGVIS, CONDUIT, RUNAWAY, DIRVS, RAIN1, SHAMAN, TCUTTER, LITEPIPE, RHOMBS, FSHEEP, FLBRKLIN, CERC07P, BAC, ALTARS, CERC07C, NECKLACE, CH3D, RECTANGL, POLYSSQ, FOREST2, KPPOLY, RAIN2, SEGMENTS, ARCHPLG, BALLOON, CIRCLES, COMPASS, EOWAMRT, ICERINK on SPOJ.

■ CultureGrowth, PolygonCover on Topcoder.

k. Suggested Reading -

■ Computational Geometry: Algorithms and applications. Mark De Burg.

3. String Algorithm.

a. KnuthMorrisPratt algorithm.

■ Problems - NHAY, PERIOD on SPOJ.

■ Suggested Reading -

1. Cormen chapter on Strings.

2. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching

b. Aho Corasick algorithm.

■ Problems - WPUZZLES on SPOJ.

c. Suffix Arrays

■ O(n^2 * logn) Naive method of suffix array construction

■ O(n * logn^2) method of suffix array construction

■ O(n * logn) method of suffix array construction.

■ O(n) method of suffix array construction

■ O(n) LCA preprocess on Suffix Arrays to solve a variety of string problems.

d. Suffix Trees

■ O(n) construction of Suffix trees using Ukkenon’s algorithm.

■ O(n) construction of Suffix Trees if provided with Suffix Arrays using Farach’s algorithm.

e. Suffix Automata

■ O(n) Suffix Automaton construction.

f. Dictionary Of Basic Factors

■ O(n * logn) method of DBF construction using Radix Sort.

g. Manachar’s algorithm to find Lengh of palindromic substring of a string centered at a position for each position in the string. Runtime -> O(n).

h. Searching and preprocessing Regular Expressions consisting of ‘?’, ‘*’.

i. Multi-dimensional pattern matching.

j. Problems on Strings [can be solved with a variety of techniques] -

■ DISUBSTR, PLD, MSTRING, REPEATS, JEWELS, ARCHIVER, PROPKEY, LITELANG, EMOTICON, WORDS, AMCODES, UCODES, PT07H, MINSEQ, TOPALIN, BWHEELER, BEADS, SARRAY, LCS, LCS2, SUBST1, PHRASES, PRETILE on SPOJ

■ http://www.algorithmist.com/index.php/Category:String_algorithms

4. Basic Graphs [beginner].

a. Representation of graphs as adjacency list, adjacency matrix, incidence matrix and edge list and uses of different representations in different scenarios.

b. Breadth First Search.

■ problems -

1. PPATH, ONEZERO, WATER on SPOJ

c. Depth First Search.

d. Strongly Connected Components.

■ problems -

1. TOUR and BOTTOM on SPOJ.

e. Biconnected Components, Finding articulation points and bridges].

■ problems -

1. RELINETS, PT07A on SPOJ.

f. Dijkstra algorithm -

■ problems -

1. SHPATH on SPOJ.

g. Floyd Warshall algorithm -

■ problems -

1. COURIER on SPOJ.

h. Minimum Spanning Tree

■ problems -

1. BLINNET on SPOJ.

i. Flood-fill algorithm

j. Topological sort

k. Bellman-Ford algorithm.

l. Euler Tour/Path.

■ problems - WORDS1 on SPOJ.

m. Suggested reading for most of the topics in Graph algorithms -

■ http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs1.

■ Also refer to the tutorial for problems concerning these techniques.

■ Cormen chapter 22 to 24.

5. Flow networks/ matching etc etc. [Interdiate/Advanced].

a. Maximum flow using Ford Fulkerson Method.

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

■ problems - TAXI, POTHOLE, IM, QUEST4, MUDDY, EN, CABLETV, STEAD, NETADMIN, COCONUTS, OPTM on SPOJ.

b. Maximum flow using Dinics Algorithm.

■ Problems - PROFIT on spoj.

c. Minimum Cost Maximum Flow.

■ Successive Shortest path algorithm.

■ Cycle Cancelling algorithm.

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow1

d. Maximum weighted Bipartite Matching (Kuhn Munkras algorithm/Hungarian Method)

■ problems - GREED, SCITIES, TOURS on SPOJ | http://www.topcoder.com/stat?c=problem_statement&pm=8143

e. Stoer Wagner min-cut algorithm.

f. Hopcroft Karp bipartite matching algorithm.

■ problems - ANGELS on SPOJ.

g. Maximum matching in general graph (blossom shrinking)

h. Gomory-Hu Trees.

■ i) Problems - MCQUERY on Spoj.

i. Chinese Postman Problem.

■ problems - http://acm.uva.es/archive/nuevoportal/data/problem.php?p=4039

■ Suggested Reading - http://eie507.eie.polyu.edu.hk/ss-submission/B7a/

j. Suggested Reading for the full category ->

■ Network flow - Algorithms and Applications by Ahuja

■ Cormen book chapter 25.

6. Dynamic Programming.

a. Suggested Reading - Dynamic Programming(DP) as a tabulation method

■ Cormen chapter on DP

b. Standard problems (you should really feel comfortable with these types)

■ http://www.topcoder.com/stat?c=problem_statement&pm=8570&rd=12012&rm=269199&cr=7581406

■ http://www.topcoder.com/stat?c=problem_statement&pm=10765&rd=14183

c. State space reduction

■ http://www.topcoder.com/stat?c=problem_statement&pm=10902

■ http://www.topcoder.com/stat?c=problem_statement&pm=3001

■ http://www.topcoder.com/stat?c=problem_statement&pm=8605&rd=12012&rm=269199&cr=7581406

d. Solving in the reverse - easier characterizations looking from the end

■ http://www.spoj.pl/problems/MUSKET/

■ http://www.topcoder.com/stat?c=problem_statement&pm=5908

e. Counting/optimizing arrangements satisfying some specified properties

■ http://www.topcoder.com/stat?c=problem_statement&pm=8306

■ http://www.topcoder.com/stat?c=problem_statement&pm=7849

f. Strategies and expected values

■ http://www.topcoder.com/stat?c=problem_statement&pm=10765&rd=14183

■ http://www.topcoder.com/stat?c=problem_statement&pm=10806

■ http://www.topcoder.com/stat?c=problem_statement&pm=7828

■ http://www.topcoder.com/stat?c=problem_statement&pm=7316

g. DP on probability spaces

■ http://www.topcoder.com/stat?c=problem_statement&pm=7422

■ http://www.topcoder.com/stat?c=problem_statement&pm=2959

■ http://www.topcoder.com/stat?c=problem_statement&pm=10335

h. DP on trees

■ http://www.topcoder.com/stat?c=problem_statement&pm=10800

■ http://www.topcoder.com/stat?c=problem_statement&pm=10737

■ http://www.topcoder.com/stat?c=problem_solution&rm=266678&rd=10958&pm=8266&cr=7581406

i. DP with datastructures

■ http://www.spoj.pl/problems/INCSEQ/

■ http://www.spoj.pl/problems/INCDSEQ/

■ http://www.spoj.pl/problems/LIS2/

■ http://www.topcoder.com/stat?c=problem_statement&pm=1986

j. Symmetric characterization of DP state

■ http://www.topcoder.com/stat?c=problem_statement&pm=8610

k. A good collection of problems

■ http://codeforces.com/blog/entry/325

■ http://problemclassifier.appspot.com/index.jsp?search=dp&usr=

7. Greedy.

a. Suggested Reading -

■ Chapter on Greedy algorithms in Cormen.

■ http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg

b. problems - refer to the topcoder tutorial.

8. Number Theory.

a. Modulus arithmetic - basic postulates [Including modular linear equations , Continued fraction and Pell's equation]

■ Suggested Reading -

1. Chapter 1 from Number Theory for Computing by SY Yan [ Recommended ]

2. 31.1, 31.3 and 31.4 from Cormen

3. www.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers

■ Problems

1. http://projecteuler.net/index.php?section=problems&id=64

2. http://projecteuler.net/index.php?section=problems&id=65

3. http://projecteuler.net/index.php?section=problems&id=66

4. http://www.topcoder.com/stat?c=problem_statement&pm=6408&rd=9826

5. http://www.topcoder.com/stat?c=problem_statement&pm=2342

b. Fermat's theorem, Euler Totient theorem ( totient function, order , primitive roots )

■ Suggested Reading

1. 1.6, 2.2 from Number Theory by SY Yan

2. 31.6 , 31.7 from Cormen

■ Problems

1. http://projecteuler.net/index.php?section=problems&id=70

2. http://www.spoj.pl/problems/NDIVPHI/

c. Chinese remainder theorem

■ Suggested Reading

1. 31.5 from Cormen

2. 1.6 from Number Theory by SY Yan

■ Problems

1. Project Euler 271

2. http://www.topcoder.com/stat?c=problem_statement&pm=10551&rd=13903

d. Primality tests -

■ Deterministic O(sqrt(n) ) approach

■ Probabilistic primality tests - Fermat primality test, Miller-Rabin Primality test

1. Suggested Reading -

a. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting

b. Cormen 31.8

c. 2.2 from Number Theory by SY Yan

2. Problems -

a. PON, PRIC, SOLSTRAS on SPOJ

b. http://www.topcoder.com/stat?c=problem_statement&pm=4515

e. Prime generation techniques - Sieve of Erastothenes

■ Suggested Problems - PRIME1 on SPOJ

f. GCD using euclidean method

■ Suggested Reading

1. 31.2 Cormen

■ Problems -

1. GCD on SPOJ

2. http://uva.onlinejudge.org/external/114/11424.html

g. Logarithmic Exponentiation

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting

h. Integer Factorization

■ Naive O(sqrt(n)) method

■ Pollard Rho factorization

■ Suggested Reading

1. 2.3 from Number Theory SY Yan

2. 31.9 Cormen

■ Problems -

1. http://www.topcoder.com/stat?c=problem_statement&pm=2986&rd=5862

2. http://www.spoj.pl/problems/DIVSUM2/

3. http://www.topcoder.com/stat?c=problem_statement&pm=4481&rd=6538

i. Stirling numbers

j. Wilson theorem

■ nCr % p in O(p) preprocess and O(log n ) query

k. Lucas Theorem

l. Suggested Reading for Number Theory -

■ Number theory for computing by Song Y Yan [ Simple book describing concepts in details ]

■ Concepts are also superficially covered in Chapter 31 of Introduction to Algorithms by Cormen

■ http://www.codechef.com/wiki/tutorial-number-theory

■ http://www.algorithmist.com/index.php/Category:Number_Theory

m. Problems on Number Theory -

■ http://www.algorithmist.com/index.php/Category:Number_Theory

■ http://problemclassifier.appspot.com/index.jsp?search=number&usr=

9. Math (Probability, Counting, Game Theory, Group Theory, Generating functions, Permutation Cycles, Linear Algebra)

a. Probability.

Syllabus

■ Basic probability and Conditional probability

1. Suggested problems

a. http://www.spoj.pl/problems/CT16E/

b. http://www.spoj.pl/problems/CHICAGO/

■ Random variables, probability generating functions

■ Mathematical expectation + Linearity of expectation

1. Suggested problems

a. http://www.spoj.pl/problems/FAVDICE/

b. http://www.topcoder.com/stat?c=problem_statement&pm=10744

■ Special discrete and continuous probability distributions

1. Bernoulli, Binomial, Poisson, normal distribution

2. Suggested Problem

a. http://acm.sgu.ru/problem.php?contest=0&problem=498

■ Suggested Readings

1. Cormen appendix C (very basic)

2. Topcoder probabilty tutorial http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=probabilities

3. http://en.wikipedia.org/wiki/Random_variable

4. http://en.wikipedia.org/wiki/Expected_value

5. William Feller, An introduction to probability theory and its applications

b. Counting

Syllabus

■ Basic principles - Pigeon hole principle, addition, multiplication rules

1. Suggested problems

a. http://acm.timus.ru/problem.aspx?space=1&num=1690

b. http://www.topcoder.com/stat?c=problem_statement&pm=10805

3. Suggested readings

a. http://en.wikipedia.org/wiki/Combinatorial_principles

b. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=combinatorics

c. http://www.maa.org/editorial/knot/pigeonhole.html

■ Inclusion-exclusion

1. Suggested readings

a. http://en.wikipedia.org/wiki/Inclusion–exclusion_principle

2. Suggested problems

a. http://www.topcoder.com/stat?c=problem_statement&pm=4463&rd=6536

b. http://www.topcoder.com/stat?c=problem_statement&pm=10238

■ Special numbers

1. Suggested reading - Stirling, eurlerian, harmonic, bernoulli, fibonnacci numbers

a. http://en.wikipedia.org/wiki/Stirling_number

b. http://en.wikipedia.org/wiki/Eulerian_numbers

c. http://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

d. http://en.wikipedia.org/wiki/Bernoulli_number

e. http://en.wikipedia.org/wiki/Fibonnaci_numbers

f. Concrete mathematics by Knuth

2. Suggested problems

a. http://www.topcoder.com/stat?c=problem_statement&pm=1643

b. http://www.topcoder.com/stat?c=problem_statement&pm=8202&rd=11125

c. http://www.topcoder.com/stat?c=problem_statement&pm=8725

d. http://www.topcoder.com/stat?c=problem_statement&pm=2292&rd=10709

■ Advanced counting techniques - Polya counting, burnsides lemma

1. Suggested reading

a. http://en.wikipedia.org/wiki/Burnside's_lemma

b. http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html

2. Suggested Problems

a. http://www.topcoder.com/stat?c=problem_statement&pm=9975

b. http://www.spoj.pl/problems/TRANSP/

c. Game theory

Syllabus

■ Basic principles and Nim game

1. Sprague grundy theorem, grundy numbers

2. Suggested readings

a. http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem

b. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames

c. http://www.ams.org/samplings/feature-column/fcarc-games1

d. http://www.codechef.com/wiki/tutorial-game-theory

3. Suggested problems

a. http://www.topcoder.com/stat?c=problem_statement&pm=3491&rd=6517

b. http://www.topcoder.com/stat?c=problem_statement&pm=3491&rd=6517

■ Hackenbush

1. Suggested readings

a. http://en.wikipedia.org/wiki/Hackenbush

b. http://www.ams.org/samplings/feature-column/fcarc-partizan1

2. Suggested problems

a. http://www.cs.caltech.edu/ipsc/problems/g.html

b. http://www.spoj.pl/problems/PT07A/

d. Linear Algebra

Syllabus

■ Matrix Operations

1. Addition and subtraction of matrices

a. Suggested Reading

i. Cormen 28.1

2. Multiplication ( Strassen's algorithm ), logarithmic exponentiation

a. Suggested reading

i. Cormen 28.2

ii. Linear Algebra by Kenneth Hoffman Section 1.6

b. Problems

i. http://uva.onlinejudge.org/external/111/11149.html

3. Matrix transformations [ Transpose, Rotation of Matrix, Representing Linear transformations using matrix ]

a. Suggested Reading

i. Linear Algebra By Kenneth Hoffman Section 3.1,3.2,3.4,3.7

b. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=6877

ii. JPIX on Spoj

4. Determinant , Rank and Inverse of Matrix [ Gaussean Elimination , Gauss Jordan Elimination]

a. Suggested Reading

i. 28.4 Cormen

ii. Linear Algebra by Kenneth Chapter 1

b. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=8174

ii. http://www.topcoder.com/stat?c=problem_statement&pm=6407&rd=9986

iii. http://www.topcoder.com/stat?c=problem_statement&pm=8587

iv. HIGH on Spoj

5. Solving system of linear equations

a. Suggested Reading

i. 28.3 Cormen

ii. Linear Algebra by Kenneth Chapter 1

b. Problems -

i. http://www.topcoder.com/stat?c=problem_statement&pm=3942&rd=6520

6. Using matrix exponentiation to solve recurrences

a. Suggested Reading

i. http://www.topcoder.com/tc?module=Static&d1=features&d2=010408

b. Problems

i. REC, RABBIT1 , PLHOP on spoj

ii. http://www.topcoder.com/stat?c=problem_statement&pm=6386 , http://www.topcoder.com/stat?c=problem_statement&pm=7262, http://www.topcoder.com/stat?c=problem_statement&pm=6877

7. Eigen values and Eigen vectors

a. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=2423&rd=4780

■ Polynomials

1. Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial, All real roots of a polynomial ]

a. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=8273&rd=10798

ii. POLYEQ , ROOTCIPH on Spoj

2. Lagrange Interpolation

a. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=10239

ii. http://www.topcoder.com/stat?c=problem_statement&pm=8725

e. Permutation cycles

■ Suggested Reading

1. Art of Computer Programming by Knuth Vol. 3

■ Problems

1. ShuffleMethod, Permutation and WordGame on topcoder.

f. Group Theory

■ Bernside Lemma, Polias theorem

1. Suggested Reading

a. Hernstein's topics in algebra

b. http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html

2. Problems

a. TRANSP on spoj

b. http://www.topcoder.com/stat?c=problem_statement&pm=9975

b. Generating functions

■ Suggested Reading

1. Herbert Wilf's generating functionology

2. Robert Sedgewick and Flajoulet's Combinatorial analysis

10. Data Structures.

i. Basic

a. Arrays/Stacks/Queues :

■ Problems

1. https://www.spoj.pl/problems/STPAR/

2. https://www.spoj.pl/problems/SHOP/

3. https://www.spoj.pl/problems/WATER/

■ Reading:

1. CLRS: section 10.1

2. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dataStructures

b. Singly/Doubly Linked List :

■ Problems

1. https://www.spoj.pl/problems/POSTERS/

■ Reading: CLRS: section 10.2, Mark Allen Weies Chapter 3

c. Hash Tables :

■ Problems

1. https://www.spoj.pl/problems/HASHIT/

2. https://www.spoj.pl/problems/CUCKOO/

■ Reading: CLRS: Chapter 11, Mark Allen Weies Chapter 5

d. Circular linked list / queue

■ Problems

1. https://www.spoj.pl/problems/CTRICK/

e. Binary/nary Trees

■ Reading

1. CLRS: section 10.4

2. CLRS: Chapter 12

3. Mark Allen Weies Chapter 4

4. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearchRedBlack

f. Heaps

■ Problems

1. https://www.spoj.pl/problems/PRO/

2. https://www.spoj.pl/problems/EXPEDI/

■ Reading : Mark Allen Weies Chapter 6

ii. Advanced

a. Trie (Keyword tree)

■ Problems

1. https://www.spoj.pl/problems/MORSE/

2. https://www.spoj.pl/problems/EMOTICON/

■ Reading

b. Interval trees / Segment Trees

■ Problems

1. https://www.spoj.pl/problems/ORDERS/

2. https://www.spoj.pl/problems/FREQUENT/

■ Reading

c. Fenwick(Binary Indexed) trees

■ Problems

1. https://www.spoj.pl/problems/MATSUM/

■ Reading: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

d. Disjoint data structures

■ Problems

1. https://www.spoj.pl/problems/BLINNET/

2. https://www.spoj.pl/problems/CHAIN/

■ Reading:

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure

2. Mark Allen Weies Chapter 8

e. Range minimum Query(RMQ)

■ Problems

1. https://www.spoj.pl/problems/GSS1/

■ Reading http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

f. Customized interval/segment trees (Augmented DS)

■ Problems

1. https://www.spoj.pl/problems/GSS3/

2. https://www.spoj.pl/problems/RRSCHED/

■ Reading: CLRS: Chapter 14 (augmented DS)

g. AVL Trees

■ Problems

1. https://www.spoj.pl/problems/ORDERS/

■ Reading

iii. Miscellaneous (Not to be covered)

a. Splay Trees

b. B/B+ Trees

c. k-d Trees

d. Red-black Trees

e. Skip List

f. Binomial/ Fibonacci heaps

iv. Exercices

1. https://www.spoj.pl/problems/LAZYPROG/ (Hint: Heaps)t

2. https://www.spoj.pl/problems/HELPR2D2/ (Hint: Interval Trees)

3. https://www.spoj.pl/problems/SAM/ (Hint: Heaps)

4. https://www.spoj.pl/problems/PRHYME/ (Hint: Trie)

5. https://www.spoj.pl/problems/HEAPULM/ (Hint: Interval Trees)

6. https://www.spoj.pl/problems/CORNET/ (Hint: Disjoint )

7. https://www.spoj.pl/problems/EXPAND/

8. https://www.spoj.pl/problems/WPUZZLES/

9. https://www.spoj.pl/problems/LIS2/

11. Search Techniques/Bruteforce writing techniques/Randomized algorithms.

a. Backtracking - [Beginner].

■ problems ->

1. N queens problems

2. Knights Tour

3. Sudoku Problem

4. Tiling Problem.

5. 15 puzzle.

b. Dancing Links and Algorithm X given by Knuth - [Advanced]

■ problems - PRLGAME, SUDOKU, NQUEEN on SPOJ

■ Suggested reading -

1. http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz

c. Binary Search - [Beginner].

■ poblems - AGGRCOW on SPOJ. Refer the tutorial for more problems.

■ finding all real roots of a polynomial using binary search. [intermediate].

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

d. Ternary Search - [Intermediate].

■ problems -

1. http://www.spoj.pl/problems/KPPOLY/

2. http://www.codechef.com/DEC09/problems/K1/

3. http://www.topcoder.com/stat?c=problem_statement&pm=4705&rd=7993

4. http://www.topcoder.com/stat?c=problem_statement&pm=7741&rd=10671

5. http://www.topcoder.com/stat?c=problem_statement&pm=6464&rd=9994

6. http://www.topcoder.com/stat?c=problem_statement&pm=3501&rd=6529

7. http://www.topcoder.com/stat?c=problem_statement&pm=4567&rd=6539

e. Meet in the middle [Intermediate].

■ problems -

1. http://www.spoj.pl/problems/MAXISET/

2. http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2868

f. Hill Climbing [Advanced].

g. Regular Iteration to reach a fixed point [Advanced].

■ Newton-Raphson method to find root of a mathematical function.

■ Iterations to solve linear non-homogeneous system of equations.

h. Randomized Algorithms [Intermediate]-

■ Quick-Sort.

12. General programming issues in contests ->

a. Arithmetic Precision - [Beginner].

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=integersReals

b. Representing sets with bitmasks and manipulating bitmasks - [Beginner].

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation

■ problems - refer to the tutorial link in Suggested reading section.

Monday, May 11, 2015

Programming contest related sites

This is a compilation of resources for my son who has just started learning programming at the age of 7.

Timus Online Judge
Topcoder algorithms tutorials
Data structures and algorithms links
Sphere Online Judge
USA Computing Olympiad and Training
International Olympiad in Informatics
UVA Online Judge
Sites with programming problems to practice with:

Bios of programmers who have won in programming contests:

Video:

Blogs and Articles:

Advice:
If I am to start programming now, I would do it this way

Solve 200 most solved problems on SPOJ or UVA, Problem by problem. In 2 months.
(This will teach all standard problems, algorithms and implementation skills)
Solve problems from CodeChef and CodeForces for 2 months.
(This will teach variations, we can read others solutions and learn better ways. Skip easy problems)
Solve problems from TopCoder for 2 months.
(This will teach Dynamic Programming. Div 1 500p)
Check past ACM ICPC Regional's Problems
(Great quality problems)

Tuesday, April 21, 2015

Book Review: Spring Chicken: Stay Young Forever (or Die Trying) (Gifford, Bill)

Following are my notes/highlights from the book:

Two of the major diseases of aging—cardiovascular disease and diabetes—are largely avoidable,
Major longevity-promoting mechanisms, hardwired into our biology, can be triggered right now, by simply going out for a short jog, or even just by skipping a meal or two.
One good way to shorten your life, statistically, is by becoming obese.
Nothing makes you look older than attempting to look young. —Karl Lagerfeld
Lifting weights (and taking testosterone) do improve strength; also, weight training and vigorous exercise like sprinting have been shown to increase growth-hormone levels naturally. So does deep sleep.
Thanks to Blast data, researchers now know that natural walking speed is one of the most accurate predictors of mortality that we have. The slower you walk, statistically speaking, the sooner you are likely to check out.
Aging is hiding in our bodies.
Mobility is key to survival
Young-middle-aged people (in their forties and fifties) with positive feelings about growing older—gaining wisdom, freedom from working, opportunities to travel and learn more—tended to enjoy better health, and better cognitive health later in life.
“If you want to become a healthy eighty-year-old, you need to live a healthy lifestyle, but if you want to become a healthy hundred-year-old, you need to inherit the right genes.”
many of them had a specific gene variant that inhibits something called CETP, a molecule involved in cholesterol processing (it stands for “cholesterol ester transfer protein,” - in general, the less CETP you have, the better; high levels of the protein are thought to lead to premature atherosclerosis. Centenarians with the CETP-inhibiting mutation not only had better heart health, and very high “good” cholesterol, but they also had a lower incidence of memory loss and dementia,
He pays special attention to his LDL cholesterol—the “bad” kind—which tends to be extremely low in centenarians. If he keeps his LDL low, he reasons, then he might stand a chance of living to be a hundred, too. The machine lets him monitor it closely: If it gets too high, he’ll cut back on the carbohydrates and perhaps up his dose of red yeast rice, a natural statin that lowers LDL.
And finally, there is one bellwether of heart trouble that on reflection should be obvious: erectile dysfunction
“Remember, our genes still think it’s three thousand years ago and we’re starving, so these mechanisms for preserving cholesterol are still going strong,” Lebowitz said.
(Oat bran fiber does much the same thing, absorbing cholesterol in the gut and escorting it out of the body.)
Red meat has long been known to be a risk factor for heart disease, originally because of its fat content.
According to this study, it is apparently only safe to eat meat if you’re a vegetarian.
A moist eye, a dry hand, a yellow cheek, a white beard, a decreasing leg, an increasing belly… your voice broken, your wind short, your chin double, your wit single, and every part about you blasted with antiquity. —Shakespeare
“three phases of a new idea”: “First you’re an idiot; second, it’s meaningless; third, it was obvious all along—and nobody gives you credit for it.”
A cell’s biological age, therefore, had almost nothing to do with its chronological age.
The only thing that seemed to matter was how many times it (the cell) had divided.
Activating telomerase might cause cancer. One thing that cancer cells all have in common is amped-up telomerase.
According to the twenty-five-year-long Rancho Bernardo study of older Californians, the higher your levels of IL-6, the earlier your checkout time from Hotel Earth.
Hayflick recognized two possible fates for our cells when they stop dividing: Either they become cancer, that is to say immortal; or they enter a state he termed replicative senescence.
“The big aha came when we realized that when a cell becomes senescent, it starts to secrete molecules that cause chronic inflammation,”
As we grow older, and growth hormone and testosterone decline (along with other chemical changes), the calories we consume are far more likely to end up as fat.
Beginning around age thirty-five, our total body fat percentage increases by as much as 1 point per year, even if our overall weight stays the same.
Diabetes itself is now thought to speed up the aging process enormously. The body becomes unable to process the sugar that we eat, which ends up rollicking around in our bloodstream, inflicting massive amounts of cellular damage in every tissue that it touches. Excess blood sugar even makes you look older: One study showed that people with higher blood sugar actually did appear older than they were, perhaps because this damage is visible in their very skin.
Men do not quit playing because they grow old; they grow old because they quit playing. —Oliver Wendell Holmes
Ron stays young, he said, by avoiding the “inflammables,” by which he seemed to mean foods containing dairy, wheat, and sugar.
Education, money, and access to medical care all correlate strongly with longevity, Jay Olshansky and other scholars have found.
“And the idea that well, it’s natural and you’re just an old man now—that isn’t natural! That is the default. That’s where we get to by not challenging ourselves. Exercise is a continuum: The more you do, the less you’re going to lose.”
the “secret” seems to be: Use It or Lose It.
We begin to lose muscle mass gradually at around age forty, and as time goes on we lose it more rapidly: Between fifty and seventy, we say good-bye to about 15 percent of our lean muscle per decade. After that, it jumps to 30 percent per decade. “You could make the case that aging starts in muscle,”
But even as we’re losing muscle in middle age, we don’t lose weight overall (duh). That means our muscle is gradually, insidiously being replaced by fat. More fat and less muscle means your metabolic “engine” runs at a much slower rate; you have less muscle, which means you have fewer mitochondria, which means your body is less efficient at burning the sugar out of your bloodstream. Not coincidentally, most new cases of diabetes appear in people in their mid-forties and older.
Recent studies have pinpointed the mere act of sitting, itself, as a potent risk factor for death. Sitting is the new smoking, some scientists believe: a bad habit that leads inevitably to disease.
caloric restriction might actually be slowing the aging process itself, on a more fundamental level.
He cut down to a protein shake for breakfast, a salad for lunch, and a baked sweet potato and perhaps a bit of fish for dinner.
The hungry monkeys were far healthier, in terms of basic measures like blood pressure, and had far less incidence of age-related disease, such as diabetes and cancer. As a result they seemed to be living as much as 30 percent longer than their overfed friends.
A wealth of good epidemiological data points to the fact that it’s better to be a little bit overweight (i.e., BMI of 25) than to be seriously underweight (BMI below 21), very skinny people may not have the fat reserves they need to survive an infection, particularly as they get older.
What to eat - not too much, and nothing processed, only good, real food. He looks forward to his salad lunches and his salmon dinners, as much as any gourmand.
“hormetic” lifestyle, in which he actively seeks out stressful experiences (like diving into bone-freezing water).
The work stresses and even damages our muscle fibers, but thanks to the miracle of hormesis, we repair and rebuild them with new, stronger fibers. Most vaccinations work by the same principle: A small dose of a pathogen stimulates a response that renders us immune to the disease.
“Stress is strengthening, even essential to life,”
Each morning he wakes up to an ice-cold shower, the cold tap cranked all the way up. He stays in for five minutes, minimum, and claims that this bracing ritual not only jolts him awake (thus reducing his coffee budget) but also burns fat, improves pain tolerance, and boosts immunity.
gettingstronger.org. (Motto: “Train yourself to thrive on stress.”)
short-term fasting—skipping one, and sometimes even two meals—and tough, intense workouts, either running barefoot on trails or climbing in a nearby rock gym, often on an empty stomach. As a matter of fact, he hadn’t eaten for twenty-two hours, or since lunch the previous day, despite going for a tough postwork run with work colleagues in the Palo Alto hills, training for an upcoming 125-mile relay race. “One thing I really love,” he confessed to me, “is fasted workouts.”
working out while you’re hungry might actually be a good thing.
“I learned to embrace a little bit of hunger.”
rapamycin could be the magic bullet that aging researchers had been looking for
continuation of cell growth leads to cellular senescence, the toxification of our aged cells.
he eats a far healthier diet, consisting of mostly green vegetables, some pasta, and a little bit of wine. Meat is an occasional luxury.
The key to Caruso’s diet, according to Longo, is its low carbohydrate content and its low protein content—intentionally or not, he thinks, it keeps his growth factors and TOR in check, which effectively slows the rate of aging.
He and his cohort were trained to eat less, in effect, by history—war, poverty, and periodic famine.
Most days he skips lunch completely, and at dinner he eats a low-protein, plant-based, vegan-ish diet designed to push down his IGF-1 levels (not just to keep himself rock-star thin at age forty-six). Once or twice a year, he’ll put himself through a bare-bones fast for up to four days, taking in a bare minimum of nutrition, in order to “reset” his system. He believes this is the best option, based on mouse and human studies, and also because it happens to work for him.
Use It or Lose It applies to our brains,
Health Extension Salon - Bay area.
A major 2011 study from UCSF found that if seven basic risk factors were addressed, including diabetes, midlife obesity (defined as waist size of thirty-nine inches or more for men, thirty-six for women), midlife hypertension, smoking, depression, low educational level, and physical inactivity, half of all Alzheimer’s cases could actually be prevented.
another recent long-term study found that people who had been fitter at age twenty-five had stayed more cognitively “intact” at age fifty.

Friday, April 17, 2015

Oracle Java Cloud Service: #1 Java App Server, in the Cloud

Wednesday, April 15, 2015

World of Baby Aarini: Book 1–"Baby Aarini and the Lawn Bunny” Published

This is the first book in the series of picture story books of Baby Aarini. In this story, baby Aarini interacts with the lawn Bunny.

Thursday, March 05, 2015

Preserving History When Renaming Files in git by Scott Nelson of This by Them

REMEMBER, GIT TRACKS CONTENT, NOT FILES

Git doesn’t really care that we renamed the file, but it knows that we moved the contents of the file to another file. When we tell git to show us the history for a particular file name, it will only show us the history for that file, not the entire history for the content within the file.

In order to see the entire history for that content, we need to tell git that’s specifically what we want. There’s a --follow option we can pass to git logfor this.

So, to see our commits before the rename, we can do git log --follow just-an-everage-blog-post.md and voila, there’s our entire history for the content of that file.

Monday, March 02, 2015

Autocrlf setting in Git

Excerpted from: http://stackoverflow.com/questions/1967370/git-replacing-lf-with-crlf/20653073#20653073

How autocrlf works:

core.autocrlf=true:    core.autocrlf=input:      core.autocrlf=false:

       repo                     repo                    repo
    /        \               /        \              /        \
crlf->lf    lf->crlf     crlf->lf       \          /            \      
 /              \        /                \      /                \

Reminder: crlf = win-style end-of-line marker, lf = unix-style.

Note that cr (mac-style) in not affected for any of three options above.

When does this warning show up (under Windows)

    - autocrlf = true if you have unix-style lf in one of your files (= RARELY),
    - autocrlf = input if you have win-style crlf in one of your files (= almost ALWAYS),
    - autocrlf = false - NEVER!

What does this warning mean

The warning "LF will be replaced by CRLF" says that you (having autocrlf=true) will lose your unix-style LF after commit-checkout cycle (it will be replaced by windows-style CRLF). Git doesn't expect you to use unix-style LF under windows.

The warning "CRLF will be replaced by LF" says that you (having autocrlf=input) will lose your windows-style CRLF after a commit-checkout cycle (it will be replaced by unix-style LF). Don't use input under windows.

Yet another way to show how autocrlf works

1) true:             x -> LF -> CRLF
2) input:            x -> LF -> LF
3) false:            x -> x -> x

where x is either CRLF (windows-style) or LF (unix-style) and arrows stand for

file to commit -> repository -> checked out file

How to fix

Default value for core.autocrlf is selected during git installation and stored in system-wide gitconfig (%ProgramFiles(x86)%\git\etc\gitconfig). Also there're (cascading in the following order):

   - "global" (per-user) gitconfig located at ~/.gitconfig, yet another
   - "global" (per-user) gitconfig at $XDG_CONFIG_HOME/git/config or $HOME/.config/git/config and
   - "local" (per-repo) gitconfig at .git/config in the working dir.

So, write git config core.autocrlf in the working dir to check the currently used value and

   - add autocrlf=false to system-wide gitconfig # per-system solution
   - git config --global core.autocrlf false        # per-user solution
   - git config --local core.autocrlf false          # per-project solution

Moral (for Windows):
    - use core.autocrlf = true if you plan to use this project under Unix as well (and unwilling to configure your editor/IDE to use unix line endings),
    - use core.autocrlf = false if you plan to use this project under Windows only,
    - never use core.autocrlf = input unless you have a good reason to (eg if you're using unix utilities under windows or if you run into makefiles issues),

P.S. What to choose when installing git for Windows?
If you're not going to use any of your projects under Unix, don't agree with the default first option. Choose the third one (Checkout as-is, commit as-is). You won't see this message. Ever.

P.P.S. My personal preference is configuring the editor/IDE to use Unix-style endings, and setting core.autocrlf to false.