gcj 2018 and my progress

First of all congratulations to those who have made through gcj (Google Code Jam) 2017 qualification, 1a & 1c. All the best for the remaining rounds.

I have been active in the competitive programming from last 3 months, though i came across Code Chef many years back. After the recent GCJ qualification round where i have made only 5 points (could have made more but i don’t want to make some excuses here). I know that i am not well prepared and ready for such big events but made a decision that I have to clear more rounds in GCJ 2018.

I had confidence building up here at Code Chef until the recent events, the progress I made so far

Long Challenges

  • FEB17 - Solved 1 problem
  • MAR17 - Solved 2 problems
  • APR17 - Solved 3 Problems

Short Contests

  • IOPC17 - Solved 0 problems with 1 wrong submission
  • April Cookoff - Solved 1 problem

With the Short Contest my ratings have dropped like anything, I believe that rankings/rantings are just like a byproduct as long as you keep solving more and more problems, they just go up. But they also give some confidence, comparatively where you are.

I am not asking here for some Algorithms to start with, as we have good links in this forum.
But I see that I am lacking some Math skills that are required for competitive programming, please suggest what concepts should I know here that helps & what else I need to improve to reach my next year goal of GCJ 2018 to clear more rounds.

PS: Please advice if posting this question here is valid.

1 Like

If you want to be a very serious competitive programmer, I will go a bit deeper into the details of what all math you might ever need for competitive programming.

Arithmetic and Geometry:-

Integers, operations(including exponentiation), comparison
Basic property of integers(sign, parity, divisibility)
Basic modular arithmetic(addition, subtraction, multiplication, division)
Prime numbers(Its a vast topic)
Fractions and percentages
Line, line segment, angle, triangle, rectangle, square, circle(and specially way to represent them in your code)
Point, vector, coordinates in a plane
Polygon(vertex, side/edge, simple, convex, inside, area)
Euclidean distances
Pythogorean theorem(There are pretty diverse use of this theorem)
In some questions you might need Fermat’s Little Theorem, Chinese remainder theorem, or may need to use the Euler function etc. You need to get better in number theory. I have encountered some problems on codechef which need these myself.
Knowing some techniques like Euclidean Algorithm and fast exponentiation are considered to be a prerequisite in some contests.
Some computational geometry techniques like Graham Scan and convex hull.

Discrete Structures:-

Functions, Relations and Sets
Functions(surjections, injections, inverses, composition)
Relations(reflexivity, symmetry, transitivity, equivalence relations, total/linear order relations, lexicographic order)
Sets(cardinality, inclusion/exclusion, complements, Cartesian products, power sets)
Basic Logic
First-order logic
Logical connectives(including their basic properties)
Truth Tables
Universal and Existential quantification
Modus ponens and Modus tollens(Not to get intimidated by the names :P)
Proof techniques(You don’t need them too rigorously)
Basics of Counting
Counting arguments (sum and product rule, arithmetic and geometric progressions, Fibonacci numbers)
Permutations and combinations (basic definitions)
Factorial function, binomial coefficients
Inclusion-exclusion principle
Pigeonhole principle
Pascal’s identity, Binomial theorem
Solving recurrence relations
Burnside Lemma
Graphs and trees
Trees and their basic properties, rooted trees
Undirected graphs (degree, path, cycle, connectedness, Euler/Hamilton path/cycle, handshaking lemma)
Directed graphs (in-degree, out-degree, directed path/cycle, Euler/Hamilton path/cycle)
Spanning trees
Traversal strategies
‘Decorated’ graphs with edge/node labels, weights, colors
Multigraphs, graphs with self-loops
Bipartite graphs
Planar graphs
Probability theory

Linear Algebra(including but not limited to)
Matrix multiplication, exponentiation, inversion, and Gaussian elimination
Fast Fourier transform

Even though, many of these topics are not to be mastered rigorously, some are prerequisites and competitive programmers should have the basic knowledge of at least most of them to be among the top tier of programmers.

I hope this helped :smiley:

Happy Coding!

More at: https://www.quora.com/What-are-the-skills-required-to-crack-Google-Code-Jam-or-Google-APAC

3 Likes

Solving first 2 or 3 problems of long challenge is aptitude and some tricks of maths…then comes data structures for remaining problems.

It will be better if you start solving large number of problem from EASY on codechef . They are just simple maths . They should really help .

Then , you may proceed to solving topic-intensive questions at Hackerearth , eg. -graphs , dp , trees , number theory , maths etc . It will surely do some good to you . Cheers …

3 Likes

For the number theory part of Mathematics , I suggest you to explore Project Euler of HackerRank. It has good and interesting problems on Number Theory : https://www.hackerrank.com/contests/projecteuler/challenges

Happy Coding!

I agree with you, because i didn’t felt so far in any long challenge that i have applied some algorithm and got the solution AC.

thanks for the suggestions @marshal_roxx , I will start implementing that.