Thinking Techniques

These notes is based on my Arabic Thinking Series.

Thinking: On papers Not on PC

• This is kind of note..rather than a technique
• Remember the comfortable zone? When you move from Easy to medium to hard problem => you suffer more.
  • The more complexity of problem, the MORE thinking you nee about it.
• One of main problems is that coders loves the PCs and loves solving over the machine.
  • In many cases, this push them to write the solution, without doing all necessary steps first (e.g. verifying idea/order)
  • The mind will be bounded on PC and will keep doing "work around" to fix idea/code.
• It is much better to think on papers away of the PC. Sketch FULL idea and verify it.
• Same for implementation of a hard problem, you need to think more about code before writing it.
• Yourself will tell you coding on PC is faster, tell her NO, this is not easy idea/code for me.
• If you sketched a code/idea and later discovered a mistake in it! LEFT the machine.
  • Back to paper, repeat your life cycle. NEVER to think on PC.
• Finally, In Real ICPC contest, Teams are of 3, with 1 pc. When you think on paper, you save team time.
  • You have 15 hours available PC if works well on papers

Thinking: Brainstorm - Rank - Approach

• In many times, contestant starts to think in a problem, find an idea (e.g. let's make it by DP) and start to do "DIVING"
  • By Diving I mean, keep trying to solve the problem based on an idea, but time passes with no real progress! ... In other words, you are "STUCK in thinking"
• Sometimes, Idea is correct, but you don't study enough algorithms to know how to continue
• Sometimes, Idea is correct, but you don't do enough observations
• Sometimes, approach is correct (e.g. it is DP), but the idea itself is wrong (you need to think in other recurrence)
• Sometimes, approach is incorrect, and you need to think differently
• How to avoid being stuck?
• It is very important to BRAINSTORM storm on different solutions that may work, before focusing on one way.
  • E.g. Given ... Find the minimum X? Think that DP, greedy, Min Cut, B & B or some ad-hock idea MAY do it.
  • 1- Try to RANK your guesses based on your analysis
  • 2- APPROACH the problem using most probable idea to do it (which may be wrong)
  • 3- Keep your eyes on TIME. When you start to tackle it this way?
  • 4- After little analysis, rethink about your ideas RANK. Is current approach still the best?
• "No idea is a bad idea"
  • Even if you think idea is ridiculous, or will never work, give it a trial
  • E.g. In many hard DPs one think this state is so big, we can't do it..and then ... an observation appears! sparce space is possible! problem is doable!

Thinking: Concretely - Symbolically - Pictorially

Think/solving concretely means solving the problem using examples (e.g. Evaluating the series).

• E.g. You are given some formula F(n) for a Sequence: 3 * (n+5) * (n+6) / 2 + 4
• You start to enumerate its values: 4 67 88, then work on its values
• Typically easy and natural
• Helps much in tough pattern problems.
• Bound your mind for given example. Need carefully considering other examples.

Think/solving Symbolically means instead of working using actual objects is to represent every thing Symbolically.

• E.g. You are given some formula F(n) for a Sequence: 3 * (n+5) * (n+6) / 2 + 4
  • Let F1(n) = (F(n) - 4)/3
    • = (n+5)*(n+6)/2
  • Let F2(n) = F1(n-5)
  • F2(n) = (n * (n+1))/2 ... a popular sequence
• In this one, we work over symbols not the concrete values. E.g. X[i-1] + X[i+1] >= 2 X[i] for every 1 <= i <= n-1
• The more you train over it, the better you recognize the solutions. Your abstractions ability improves too.
• Sometimes, you can't recognize the solution without it!

Think/solving pictorially means drawing the problem elements, their relations and figuring properties from the visualization.

• In this one, we try to do visualization
• You could visualize input elements, their relations
• You could visualize the nature of the output
• Many times, it appears with the concrete or Symbolic

Thinking: Problem Constraints

Sometimes Problem Constrains are the clue. Many times it is a guide of how algorithm should be complex! Rarely misleading. Following are some styles:

Common style:

• Just describes problem different limits
• E.g. Constraints : 3 <= N <= 50
• Consider following table as guide (say for World Finals submissions)

Constraining Constrain style

Sometimes they are problem domain specific: max(2*a + b, c) < d

• This one is so critical, never ignore them if you don't understand why this constraint is important
• Many times, such constraints makes a special problem out of a general one. Ignoring them is fatal mistake.

Fake Constraint

Sometimes the constraint is misleading and it is a "fake" limit:

• E.g. what is 1st most right digit in n! where n < 10^18? Simply starting from n = 5, answer is zero!
• Say you need to calculate F(n) where n < 10^9, by analysis you discovered that F(n > 20) is constant, and < 20 is brute forcable!

Cancelled Constrain

Sometimes the constraint is real, but could carefully be eliminated, e.g. Mathematics problems

• As a trivial example for elimination is combination: Choose(1000, 997) = 1000! / (!997 * 3!) = (998 * 999 * 1000) / 6
• Generally, your target calculations could be highly simplified

Thinking - Problem Abstraction

Problem Abstraction is a great tool to have a different view of the problem, where you redefine the problem

in "general" terms AWAY from the problem domain.

E.g. if the problem talks about set of words, and we could translate a word to another according to a cost function.

• What is minimal cost to convert string A to string B.

Problem abstraction: graph node = word, edge cost = cost function.

• What is "shortest path" to move from Node A to Node B.

The Power of Abstraction is that it drops with problem domain (dictionary words in the example) and give you a general definition.

The point, our mind is filled with the basic algorithms definition - hence recognizing the target algorithm FASTER.

So when ever you got a problem, think in some ways to abstract it, you could reach correct algorithm faster than you imagine.

But, never to drop the original problem, sometimes your abstraction drop some important domain consideration.

• E.g. Given set of points in Euclidean space, find a path with the given criteria.
  • Abstracting the problem to a general graph representation, lose the Euclidean space, which was the CLUE!
• E.g. the given graph is bipartite and your abstraction dropped this feature.

Thinking - Problem Reverse

Problem Reverse is to think backward in the problem definition.

E.g. What is probability of event X occurs.

Reverse: What is probability of event ~X. Answer is 1 - ~X. Sometimes Calculating ~X is extremely easier than X.

E.g. We have 2^N subset, find subset with property X (e.g. # 1s are 5).

Reverse: Find subsets with property ~X (e.g. # 1s != 5). Answer = 2^N - Count ~X

E.g. Find Minimum Summation. (many times min/max are interchangeable)

Reverse: Total - Maximum Summation

E.g. Given An "inc/decreasing" generating Sequence (Say Fibonacci), Given a value, what is its index in the sequence?

Reverse: Given an index, could you get its value? If so, Binary Search on X tell finding vlaue index

Sometimes, problem is solvable through its main definition or reversed one. Sometimes, the ONLY way to solve it is its reverse.

Thinking - Problem Simplification

Sometimes, thinking in a simpler or a special version of the given problems, helps you to build up your intuition.

Case 1: Problem to Sub-Problems

In many cases, especially hard problems, a problem may be decomposed of other sub-problems.

Realizing these sub-problems may be easy and may be hard. Sometimes, a problem could be divided in may ways.

Sometimes problems occurs:

You keep trying in the sub-problem with no hope!

Always remember, you are JUST solving a sub-problem you invented.

If could not do it, may be you need to think in other sub-problem...or tackle it in a totally different way

Case 2: From Simple to complex

Sometimes, you could think in a special problem/case, and then try to update the solution for general problem/case.

E.g. Problem mentioned 3 Constraints on the returned output. What if no constraints? What if 2nd constraint only?

E.g. Given R*C 2D array? what if 1*1? 1*2? 2*1? 2*2 ...increment to ... R*C

E.g. Given a polygon? What if it was just a triangle? What if was convex?

E.g. Game consist of N players? What if 1 player? 2? 3 .... N players?

E.g. Given a graph? What if A chain Graph? What if DAG? What if tree?

E.g. Given a 3D shape/array? What if 1D? What if 2D? 3D?

E.g. Given set of Rectangles covering Big Space? What if their coordinates are small?

E.g. Find answer in the given base? What if base only is 10? base is a prime number?

E.g. In many cases, simplification is adhock - think how to start with simple state

Sometimes problems occurs:

E.g. you started to solve the polygon problem for convex case, BUT convex case couldn't be incremented!

E.g. you started to solve the graph problem for DAG case, BUT DAG case couldn't be incremented!

Always have a vision, how a special case may be incremented? Don't consume lot of time without return!

Case 3: Simplification by Assumptions

Idea is to make some assumptions that make problem easier, or special of general one.

Say you have to find X, Y and Z and use them in evaluating F(X, Y, Z).

You got confused due to trying to think in all of them together.

Start to do temporary assumptions to have thoughts about the solution. E.g. What if we SOLVED X, how to find Y and Z?

Found it harder? Think What if we SOLVED X & Y, how to find Z?

Generally,

Problem simplification helps when you can't start with an idea and is stuck.

They open up our brains to think creatively and encourage solutions.

Finally,

The more experience you gain, the harder problems you can directly attack without simplifying them.

Thinking - Incrementally

Incremental algorithm is one that process input step by step, in each step it finds its way to update the old state with new item.

E.g. Given N unordered Numbers, find a sorting algorithm. To think incrementally, you do the following:

[Say we have sorted the first m items], how to add the m+1 item and update array to be again sorted?

If we managed to do that, we found an algorithm.

Let say array is 10 2 7 4 15

Let's say we have sorted the first 3 elements (then we have 2 7 10), could we add 4th element (4)?

YES, move backward tell find an element 4th element is greater than it

Initially 2 7 10 4 NO

2 7 4 10 NO

2 4 7 10 YES

This is called Insertion Sort Algorithm.

E.g. Given an array, we perform K swap operations selected randomly, what is expected array?

[Say we have the answer array after m swaps], how to update the m+1 swap?

Let say we have array a b c d .. a position is prop1 to be selected in a swap, prop2 to not.

Now, let's build answer incrementally, that step by step we update the array.

For each position, it is either swapped with one of n-1 var, or not swapped. Using normal Expectation Equ

E.g, for first position : a' = a*prop2 + b*prop1 + c*prop1 + d*prop1

E.g, for second position: b' = a*prop1 + b*prop2 + c*prop1 + d*prop1

Repeat for k times. SRM575-1-2

** In Many cases, Incremental Thinking needs data sorting, as its idea is based on growing up the solution.

E.g. Given N points in 2D space, find a convex hull of them (later we will take that algorithm)

[If we have the convex hull of the first m points], how to add the m+1 point, and update to the next convex hull?

CAN'T!

Let's sort the points relative to a corner point, could we do the update? YES

E.g. Given set of squares, {(-R, -R), (R, R)}, a random bomb is put inside each square.

Power of a Point is X^2 (X number of bombs in point). Total power is sum of points power. What is expected power?

Sort the rectangles based on R. Say we have expected power of first m rectangles, how to update for next? SRM526.5-1-2

Sometimes, the incremental algorithm order is big, as update operation is costive.

In case order doesn't affect, consider input randomization, sometimes help.

Sometimes update from state to another is systematic, that we could model it in a matrix,

and perform matrix power to get all incremental steps zipped in one matrix.

Thinking - Problem Domain re-interpretation

A problem may have a domain: E.g. given N cities find a path from A to B?

This problem lies in graph theory domain.

What if the cities are in Euclidean space? Then we have 2 involved domains: Graphical and Geometrical.

Sometimes, the solution requires you to re-interpret the problem in another domain. This is not always do-able, but may be the clue.

E.g. Say we have teams in ICPC competitions. Each team has strength (a, b). Team beat another if both a1 > a2 and b1 > b2.

The problem solution in its internals requires knowing how many teams I could beat. This is doable in O(n^2). What if n so big?

Could you reinterpret this problem domain? Yes, Geometrically!

Imagine plane where points are strength (a, b).

Now, Team with (a, b) beats the teams in rectangle (a+1, b+1) - (MAX_A, MAX_B). Find fast way to count them FAST.

E.g. Given a sequence S of integers, and operation to minimize an item by 1, what is minimum operations applied to

let this sequence convex (e.g. S[i-1] + S[i+1] >= 2 * S[i], for each i)

Imagine plane where points are (idx, S[idx])...start to draw lines from ith point to....and do.... (don't care with details)

E.g. You are given set of states, each one is represented in terms of other sub-states, evaluate value for a given state.

Let's reinterpret it Mathematically. Let each state is variable. Then we have N variables.

Construct a matrix of the variables relations, Gaussian Elimination is the solution .... (don't care with details)

E.g. Given set of boxes, each box has a key and is opened by certain key. Given a starting key, could you open all of them?

Let's interpret it Graphically. Think in keys as graph nodes. We start from certain node(key). We move from key to another, by opening a box.

Solution now is Eulerian Path.

What about thinking in boxes as nodes, and form box to box an edge if it has its key. An extra source node for the starting key.

Thinking - Search Space and Output Analysis

One of important ways to tackle a problem is to start from the output and analyze it and its space.

When we are solving a problem, there could be many candidate solutions for it.

A candidate solution is a member of a set of possible solutions to a given problem.

A candidate solution does not have to be the target solution to the problem – it is just part of the set that satisfies all constraints.

The space of all candidate solutions is called the feasible region, feasible set, SEARCH SPACE, or solution space.

Every candidate solution C, is good IFF satisfiyConstraints(C) = TRUE

Every candidate solution C is mapped to F(C) which is the evalaution of this C.

There are 3 things to consider:

Let S = {C1, C2, ...} Set of candidate solutions

Let's Define F(C) according to problem Statement.

Let F(C) = O, the output of the function.

We need to think in:

1) Size of Cs - # of candidate solutions

2) Nature of F - The function that generates the output

3) Output Bounding - Output of the function.

------------------------------------------------- Search Space Size |S| -------------------------------------------------

Sometimes, all seacrh space size |S|, is small enough to brute force it.

Brute-force search(exhaustive search) is to systematically enumerating all possible candidates for the solution and

checking whether each candidate satisfies the problem's statement.

E.g. given an array of length N = 1000, what is maximum difference between a pair of numbers?

What is search space? It seems we could try every pair, and maximimze among them.

Then we try N^2 pair, overall 10^6 solution, which is doable! So brute force is enough.

Let Say array is: 2 5 1 4 -> Then we try

C : (2, 5), (2, 1), (2, 4), (5, 1), (5, 4), (1, 4)

F(C) = |A-B|: 3, 1, 2, 4, 1, 3

Then best C is (5, 1) with F(C) = 4

See 3D Image.

What if N = 100000, then we have 10^10 pair! Then exhaustive search is impossible! Typically like many problems.

Then, we need to think in better ways. Better algorithm may be many thing! Let's give an observation.

Observation: The maximum difference will be between the smallest and largest number!

Then, if we sorted the array, last-first is the solution.

Sort is nlogn. So 10^5 is dobale.

Sorted array: 1 2 4 5. Solution is 5-1=4

Sometimes, we implement the exhaustive search, but we do lots tricks to make it within time using

E.g. Search space pruning, Branch and Bound, Memoization....

------------------------------------------------- Nature of target Function -------------------------------------------------

We need to think about the requested function. Sometimes there are popular styles and sometimes it is adhock. Let's see adhock cases.

Decision problem (True / False)

2 SAT, Bellman Difference constraints - Games(Nim/Grundy) - Graph Conflict? Is Bipartite? Do system of linear equation has solution?

Optimization problems: Find minimum/maximum F()?

First thing to think about are all algorithms that could do optimization.

Common: BF, Dfs, BFS, DP, Greedy, Bi/ternary Search - D & C - B & B - RMQ/LCA - Line sweep - MCMF ...

Minimization: Min cut / vertex - MST - Dijkstra - Convex hull ...

Maximization: Max flow - Max Independent Set - GCD ...

Counting problems:

E.g. DP - Combinations - Permutations - Inclusion-exclusion - Matrix power

In counting problems, especially DP problems, answer may be computed in different ways. One of them mab be the clue.

Say, we have M segments, each of length L, and want to know how many ways to count configurations?

You could think data is built layer by layer, and next layer is connected with sometihng in old layer (3 layers)

You could think in segments in traversal oder, from left to right...going bottom and up

---1--- --4---- ---6--- ---10---

---2--- ---7--- ---9---

--3--- --5--- ---8---

Generally we need to think in F and its nature, especially in adhock cases

Equations reformulation

In many cases an equation could be extracted (if not given explicty), and reformulating make solution clear

Nested and triple linear summations most probably will be reformulated

------------------------------------------------- Output Bounding -------------------------------------------------

It is very important to bound the output of the function F. That's we bound its min value or/and its max value?

In many cases, this is the clue. You may estimate different bounds, based on your needs.

That is say, we could do it using O(nlogn) algorithm. If we managed to do a bound of < 100000 for output.

Then it is enough, ALTHOUGH correct bound is 5000.

Let's try problem SRM522-1-2(CorrectMultiplication)

Given a, b, c: Find minimum value of |A - a| + |B - b| + |C - c|, where A, B, and C are positive integers satisfying A * B = C.

Once: Let a, b, and c <= 10^6

Once: Let a, b, and c <= 10^9

You could think in 2 synonymous things to bound: (A, B, C) or RESULT = |A - a| + |B - b| + |C - c|

Clearly bounding the RESULT bound the 3 variables, espeically due to nature of multiplication.

What is best RESULT ? A=a, B=b, C=c, then RESULT = 0

What is worst RESULT ? A=a, B=1, C=1, then RESULT = a + b + c - 3

How the worst case bound A, B and C?

Let C = Result+c, then |a + b + c - 3 +c - c| = |a + b + c - 3|

Then Clearly, C must be <= Result+c

Similarly: A <= Result+a and B <= Result+b

Then for every A <= Result+a and for every B <= Result+b do check! This will never run in time!

We know that A*B = C, then A <= C and B <= C --> Then A <= Result+c and B <= Result+c too. Doesn't help!

More utilization for *, Let A=X, then B <= C/X. That is B is tightly bounded with value of A.

Then for every A <= Result+c and for every B <= C/A do check. This fit for case <= 10^6 ONLY

The intersting thing is that, Given A, we could approzimate B = c/A. It could be fraction, so try -1, +1. Still only fit to 10^6

Let's think in multiplication more! 12 = 1*12, 2*6, 3*4, 4*3, 6*2, 12*1

Wait, after sqrt is repetation for what is before it! A, B are the 2 factors of C.

Then, we could only try A up to sqrt(Result+c). In a real contest, you could think, i don't need to know result+c. Assume it even to 10^10!

Trying As up to sqrt, doesn't consider cases when it is after sqrt. So swap (a, b) and do same. This way we guarntee it is tried.

Let's try problem SRM507-1-2(CubePacking)

We have Ns cubes with edge length 1 and Nb cubes with edge length L. Ns(10^9), Nb(10^6), L(10).

What is min volume of box to pack all cubes.

You could think in 2 synonymous things to bound: (X, Y, Z) or RESULT = X*Y*Z

Clearly answer(2, 4, 5) is same as (5, 4, 2). So we consider only X <= Y <= Z

BruteForce:

For each X up to some bound

For each Y up to some bound

Find Z given X, Y

Unless we found so tight bounds, we should think in other approach!

Let's try to bound the result.

If we have Nb cube only, result is L^3 * Nb = 10^9

If we have too Ns cube, we could set them in base L^2. So answer is 10^9 + 10^9/10 <= 2 * 10^9

So we have a bound 2 Milliars for the result. Big? No, it is X*Y*Z <= 2 * 10^9. See how this would affect X, Y, Z

Let bound be 1000. What is max values: 10*10*10. As if X = 11, then Y < X and we said X <= Y <= Z

So actually X is limited to Cube root, Result^(1/3)

Similarly, if we have an X, then Y is limited such that Z >= Y. Then X * Y * Y <= RESULT

for (ll x = L; x <= limit/x && x*x <= limit / x; ++x) { // make sure x * x * x <= limit

for (ll y = x; x <= limit / y && x * y <= limit / y; ++y) { // make sure x * y * y <= limit

Thinking - Observations Discovery

In many cases, a hard problem is based on observations.

Actually, one observation may lead to a solution, while another lead to a different one.

One of best ways to discover properties of a problem is through test cases TRACING.

Pick test cases one by one, from smaller to larger. Trace the sample & try to discover properties & patterns

As long as tracing new bigger sample helps you think/understand more, trace more.

Typically properties are adhock, and this what makes them hard.

E.g. the problem depends on a given triangle with certain construction steps, say similar to pascal triangle, findings its properties is the key

The worst scenario is when you dig for properties that is not the key for solution.

Sometimes, it is hard to discover the properties by analysis on papers. Try to write some SAMPLE code on PC.

e.g. bf solution and see the output - enumerating sequence elements to find pattern

NEVER to start by the pc to find observations. Always try on papers, and move if stuck

Remember, code = bugs. So avoid big codes for observations, to avoid losing your time.

Your turn to balalnce between need to work on paper vs PC

Some popular properties:

Sparseness: E.g. You have State (X, Y) and move to State (X/2, Y/3). X, Y is 10^9, but we have only logX * logY state.

Constrained Input combinations: When not every input combination is valid.

E.g. Say input X <= N and Y <= M, typically we expect N*M possible inputs.

But given is that X binary representation won't Intersect with Y Binary representation.

Symmetry: the output 2D array is symmetric - F(angle) is symmetric in [0-PI], the given sequence repeats in a symmetric way.

Inference: Z = 2*(X+Y)+3, Height = Area(mask) / Width ... then we don't need to think in the Inferenced ariables

Redundancy:

Button if clicked is on, if re clicked is off. Doesn't matter how many times clicked. Either even or odd clicks.

Clock moves, after some moves, it back to original

In-dependency: A problem could be simplified by realizing its parts.

Minimize some Manhattan Distance = Minimize on Xs + Minimize on Ys

F(Start, End) = F(Start, MID) + F(MID, End) For every possible Mid

In probability: When Trials are Independent then: sum of the expectations = expectation of the sum

Independent Games(Grundy)

Adhock: Given set of words, align them. Given rule two align 2 consecutive words. Then, each word is dependent ONLY on previous word.

IO re-representation: E.g. Given Graph --> S/CC - Given Array --> Sorted array - Frequency Array

Given input graph, is it: Tree, DAG, Complete, Bipartite

Given polygon, is it: Convex? Concave? General?

Given X find smallest Y such that X%Y ... ? Then we care only with MODE

Find numbers with property X? E.g. palindromes

a) You could try all Xs and check IsPalindrome(X)

b) Find properties of X to directly generate it.

Find count of numbers with properties p1 & p2 (e.g. prime & palindromes)

how many p1’s? p2’s?, who to generate first?

Find tuples with property: at least one of them >= D

Negation of = Find tubles with each one < D-1

Find tuples with property: Each one of them <= D1 AND at least one of them >= D2

= Range Substraction of {Each one of them <= D1} - {Each one of them <= D2-1}

Note: Ys property = Don't Include !Ys. Double Negation.

Is input built in algorithmic way? It may be the clue

Large 2D array, but it is just (N/5, N/5) repeated every where

Graph constructed by repeating certain operation

Sequence gernerated by certain formula: A[i] = oper(A[i-1])%D

Splitting vs Combining

1 Big Object (e.g polygon) consists of N small Objects (e.g. triangle)? Can the N elements fit in big object

Try splitting big objects to small ones

Try to merge small objects in big one

Atmost vs Exact

atmost(n) = exact(1)+exact(2)...exact(n)

exact(n) = atmost(n) - atmost(n-1)

Canonical Form

When you need to compare two things one-to-one correspondence think about CANONICAL form

Fast Reduction

E.g. we have F(X), but it moves to F(X/2). Even X with 10^18, it finish in logX steps.

Cycle tricks

Say we evaluate a^0 % n, a^1 % n, a^2 % n ....a%k % n. Let k > n

Then at some a^t = a^f where f < t. In other words, this mode value appeared before. So Sequence of modes repeats.

Input Function Nature

Exponential

F(X > Limit) = Constant

Increasing Sequence

Uni-modal Sequence: function that is either increasing and then decreasing or vice versa

Thinking - Misc

1- The Brute Force solution

One of best ways to think about the problem, is the Brute Force solution

Even if you think it won't be the solution, or not practical at all

In many cases, solution is the BF one, but improved based on observations / clever coding.

It needs minimal thinking, hence push your mind to start from trivial to complex -> avoid OVERESTIMATION

In worst case, BF let your mind swim in something, rather than being stuck!

Think in BF ITERATIVE and RECURSIVE. Think about Search space & Search State

2- The similar problems - advantages & cautions

Sometimes, when you read a problem, you know you met a SIMILAR problem

Sometimes, it is an advantage that you worked your mind in such problem and have some properties about it

Many times, you use your old solution for the new problem, and fails, because you need to ask:

a) what exactly was same in old problem

b) what is different? How these changes may CHANGE the solution

DON't let the similar problem MISLEAD you

3- Still Stuck? Try to re-state the problem definition in 2 or 3 different ways, and see if this helps.

3- Still Stuck? Do BF & Observe. Write the impractical BF solution, and try to find a pattern for answer / useful fact

4- Still Stuck? Do Guess & Check. Guess some ideas & assumptions, do extensive verification over test cases.

5- Still Stuck? Iterate on your algorithms list, see if it could be the solution.

6- Be careful in analysis for solutions. You may discard a correct solution

E.g. Calculated O(n^3) although it is O(n^2logn)

E.g. Calculated recursion depth wrongly, then DFS seems to be TLE/RTE

7- Sometimes you work with so BIG N, or your Order is BIG, some tips & tricks:

- Check Exact # of operations Not the Order?

- Check for Reduced variables & Constrained input combinations

- Check calculations sparseness & symmetry (e.g. Powering a matrix result in 6 unique values, and all others are repetitive)

- Reference of locality tricks

- Order loops such that: loops don't pass over arrays is in depth. Watch-out from Col-order accessing

- May duplicate some memory to switch some col order to row order

- Pre-computation

-- Full, Partial (Range Props)

-- Preprocessing

*) You can think in pre-computation in input like {N<500 or A,B < 30)

*) Think in all kind of pre-computation and try to utilize any of them.

*) Think in partial preprocessing/pre-computation

*) Divide to SQRT(n) ranges and calc reminder in time

*) Calc on machine a small temp array that help you in run time

*) A[10], each answer is answer for i*10^6

*) In Query problems, consider sorting quries TRICK

- Clever tricks

- Say we have 3 loops of 2.5 * 10^8 operation which is beyond accepted 10^8 operation.

- Say there is some break conditions there, you may think how to

- Order loops

- Order data (e.g. sort array or reverse its sort)

Such that loops break so early as much as possible. E.g. SRM421-1-2(CakesEqualization)

--------------------------------------------------Thinking - Solution Verification--------------------------------------

Finally Found a solution? Wait!

The most common case for contestant is to rush to code it! Ignoring Verifying the solution.

But before you verify, you should remember KISS! Could we find something simpler!

Verifying the solution requires:

1- Test cases Verification(Ones in statement, boundaries, yours)

2- Solution Order: Time & Memory

3- Full logic & intuitive Revision

4- Correctness, at least good intuitive - Assumptions validations

5- In case recursive code, does depth fit?

6- In case (*+^) operations, Any overflow(intermediate & output)

7- In case Double /, Is precision fine?

--------------------------------------------------Thinking - Solution Implementation--------------------------------------

Again: Discipline + Out of comfort zone is the key for your level improvement

Write now, you r supposed to have a verified idea. Before moving to coding it, you need to have FULL vision about code.

1- Start to think about code blocks, the "repeated" ones, and the code order

2- Think about little different ways to do it, especially when you think you do lots of code for sub-target.

3- For every block out of your comfort zone, Write full code on a paper

After Implementation

1- Revise code order & logic. Make sure it matches what you intended

2- Challenge every block of code. Never to read in a way that dop even ONE character

3- Think how this block of code may fail. Think in corner cases of it (E.g. this A/B...could B = 0?)

4- Revise data types, especially in overflow problems

5- Be careful from /, % for RTE, +, * for Overflow, Integer Division instead of doubles.

6- Double comparison, precision of +- numbers [(int)(a +/- EPS)]

Testing

Test special cases. Testing the boundaries is a must + revise SPECIAL CASES.

E.g. Given X --> Test -a, 0, +a, and specially MAX of -a, a

E.g.Board N*M --> 1*1, 2*2, 3*3, 1*M, N*1, N*M.

E.g. Given sequence of numbers --> test distinct, repeated, 0-length seqs, N-length seqs, all pos, negative, mix

Failed?

Check Error Inspection List

Got accepted? Tips for Improving your self Further

1- Try to make code shorter. Check other coders available codes, like in TC, learn from it.

2- Try to make code faster. In site like SPOJ and UVA, you could know the fastest solutions. Challenge yourself

3- Check if possible for other approaches for the solving. E.g. See Forums / Editorial.