List of interesting problems on SPOJ

Posted on by
3

List on interesting problems on spoj

DP:

  1. Advanced edit distance ADVEDIST
  2. Distinct Subsequences DSUBSEQ
  3. Juice Extractor JUICE (very cool problem)
  4. Coins Game MCOINS ( easy dp to practice )
  5. Bob and magical scale MGCSCLS
  6. Boy scouts BOYSCOUT (n^4 passes)
  7. Palindrome 2000 IOIPALIN ( calculate LCS of string and it’s reversed form )
  8. Counting binary strings STRCOUNT (dp /recurse + memo)
  9. Another tree problem MTREE ( cool problem, dp + dfs )

Max flow – min cut and similiar

  1. Fast Maximum Flow FASTFLOW
  2. Gas Wars GASWARS
  3. Fast Maximum Matchig MATCHING
  4. MobiZone vs VinaGone MOBIVINA
  5. Group partition MPART
  6. Potholers POTHOLE
  7. Disjoint Paths DISJPATH
  8. Oil Company OILCOMP (most efficient algorithm here is dinic( but simple dfs passes too), also this task can be done with bit masks. Tricky task. )

Math problems, combinatorics and similiar

  1. Win gold medal WINGOLD
  2. OAE OAE
  3. Non-decreasing digits NY10E
  4. Special Numbers NOVICE63
  5. N-factorful NFACTOR
  6. N DIV PHI_N NDIVPHI
  7. Legrende Symbol LEGRENDS
  8. LCM Sum LCMSUM
  9. IOI camp sequence ICAMPSEQ
  10. Suffix of cube CUBEND ( had a lot of fun while solving this )
  11. A HUGE TOWER CTOI10D3
  12. Skyline SKYLINE
  13. Flibonakki FLIB ( matrix expo, try to get 2×2 matrix or try to speed up 3×3 matrix calculation )

Graph problems

  1. Arbitrage ARBITRAG (floyd-warshall)
  2. Code CODE ( very cool problem, find euler tour with DFS and print it reversed )
  3. Frogger FROGGER ( i call it 3d bfs, funny problem )
  4. Indiana Jones and the lost Soccer Cup GCPC11C ( find if there’s only one way to topological sort )
  5. Time to live GCPC11J ( longest path in tree )
  6. Ghosts having fun GHOSTS ( on-line algorithm for checking if DAG stays acyclic after adding edge to it )
  7. Hierarchy MAKETREE (topological sort)
  8. Paradox PARADOX ( dfs )
  9. Query on a tree QTREE ( LCA )
  10. Query on a tree 2 QTREE2 ( LCA again )
  11. Wandering Queen QUEEN ( BFS + bit mask )
  12. Robots on grid ROBOTGRI ( bfs/dfs + dp )
  13. Elevator trouble ELEVTRBL ( simple BFS )
  14. Mega inversions TRIPINV ( find amount of triplets which satisfy : i<j<k Ai>Aj>Ak. Hint : 2 Binary indexed trees )
  15. Capital City CAPCITY ( find nodes from which we can achieve other nodes )
  16. Cost KOICOST ( reverse the problem )

Computional geometry:

  1. A Chase in wonderland CHASE ( find maximum size of collinear points)
  2. Closest pair of points CLOPPAIR
  3. Bob and his new kite factory KITEPRBL ( three things to practice )
  4. Closest Triplet CLOSEST
  5. Cocircular Points MCOCIR (hardest part is to get working well equations )
  6. The Ant ANTTT ( simple line intersection exercise + find and union 😉 )
  7. Doors and penguins DOORSPEN ( similiar to separate points, but now we must deal with rectangles, not points )
  8. Maximum triangle area MTRIAREA ( given points on a plane find 3, which form biggest triangle area )
  9. Separate Points SPOINTS ( given n+m points on plane, find straight line which separates n points from m points )
  10. Military Story VMILI ( convex hull and other stuff )

List will be successively updated.