SPOJ List

Updated automatically every 5 minutes

CPRIME - optimized sieve of eratothenes

TDKPRIME - optimized sieve of eratothenes

PRIMES2 - optimized sieve of eratothenes

FCTRL - number of zeros in factorial n

BRCKTS - BIT, segment tree

BOXES - minimum cost flow, comment: see adrian kuegel's post

ONEZERO - BFS

STRDIST - DP, optimization

MARBLES - combinatorics, x1 + x2 + ... + xk = n with xi>=1 (1<=i<=k)

DISUBSTR - suffix array, suffix tree

BIA - dominator tree in a flow graph, paper by Lengauer and Tarjan

ASSIST - easy, precalc

NHAY - KMP

PERIOD - KMP

REPEATS - KMP, suffix array, comment: for nlogn solution see gawry's post

PT07X - minimum vertex cover of a tree

MINDIST - greedy, graph theory, tree, good

DQUERY - data structues, BIT, segment tree, preprocessing

SEGMENTS - greedy, good

STABARDS - bipartite matching

AE2A - DP, probability, guesswork

GCD - number thoery, interesting

TWOSQRS - number theory, comment: see posts in forums for comparison of different approaches

MAXISET - backtracking, prunning

MINUS - DP

PALIN - Finding the next palindrome of a given number, SRM 330, Div-2 Hard

POSTERS - line sweep, binary heap, interval tree

MATRIX2 - sliding RMQ, see pegwiki, IOI06 Pyramid

SWAP - BIT, inversions, good

DISPUTES - DP, trick, brute force

INTERVAL - sorting, greedy, binary search

PARITY - bits, math, backtrack

WINDMILL - observation

MAXLN - geometry

BRICKS - merge sort

BYTESE1 - dijkstra

MST - MST

BLINNET - MST

MSTS - bfs, union find, gaussian elimination, chinese remainder theorem, comment: see misofs post

PRMLX - combinatorics, postition of a permutation

ANARC08C - KMP, greedy

VPARTY - maximum matching in general graph, edmond's blossom algorithm, see StevieT's post

MCQUERY - all pairs maximum flow, gomory-hu trees, comment: two other problems using this algorithm can be found at UVa

RACETIME - merget sort, k-th smallest integer, binary search

QMAX3VN - BIT, BST, comment: look at topcoder forum for stjepan's bst solution

GSS6 - similar to QMAX3VN, Treap

CF36D - game of acyclic graph, see codeforces

NOCHANGE - DP, hard, comment: see humblefools explanation / SRM 416, Div 1 500.

STORE - DFS, articulation point

LAZYCOWS - DP, observation, comment: see paladin8's post

MATRIX - optimization, comment: see prunthaban solution, plus seeing this thread wouldn't hurt: http://acm.uva.es/board/viewtopic.php?t=5811

LIM - gaussian Elimination

GS - gaussian Elimination, comment: Look at CEOI 2010 arithmetic rectangles

NWERC04H - gaussian elimination

BANDMATR - gaussian elimination, hell

DOCTOR - gaussian elimination, comment: see NilayVaish, braineter and abstractwiz post, idea is similar to Div-1 Medium SRM 306

CMPLS - lagrange interpolation, gaussian elimination

BMJ - hexagons, patterns

DISTANCE - analysis, brute force, comment: similar to

GSS2 - sotring, segment tree

CTGAME - histogram, stack, binary tree

KQUERY - data structures, sorting the queries

KQUERY2 - data structures, like RACETIME, comment: see decowboy's post on forum for an interesting approach

DQUERY - data structures, sorting the queries

LUCKYNUM - BFS

SSHUFFLE - DP

WEIRDFN - heap, priority queue, comment: tc forum says priority queues were slow, but someone solved it with PQ.

ASISTENT - permutation ranking

BABY - min-cost maximum matching, DP, comment: DP is hard to get AC

DIVSUM2 - pollard's rho factorization

QTREE - lca, heavy light decomposition

QTREE2 -

QTREE3 - segment tree, heavy light decomposition, comment: see stjepan thread, OTOCI is a harder one

QTREE4 -

OTOCI - heavy light decomposition, harder version of QTREE3

TOUR - transitive closure, comment: transistive closure in O(n^2)

SKYLINE - catalan number

MINCOUNT - math

HEAPULM - hard, heap, treap, comment: there is a linear solution, see defrager's comment

LIS2 - coastline algo by misof, comment: read two good post made by venco and bbi5291

NICEDAY - coastline algo by misof, comment: See http://www.algorithmist.com/index.php/LA_3525

FRACTION - farey sequence, comment: see a solution by sql_lall in tc forum based on gcd, closed form is in concrete mathematics

ACS - puzzle

SQRBR - DP

TWENDS - DP

SEQPAR - greedy, good

MRECTCNT - number theory

PAGAIN - number theory, primality testing, miller rabin

PON - number theory, primality testing, miller rabin

PGCD - number theory

LCMSUM - numbet theory, euler totient function

ASSIGN4 - min-cost max-flow

COCONUTS - min-cut

COURIER - DP

DOMINO2 - inclusion-exclusion, hard

PERMSG - solving system of linear congruence

SUPPER - LIS, good

DPEQN - number theory

INUMBER - number theory, interesting

PRIMIT - graph theory, degree count, comment: read this polish solution :P http://oi.edu.pl/old/html/blue/download/oi6-etap3.ps.zip

LAZYCOWS - dp, good

INTERVALS - sets

KGSS - segment tree

KPPOLY - geometry, ternary search

PALSEC - DP

PARTSUM - data structures, good

MINMOVE - lyndon words, comment: see thread posts by blueblimp and others

SUBS - strings, binary search

SCITIES - kuhn-munkres

SUBSUMS - meet in the middle, comment: see LongPipes, the Div 1 hard from SRM 205

LOTTERY - BST, sets, comment: see thread with cpphamza's post

PHONY - number theory, good, comment: see misof's post

SAMER08D - DP

HIGH - determinant, kirchoff's matrix tree theorem

MPOLY - DP, geometry

CVXPOLY - DP, geometry

MTRIAREA - DP, geometry

MORSE - DP, trie

RENT - DP, BIT

CEOI09HA - DP, convex hull optimization, comment: see pegwiki

NKLEAVE - DP, convex hull optimization

SUBST1 - string, lcp, segment tree, suffix array, comment: see manber's article link in tc forum, post by MauricioC and ardiankp

CCOST - BIT, finding a way to change 2D range sum to 1D, comment: see gawry's post in TC

CHASE - geometry, maximum number of points on a line, line-point duality, hashing, comment: see eleusive's post in forums

HORRIBLE - segment tree, lazy propagation

TLE - dp, optimization, comment: if you are stuck, took at StevieT's post

CASHIER - RMQ, deletion

ANARC08I - efficient printing of a walsh matrix

RSORTING - DP, hard, comment: see BOI 2007 booklet, problem: sorting

BOI7SOU - RMQ, nice trick, comment: see BOI 2007 booklet, problem: sound

BOI7FEN - dijkstra, geometry, encircling trick, comment: see BOI 2007 booklet, problem: fence

BOI7ESC - min-cut, maximum flow, dfs, vertex splitting, comment: see BOI 2007 booklet, problem: escape

CONNECTE - matrix exponentiation, comment: link: http://vn.spoj.pl/problems/CONNECTE/ see BOI 2007 booklet, problem: points

BOI7SEQ - DP, greedy, comment: see BOI 2007 booklet, problem: sequence

EOPERA - IDDFS, comment: similar problem www.hsin.hr/2010/coci/contest2_tasks.pdf, but ikatanic says this solution is slow

TREESUM - tree, dfs, combinatorics, binomial theorem, comment: see nokia's explanation in forums

SCALES - DP, comment: see StevieT's post

SUMFOUR - given 40000 a's, b's, c's, d's, find how many a+b+c+d=0

TRGRID - pattern, case analysis

BITMAP - BFS

WORDEQ - Union-find

M00PAIR - DP

MOD - discrete log, baby step giant step

ORDERS - permutation reconstruction, fining k-th remaining item in logN, comment: see gawry's binary tree implementation at forum

ORDERSET - treap, splay tree

OPTM - max flow, comment: Similar to SRM 442 Div 1 Hard

ALL - BFS

AMATH - number theory, big integer

AMBM - greedy, comment: kinda like FibonacciKnapsack of TC, see moshiur's blog for proof

AMR10E - matrix multiplication, good, comment: amritapuri 2010

ANARC08D - DP, triangular grid

ANARC08J - bruteforce

ANARC08J - sorting

ANARC09F - geometry

ANTTT - graph theory, geometry

AP - bipartite matching, DP, comment: google codejam APAC Semifinal 2008, see ACRush's code

ARCTAN - math

ARITHSEQ - DP, brute force, cycle finding, comment: brute forcable in time limit, observation: cycles

ARRANGE2 - backtrack, heavy optimization, comment: codechef problem

TREECST - graph theory, DP, comment: see COCI 08-09 contest 1, problem KRTICA

BARB - modular arithmetic, brute force

BFALG - modular arithmetic, extended euclid, chinese remainder theorem, fibonacci

BLUEEQ2 - number of solution of an eq k1x1^p1+k2x2^p2+...+knxn^pn where k, p are known

BOBALLS2 - bouncing balls, math

BOOKCASE - DP, good

BORW - dp, easy, comment: huge timelimit

BOYSCOUT - DP, geometry

BRCKGAME - DP, good

CHOCOLA - greedy, good

KPSUM - DP, digits, comment: pattern solution described by rem in forums(RIP).

DOORSPEN - geometry, convex hull

BSHEE - geometry, convex hull

BULK - geometry, cube, stuff

SEGVIS - geometry, visibility

CONDUIT - geometry, lengths of OR of lines

STONE - geometry, centroid of polygon

RUNAWAY - geometry, largest empty circle

DIRVS - geometry, shortest path

RAIN1 - geometry, envelopes

DRAWQUAD - geometry, max area quadrangle from 10^3 points

TCUTTER - geometry, co-ordinate compression, graph traversal

LITEPIPE - geometry, line segment intersection

RHOMBS - geometry, rhombus, looks hard

FSHEEP - geometry, point in polygon in O(lg n)

FLBRKLIN - geometry, BIT

CERC07P - geometry, sorting, costline?

BAC - geometry, voronoi

Note: I have been following topcoder forum for quite a while. Every time there is an interesting discussion about something (a discussion involving of high rated coders/interesting topics), I created an entry in a text file for future reference. I collected some of the problems from other sources as well. It will help you to set contests. But it is full of spoilers and should not be used extensively for someone’s own training.

-- Mir Wasi Ahmed

PS: I stopped updating this list a while ago.