One Algorithmic Site A Day

Uva Online Judge Solutions

2011-07-08T00:53:00.000+03:00

There is a big disadvantage about online judges.

You know the correct algorithm, but a newline character or a space may change the result from "Accepted" to "Wrong". Since the outputs of your program are checked with the correct ones, you can't be sure if there is a problem in your solution algorithmically.

Those times, you have to check your solutions with others to ensure your algorithm. And here I give you a site with full of uva problem set solutions. The site is founded by two college students to have a repository of solutions during ACM ICPC preperation.

Uva Online Judge hints and algorithmic solutions are @ http://www.questtosolve.com/

They are inspired by Steven Halim's World of Seven, which is another website for the solutions or better to say solution hints.

You can browse solutions to the Uva Online Judge Problems with a single click including
#104 - Arbitrage, #106 - Fermat vs. Pythagoras, #107 - The Cat in the Hat, #108 - Maximum Sum, #109 - SCUD Busters, #115 - Climbing Trees, #116 - Unidirectional TSP, #122 - Trees on the level, #123 - Searching Quickly, #124 - Following Orders, #130 - Roman Roulette, #133 - The Dole Queue, #140 - Bandwidth, #144 - Student Grants, #145 - Gondwanaland Telecom, #147 - Dollars, #153 - Permalex, #155 - All Squares, #161 - Traffic Lights, #167 - The Sultan's Successors, #170 - Clock Patience, #190 - Circle Through Three Points, #191 - Intersection, #195 - Anagram, #200 - Rare Order, #202 - Repeating Decimals, #216 - Getting In Line, #253 - Cube painting, #254 - Towers of Hanoi, #260 - Il Gioco dell'X, #270 - Lining Up, #271 - Simply Syntax, #275 - Expanding Fractions, #294 - Divisors, #296 - Safebreaker, #297 - Quadtrees, #300 - Maya Calendar, #315 - Network, #332 - Rational Numbers from Repeating Fractions, #336 - A Node Too Far, #337 - Interpreting Control Sequences, #340 - Master-Mind Hints, #341 - Non-Stop Travel, #343 - What Base Is This?, #344 - Roman Digititis, #346 - Getting Chorded, #348 - Optimal Array Multiplication Sequence, #356 - Square Pegs And Round Holes, #357 - Let Me Count The Ways, #371 - Ackermann Functions, #377 - Cowculations, #378 - Intersecting Lines, #386 - Perfect Cubes, #389 - Basically Speaking, #408 - Uniform Generator, #413 - Up and Down Sequences, #429 - Word Transformation, #437 - The Tower of Babylon, #438 - The Circumference of the Circle, #441 - Lotto, #442 - Matrix Chain Multiplication, #448 - OOPS!, #455 - Periodic Strings, #457 - Linear Cellular Automata, #459 - Graph Connectivity, #465 - Overflow, #469 - Wetlands of Florida, #474 - Heads / Tails Probability, #481 - What Goes Up, #482 - Permutation Arrays, #485 - Pascal's Triangle of Death, #487 - Strategic Defense Initiative, #489 - Hangman Judge, #492 - Pig-Latin, #498 - Polly the Polynomial, #501 - Black Box, #507 - Jill Rides Again, #514 - Rails, #515 - King, #516 - Prime Land, #524 - Prime Ring Problem, #531 - Compromise, #534 - Frogger, #536 - Tree Recovery, #537 - Artificial Intelligence?, #539 - The Settlers of Catan, #540 - Team Queue, #541 - Error Correction, #542 - France '98, #543 - Goldbach's Conjecture, #557 - Burger, #558 - Wormholes, #562 - Dividing coins, #571 - Jugs, #574 - Sum It Up, #580 - Critical Mass, #583 - Prime Factors, #587 - There's treasure everywhere!, #590 - Always on the run, #594 - One Little, Two Little, Three Little Endians, #601 - The PATH, #602 - What Day Is It?, #608 - Counterfeit Dollar, #615 - Is It A Tree?, #619 - Numerically Speaking, #620 - Cellular Structure, #621 - Secret Research, #624 - CD, #637 - Booklet Printing, #639 - Don't Get Rooked, #642 - Word Amalgamation, #644 - Immediate Decodability, #657 - The die is cast, #661 - Blowing Fuses, #673 - Parentheses Balance, #674 - Coin Change, #675 - Convex Hull of the Polygon, #701 - The Archeologists' Dilemma, #729 - The Hamming Distance Problem, #739 - Soundex Indexing, #740 - Baudot Data Communication Code, #748 - Exponentiation, #750 - 8 Queens Chess Problem, #753 - A Plug for UNIX, #763 - Fibinary Numbers, #782 - Contour Painting, #784 - Maze Exploration, #785 - Grid Colouring, #820 - Internet Bandwidth, #821 - Page Hopping, #825 - Walking on the Safe Side, #836 - Largest Submatrix, #843 - Crypt Kicker, #846 - Steps, #847 - Multiplication Game, #850 - Crypt Kicker II, #872 - Ordering, #991 - Safe Salutations, #10000 - Longest Paths, #10002 - Center of Masses, #10003 - Cutting Sticks, #10007 - Count the Trees, #10009 - All Roads Lead Where?, #10010 - Where's Waldorf?, #10012 - How Big Is It?, #10014 - Simple Calculations, #10015 - Joseph's Cousin, #10017 - The Never Ending Towers of Hanoi, #10023 - Square root, #10025 - The ? 1 ? 2 ? ... ? n = k problem, #10026 - Shoemaker's Problem, #10033 - Interpreter, #10034 - Freckles, #10036 - Divisibility, #10042 - Smith Numbers, #10044 - Erdos Numbers, #10048 - Audiophobia, #10049 - Self-describing Sequence, #10051 - Tower of Cubes, #10056 - What is the Probability?, #10057 - A mid-summer night's dream., #10067 - Playing with Wheels, #10069 - Distinct Subsequences, #10070 - Leap Year or Not Leap Year and ..., #10074 - Take the Land, #10077 - The Stern-Brocot Number System, #10078 - The Art Gallery, #10080 - Gopher II, #10081 - Tight Words, #10099 - The Tourist Guide, #10100 - Longest Match, #10102 - The path in the colored field, #10104 - Euclid Problem, #10105 - Polynomial Coefficients, #10107 - What is the Median?, #10111 - Find the Winning Move, #10112 - Myacm Triangles, #10115 - Automatic Editing, #10116 - Robot Motion, #10125 - Sumsets, #10128 - Queue, #10129 - Play on Words, #10131 - Is Bigger Smarter?, #10137 - The Trip, #10139 - Factovisors, #10141 - Request for Proposal, #10142 - Australian Voting, #10150 - Doublets, #10152 - ShellSort, #10161 - Ant on a Chessboard, #10162 - Last Digit, #10165 - Stone Game, #10167 - Birthday Cake, #10168 - Summation of Four Primes, #10169 - Urn-ball Probabilities !, #10170 - The Hotel with Infinite Rooms, #10176 - Ocean Deep ! - Make it shallow !!, #10179 - Irreducable Basic Fractions, #10182 - Bee Maja, #10183 - How Many Fibs?, #10188 - Automated Judge Script, #10190 - Divide, But Not Quite Conquer!, #10191 - Longest Nap, #10192 - Vacation, #10196 - Check The Check, #10197 - Learning Portuguese, #10199 - Tourist Guide, #10200 - Prime Time, #10205 - Stack 'em Up, #10212 - The Last Non-zero Digit., #10213 - How Many Pieces of Land ?, #10219 - Find the ways !, #10221 - Satellites, #10223 - How many nodes ?, #10229 - Modular Fibonacci, #10235 - Simply Emirp, #10238 - Throw the Dice, #10242 - Fourth Point !!, #10245 - The Closest Pair Problem, #10250 - The Other Two Trees, #10258 - Contest Scoreboard, #10262 - Suffidromes, #10267 - Graphical Editor, #10269 - Adventure of Super Mario, #10278 - Fire Station, #10281 - Average Speed, #10285 - Longest Run on a Snowboard, #10286 - Trouble with a Pentagon, #10295 - Hay Points, #10297 - Beavergnaw, #10301 - Rings and Glue, #10303 - How Many Trees?, #10304 - Optimal Binary Search Tree, #10305 - Ordering Tasks, #10315 - Poker Hands, #10324 - Zeros and Ones, #10330 - Power Transmission, #10347 - Medians, #10361 - Automatic Poetry, #10369 - Arctic Network, #10375 - Choose and divide, #10392 - Factoring Large Numbers, #10394 - Twin Primes, #10397 - Connect the Campus, #10404 - Bachet's Game, #10407 - Simple division, #10417 - Gift Exchanging, #10450 - World Cup Noise, #10465 - Homer Simpson, #10473 - Simple Base Conversion, #10474 - Where is the Marble?, #10479 - Then Hendrie Sequence, #10487 - Closest Sums, #10489 - Boxes of Chocolates, #10491 - Cows and Cars, #10499 - The Land of Justice, #10502 - Counting Rectangles, #10508 - Word Morphing, #10509 - R U Kidding Mr. Feynman?, #10533 - Digit Primes, #10534 - Wavio Sequence, #10550 - Combination Lock, #10557 - XYZZY, #10566 - Crossed Ladders, #10573 - Geometry Paradox, #10579 - Fibonacci Numbers, #10583 - Ubiquitous Religions, #10591 - Happy Number, #10594 - Data Flow, #10602 - Editor Nottoobad, #10603 - Fill, #10610 - Gopher and Hawks, #10611 - The Playboy Chimp, #10618 - Tango Tango Insurrection, #10622 - Perfect P-th Powers, #10633 - Rare Easy Problem, #10642 - Can You Solve It?, #10651 - Pebble Solitaire, #10673 - Play with Floor and Ceil, #10678 - The Grazing Cow, #10680 - LCM, #10684 - The jackpot, #10699 - Count the factors, #10700 - Camel trading, #10701 - Pre, in and post, #10717 - Mint, #10739 - String to Palindrome, #10763 - Foreign Exchange, #10773 - Back to Intermediate Math, #10784 - Diagonal, #10789 - Prime Frequency, #10790 - How Many Points Of Intersection?, #10791 - Minimum Sum LCM, #10798 - Be wary of Roses, #10801 - Lift Hopping, #10820 - Send a Table, #10838 - The Pawn Chess, #10879 - Code Refactoring, #10891 - Game of Sum, #10900 - So you want to be a 2n-aire?, #10908 - Largest Square, #10910 - Marks Distribution, #10918 - Tri Tiling, #10926 - How Many Dependencies?, #10931 - Parity, #10945 - Mother Bear, #10946 - You want what filled?, #10954 - Add All, #10970 - Big Chocolate, #10986 - Sending email, #11003 - Boxes, #11005 - Cheapest Base, #11040 - Add bricks in the wall, #11044 - Searching for Nessy, #11045 - My T-shirt suits me, #11057 - Exact Sum, #11108 - Tautology, #11110 - Equidivisions, #11111 - Generalized Matrioshkas, #11121 - Base -2, #11137 - Ingenuous Cubrency, #11150 - Cola, #11152 - Colourful Flowers, #11168 - Airport, #11181 - Probability|Given, #11202 - The least possible effort, #11203 - Can you decide it for ME?, #11205 - The broken pedometer, #11223 - O: dah dah dah!, #11244 - Counting Stars, #11292 - Dragon of Loowater, #11309 - Counting Chaos, #11310 - Delivery Debacle, #11313 - Gourmet Games, #11403 - Binary Multiplication, #11407 - Squares, #11412 - Dig the Holes, #11420 - Chest of Drawers, #11428 - Cubes, #11437 - Triangle Fun, #11448 - Who said crisis?, #11450 - Wedding shopping, #11452 - Dancing the Cheeky-Cheeky, #11455 - Behold my quadrangle, #11458 - Hot Spot, #11463 - Commandos, #11500 - Vampires, #11503 - Virtual Friends, #11506 - Angry Programmer, #11507 - Bender B. Rodríguez Problem, #11508 - Life on Mars?, #11515 - Cranes, #11518 - Dominos 2, #11520 - Fill the Square, #11530 - SMS Typing, #11541 - Decoding, #11554 - Hapless Hedonism, #11556 - Best Compression Ever, #11560 - Fixing the Bugs, #11646 - Athletics Track, #11700 - Pipes, #11703 - sqrt log sin, #11715 - Car, #11749 - Poor Trade Advisor, #11843 - Guessing Game, #11849 - CD, #11850 - Alaska, #11854 - Egypt

MIT - OpenCourseWare

2011-06-22T21:56:00.000+03:00

After a long break, I'm back here with a well-known website for college students. Massachusetts Institute of Technology OpenCourseWare. The website is a compilation of MIT Course Materials. It includes nearly all the MIT courses taught. If you need some real-good video lectures about a topic, you can check OCW and have fun!

The reason why I chose this is about algorithms (as the blog name implies). It is really easy to understand the lectures. Actually, it is a good starting point for people with algorithms enthusiasm.

The Introduction to Algorithms course is invaluable with its full content (video-audio lectures, subtitles, assignments, their solutions and exams with solutions). Course topics include sorting, search trees, heaps, hashing, divide-and-conquer, dynamic programming, amortized analysis, graph algorithms, shortest paths, network flow, computational geometry, number-theoretic algorithms, polynomial and matrix calculations, caching, and parallel computing and their analysis.

I definitely advise you to check the lectures, if you are not familiar with the topics. They are very clear and informative.

MIT OCW - Introduction to Algorithms

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/

One Problem A Day

2011-01-15T02:12:00.002+02:00

After making you familiar with online judges (spoj, topcoder and uva), it is a blog's turn. It is the first blog I introduce. (To be honest, it is my inspiration for this blog.)

Site name is really meaningful but let me go over the blog.
It is a blog created by Sabbir Yousuf Sanny. He solves one problem a day, describes his solution and shares the solution code. He started with some general problems taken from Uva, TopCoder and SPOJ. He continued with TopCoder SRMs and SWERC - Southwestern European Regional Programming Contest 2010 problems. Although he can not share problems on daily basis anymore, it will be very helpful to follow.

Especially after trying to solve the problem, you will enjoy having a look at his solution. He writes everything about the problem including alternative solutions, difficulty level, the detailed algorithm, his first approach etc.

At first look, I decided to be a follower of this blog. What about you?

One Problem A Day

http://one-problem-a-day.blogspot.com/

Uva Online Judge

2011-01-14T03:56:00.003+02:00

Another Online Judge.

Why are they important?
I think, experience and practice is really important in this area of science as it is in all the rest.
Vasyl Biletsky, gold prize winner, ACM World Finals 2009, thinks so. When I asked him about the most important part of his education, he replied immediately: "Practice, Start with easy questions and continue with harder ones."

Universidad de Valladolid is the owner. Uva Online Judge is different from the other judges because it provides problem sets in groups:

Problem Set Volumes
Random problems. Total submissions, succesful submissions, total users, successful users statistics for each problem can be seen.

Contest Volumes
Problems from different contests. Same statistical information is shown. Best place to prepare for the contest that you want to join.

Prominent Problemsetters
Problems set by 23 diferent problemsetters. If you are a fan of one of them, you'll love it.

ACM-ICPC World Finals
1990-2000 ACM ICPC World Finals Problems.

Programming Challenges (Skiena&Revilla)
Challenges. 14 Chapters.

AOAPC I: Beginning Algorithms Contests(Rujia Lui)
If you are a newbie, then here is for you. Volumes are:
Volume 0. Getting Started
Volume 1. Elementary Problem Solving
Volume 2. Data Structures
Volume 3. Brute Force
Volume 4. Algorithm Design
Volume 5. Dynamic Programming
Volume 6. Mathematical Concepts and Methods
Volume 7. Graph Algorithms and Implementation Techniques

Competitive Programming: Increasing the Lower Bound of Programming Contests (Steven & Felix Halim)
Chapter 1. Introduction
Chapter 2. Data Structures and Libraries
Chapter 3. Problem Solving Paradigms
Chapter 4. Graph
Chapter 5. Mathematics
Chapter 6. String Processing
Chapter 7. (Computational) Geometry

In their own words:

"Here you will find hundreds of problems. They are like the ones used during programming contests, and are available in HTML and PDF formats. You can submit your sources in a variety of languages, trying to solve any of the problems available in our database."

Uva Online Judge
http://uva.onlinejudge.org/

TC - TopCoder

2011-01-12T20:08:00.011+02:00

TopCoder is another nice and really fascinating website founded by Jack Hughes (founder of Topcoder, Inc.). TopCoder.com is a contest site. You can compete in several different competetions such as Algorithms, Design, Development and two other called "marathon matches" and "studio" competitions. In these competitions, you can earn money. You can even make a living from this site.
Topcoder is famous for their SRMs. Single Round Matches are held every week. You are given 75 minutes to solve 3 questions according to your level. After solving, you can have a look at other solutions submitted. If you wish, you provide some test cases, If the code fails for your test case, you gain extra points. Finally, system tests the solutions. According to the points you collect from SRMs, you are classified as a Red, Green, Yellow, .. member.
Topcoder also have partners that desire to hire talented people from this site. (Facebook, Paypal, Alcatel, Nasa etc.). They care about SRMs the most. If you do well, you can get hired by facebook!
According to rankings change, you can be selected as the Coder of The Month. It is an honor to be selected.

One final note: There are useful algorithm tutorials submitted by members. They help a lot!

To learn, have fun and practice:
Topcoder
http://www.topcoder.com

SPOJ - Sphere Online Judge

2011-01-11T14:12:00.002+02:00

First of all, an Online Judge is a system that tests your programs with different inputs and checks whether the outputs of your program are true. Online Judges generally used for programming contests, however you can use some of them for practice.
SPOJ is a popular Online Judge System. It has ~90000 registered users, ~8000 problems and you can use ~40 programming languages. You can discuss the algorithms below the problem-texts and in the forum with other members.
I am sure if you are interested in algorithmic problem solving, then you will enjoy it!

Supported Languages:

C++ C++ (g++ 4.0.0-8)
C C (gcc 4.3.2)
PAS Pascal (fpc 2.2.4)
C++ C++ (g++ 4.3.2)
JAVA Java (JavaSE 6)
PYTH Python (python 2.5)
C99 C99 strict (gcc 4.3.2)
PERL Perl (perl 5.12.1)
C# C# (gmcs 2.0.1)
RUBY Ruby (ruby 1.9.0)
HASK Haskell (ghc 6.10.4)
BF Brainf**k (bff 1.0.3.1)
PYTH Python 3 (python 3.1.2)
PAS Pascal (gpc 20070904)
PHP PHP (php 5.2.6)
CAML Ocaml (ocamlopt 3.10.2)
ADA ADA 95 (gnat 4.3.2)
BASH Bash (bash-4.0.37)
LISP Common Lisp (clisp 2.44.1)
LISP Common Lisp (sbcl 1.0.18)
D D (gdc 4.1.3)
LUA Lua (luac 5.1.3)
ASM Assembler (nasm 2.03.01)
SCM Scheme (guile 1.8.5)
JAR JAR (JavaSE 6)
FORT Fortran 95 (gfortran 4.3.2)
GO Go (gc 2010-07-14)
PIKE Pike (pike 7.6.112)
ERL Erlang (erl 5.6.3)
SCAL Scala (scala 2.8.0)
PRLG Prolog (swipl 5.6.58)
WSPC Whitespace (wspace 0.3)
ICON Icon (iconc 9.4.3)
TCL Tcl (tclsh 8.5.3)
F# F# (fsharp 2.0.0)
NICE Nice (nicec 0.9.6)
NEM Nemerle (ncc 0.9.3)
SCM Scheme (stalin 0.11)
ICK Intercal (ick 0.28-4)
ST Smalltalk (gst 3.0.3)
JS JavaScript (rhino 1.7R1-2)
CLOJ Clojure (clojure 1.1.0)
CLPS Clips (clips 6.24)
PERL

44 programming languages.

BTW, you can not use some languages for some problems.

SPOJ - Sphere Online Judge
http://www.spoj.pl/

About This Blog

2011-01-11T13:47:00.000+02:00

In this blog, I want to share websites and blogs about computer science -especially algorithms- that will help you learn and practice. I hope, you enjoy.