Programming Exercises of CP4 Book 1

THE EASY PROBLEMS

I/O + Sequences Only

1. Entry Level: Kattis - hello ✅
2. UVa 10071 - Back to High School ✅
3. UVa 11614 - Etruscan Warriors ✅
4. Kattis - r2 ✅

Repetition Only

1. Entry Level: Kattis - timeloop ✅
2. UVa 01124 - Celebrity Jeopardy ✅
3. UVa 11044 - Searching for Nessy
4. Kattis - different

Selection Only

1. Entry Level: Kattis - moscowdream
2. Kattis - isithalloween
3. Kattis - onechicken
4. Kattis - quadrant

Multiple Test Cases + Selection

1. Entry Level: Kattis - oddities
2. UVa 11172 - Relational Operators
3. UVa 12372 - Packing for Holiday
4. Kattis - helpaphd

Control Flow

1. Entry Level: Kattis - statistics
2. UVa 11764 - Jumping Mario
3. UVa 12279 - Emoogle Balance
4. Kattis - oddgnome

Function

1. Entry Level: Kattis - mia
2. UVa 10424 - Love Calculator
3. UVa 11332 - Summing Digits
4. Kattis - filip

1D Array Manipulation, Easier

1. Entry Level: Kattis - lostlineup
2. UVa 11679 - Sub-prime
3. UVa 12015 - Google is Feeling Lucky
4. Kattis - acm

Easy

1. Entry Level: Kattis - hissingmicrophone
2. UVa 12658 - Character Recognition
3. UVa 12696 - Cabin Baggage
4. Kattis - pokerhand

Still Easy

1. Entry Level: Kattis - bubbletea
2. UVa 11559 - Event Planning
3. UVa 11683 - Laser Sculpture
4. Kattis - bossbattle

Medium

1. Entry Level: Kattis - basicprogramming1
2. UVa 12157 - Tariff Plan
3. UVa 12643 - Tennis Rounds
4. Kattis - battlesimulation

---

THE AD HOC PROBLEMS

Game (Card)

1. Entry Level: UVa 10646 - What is the Card?
2. UVa 12247 - Jollo
3. Kattis - bela
4. Kattis - memorymatch

Game (Chess)

1. Entry Level: UVa 00278 - Chess
2. UVa 00696 - How Many Knights
3. Kattis - empleh
4. Kattis - helpme

Game (Others), Easier

1. Entry Level: UVa 10189 - Minesweeper
2. UVa 00947 - Master Mind Helper
3. Kattis - connectthedots
4. Kattis - gamerank

Interesting Real Life Problems, Harder

1. Entry Level: UVa 00706 - LC-Display
2. UVa 11279 - Keyboard Comparison
3. Kattis - creditcard
4. Kattis - workout

Time, Easier

1. Entry Level: Kattis - marswindow
2. UVa 00579 - Clock Hands
3. UVa 12148 - Electricity
4. Kattis - friday

Time, Harder

1. Entry Level: Kattis - timezones
2. UVa 10942 - Can of Beans
3. UVa 11947 - Cancer or Scorpio
4. Kattis - birthdayboy

Roman Numerals

1. Entry Level: UVa 00759 - The Return of the Roman Empire
2. UVa 12397 - Roman Numerals
3. Kattis - rimski
4. Kattis - romanholidays

Cipher/Encode/Encrypt/Decode/Decrypt, Easier

1. Entry Level: UVa 13145 - Wuymul Wixcha
2. UVa 11278 - One-Handed Typist
3. UVa 12896 - Mobile SMS
4. Kattis - t9spelling

Cipher/Encode/Encrypt/Decode/Decrypt, Medium

1. Entry Level: Kattis - secretmessage
2. UVa 00245 - Uncompress
3. UVa 11787 - Numeral Hieroglyphs
4. Kattis - anewalphabet

Input Parsing (Iterative)

1. Entry Level: UVa 11878 - Homework Checker
2. UVa 00397 - Equation Elation
3. UVa 01200 - A DP Problem
4. Kattis - timebomb

Output Formatting, Easier

1. Entry Level: UVa 00488 - Triangle Wave
2. UVa 10500 - Robot maps
3. UVa 12364 - In Braille
4. Kattis - musicalnotation

Time Waster Problems, Easier

1. Entry Level: Kattis - asciiaddition
2. UVa 11638 - Temperature Monitoring
3. UVa 12608 - Garbage Collection
4. Kattis - pachydermpeanutpacking

Time Waster Problems, Harder

1. Entry Level: UVa 10188 - Automated Judge Script
2. UVa 00405 - Message Routing
3. Kattis - froggie
4. Kattis - windows

---

LINEAR DS WITH BUILT-IN LIBRARIES

1D Array Manipulation, Medium

1. Entry Level: Kattis - jollyjumpers
2. UVa 12150 - Pole Position
3. UVa 12356 - Army Buddies
4. Kattis - greedilyincreasing

1D Array Manipulation, Harder

1. Entry Level: UVa 10978 - Let’s Play Magic
2. UVa 11222 - Only I did it
3. Kattis - mastermind
4. Kattis - pivot

2D Array Manipulation, Easier

1. Entry Level: Kattis - epigdanceo↵
2. UVa 11581 - Grid Successors
3. UVa 12667 - Last Blood
4. Kattis - nineknights

2D Array Manipulation, Harder

1. Entry Level: Kattis - 2048
2. UVa 00466 - Mirror Mirror
3. UVa 11360 - Have Fun with Matrices
4. Kattis - flagquiz

Sorting, Easier

1. Entry Level: Kattis - basicprogramming2
2. UVa 12541 - Birthdates
3. UVa 12709 - Falling Ants
4. Kattis - mjehuric

Sorting, Harder

1. Entry Level: Kattis - sortofsorting
2. UVa 01610 - Party Games
3. UVa 11321 - Sort Sort and Sort
4. Kattis - dyslectionary

Special Sorting Problems

1. Entry Level: UVa 11462 - Age Sort
2. UVa 11495 - Bubbles and Buckets
3. Kattis - bread
4. Kattis - magicsequence

Bit Manipulation

1. Entry Level: UVa 11933 - Splitting Numbers
2. UVa 12571 - Brother & Sisters
3. Kattis - deathstar
4. Kattis - snapperhard

Big Integer26

1. Entry Level: UVa 10925 - Krakovia
2. UVa 10523 - Very Easy
3. Kattis - primaryarithmetic
4. Kattis - wizardofodds

Stack

1. Entry Level: Kattis - evenup
2. UVa 00514 - Rails
3. UVa 01062 - Containers
4. Kattis - restaurant

Special Stack-based Problems

1. Entry Level: UVa 00551 - Nesting a Bunch of...
2. UVa 00673 - Parentheses Balance
3. Kattis - bungeebuilder
4. Kattis - delimitersoup

List/Queue/Deque

1. Entry Level: Kattis - joinstrings
2. UVa 11988 - Broken Keyboard ...
3. UVa 10172 - The Lonesome Cargo ...
4. Kattis - teque

---

NON-LINEAR DS WITH BUILD-IN LIBRARIES

Hash Table (set)

1. Entry Level: Kattis - cd
2. UVa 10887 - Concatenation of ...
3. UVa 12049 - Just Prune The List
4. Kattis - greetingcard

Hash Table (map), Easier

1. Entry Level: Kattis - recount
2. UVa 00902 - Password Search
3. UVa 11348 - Exhibition
4. Kattis - competitivearcadebasketball

Hash Table (map), Harder

1. Entry Level: Kattis - conversationlog
2. UVa 00417 - Word Index
3. UVa 10145 - Lock Manager
4. Kattis - awkwardparty

Balanced BST (set)

1. Entry Level: UVa 10815 - Andy’s First Dictionary
2. UVa 11136 - Hoax or what
3. Kattis - bst
4. Kattis - compoundwords

Balanced BST (map)

1. Entry Level: Kattis - doctorkattis
2. UVa 10138 - CDVII
3. UVa 11308 - Bankrupt Baker
4. Kattis - administrativeproblems

Order Statistics Tree

1. Entry Level: UVa 10909 - Lucky Number
2. Kattis - babynames
3. Kattis - continuousmedian
4. Kattis - cookieselection

---

DS WITH OUR OWN LIBRARIES

Graph Data Structures Problems

1. Entry Level: UVa 11991 - Easy Problem from ...
2. UVa 10895 - Matrix Transpose
3. Kattis - abinitio
4. Kattis - traveltheskies

Union-Find Disjoint Sets

1. Entry Level: Kattis - unionfind
2. UVa 01197 - The Suspects
3. UVa 01329 - Corporative Network
4. Kattis - control

Tree-related Data Structures

1. Entry Level: Kattis - fenwick
2. UVa 11402 - Ahoy, Pirates
3. UVa 11423 - Cache Simulator
4. Kattis - supercomputer

---

COMPLETE SEARCH

Pre-calculate-able

1. Entry Level: UVa 00750 - 8 Queens Chess ...
2. UVa 10128 - Queue
3. Kattis - cardtrick2
4. Kattis - sgcoin

Iterative (Two Nested Loops)

1. Entry Level: Kattis - pet
2. UVa 00592 - Island of Logic
3. UVa 01588 - Kickdown
4. Kattis - blackfriday

Iterative (Three or More Nested Loops, Easier)

1. Entry Level: UVa 00441 - Lotto
2. UVa 12515 - Movie Police
3. Kattis - cudoviste
4. Kattis - npuzzle

Iterative (Three or More Nested Loops, Harder)

1. Entry Level: UVa 00386 - Perfect Cubes
2. UVa 11236 - Grocery Store
3. Kattis - calculatingdartscores
4. Kattis - tautology

Iterative (Permutation)

1. Entry Level: UVa 11742 - Social Constraints
2. UVa 00234 - Switching Channels
3. Kattis - dancerecital
4. Kattis - dreamer

Iterative (Combination)

1. Entry Level: UVa 00639 - Don’t Get Rooked
2. UVa 11659 - Informants
3. Kattis - geppetto
4. Kattis - squaredeal

Try All Possible Answer(s)

1. Entry Level: Kattis - flexible
2. UVa 00188 - Perfect Hash
3. UVa 00725 - Division
4. Kattis - islands

Mathematical Simulation (Complete Search), Easier

1. Entry Level: Kattis - easiest
2. UVa 00382 - Perfection
3. UVa 10346 - Peter’s Smoke
4. Kattis - trollhunt

Mathematical Simulation (Complete Search), Harder

1. Entry Level: UVa 00616 - Coconuts, Revisited
2. UVa 11254 - Consecutive Integers
3. Kattis - crackingrsa
4. Kattis - falling

Josephus Problem

1. Entry Level: UVa 00151 - Power Crisis
2. UVa 11351 - Last Man Standing
3. Kattis - eenymeeny
4. Kattis - toys

Recursive Backtracking (Easier)

1. Entry Level: UVa 10344 - 23 Out of 5
2. UVa 12840 - The Archery Puzzle
3. Kattis - goodmorning
4. Kattis - paintings

Recursive Backtracking (Harder)

1. Entry Level: UVa 00208 - Firetruck
2. UVa 00307 - Sticks
3. Kattis - dobra
4. Kattis - pagelayout

---

DIVIDE AND CONQUER

Binary Search

1. Entry Level: UVa 11057 - Exact Sum
2. UVa 12965 - Angry Birds
3. Kattis - firefly
4. Kattis - outofsorts

Bisection Method and BSTA (Easier)

1. Entry Level: Kattis - carefulascent
2. UVa 12190 - Electric Bill
3. UVa 13142 - Destroy the Moon ...
4. Kattis - monk

Ternary Search and Others

1. Entry Level: UVa 00183 - Bit Maps
2. UVa 10385 - Duathlon
3. Kattis - a1paper
4. Kattis - ceiling

---

GREEDY

Classical

1. Entry Level: UVa 10020 - Minimal Coverage
2. UVa 11264 - Coin Collector
3. Kattis - classrooms
4. Kattis - squarepegs

Involving Sorting (Or The Input Is Already Sorted), Easier

1. Entry Level: UVa 11369 - Shopaholic
2. UVa 11900 - Boiled Eggs
3. Kattis - icpcteamselection
4. Kattis - shopaholic

Involving Sorting (Or The Input Is Already Sorted), Harder

1. Entry Level: UVa 12673 - Football
2. UVa 12834 - Extreme Terror
3. Kattis - birds
4. Kattis - delivery

Involving Priority Queue

1. Entry Level: Kattis - ballotboxes
2. UVa 10954 - Add All
3. UVa 13177 - Orchestral scores
4. Kattis - canvas

Non Classical, Easier

1. Entry Level: UVa 10656 - Maximum Sum (II)
2. UVa 11520 - Fill the Square
3. Kattis - ants
4. Kattis - bank

Non Classical, Harder

1. Entry Level: UVa 11491 - Erasing and Winning
2. UVa 11583 - Alien DNA
3. Kattis - dvds
4. Kattis - stockbroker

---

DYNAMIC PROGRAMMING

Max 1D/2D Range Sum

1. Entry Level: UVa 10684 - The Jackpot
2. UVa 10755 - Garbage Heap
3. Kattis - commercials
4. Kattis - prozor

Longest Increasing Subsequence (LIS)

1. Entry Level: UVa 00481 - What Goes Up?
2. UVa 10534 - Wavio Sequence
3. Kattis - increasingsubsequence
4. Kattis - trainsorting

0-1 Knapsack (Subset-Sum)

1. Entry Level: UVa 10130 - SuperSale
2. UVa 11566 - Let’s Yum Cha
3. Kattis - knapsack
4. Kattis - orders

Coin-Change (CC)

1. Entry Level: UVa 00674 - Coin Change
2. UVa 11259 - Coin Changing Again
3. Kattis - canonical
4. Kattis - exactchange2

Traveling-Salesman-Problem (TSP)

1. Entry Level: Kattis - beepers
2. UVa 00216 - Getting in Line
3. UVa 11795 - Mega Man’s Mission
4. Kattis - bustour

---

GRAPH TRAVERSAL

Finding Connected Components

1. Entry Level: Kattis - wheresmyinternet
2. UVa 00459 - Graph Connectivity
3. UVa 11906 - Knight in a War Grid
4. Kattis - dominoes2

Flood Fill, Easier

1. Entry Level: UVa 00572 - Oil Deposits
2. UVa 11953 - Battleships
3. Kattis - amoebas
4. Kattis - gold

Flood Fill, Harder

1. Entry Level: UVa 11094 - Continents
2. UVa 01103 - Ancient Messages
3. Kattis - 10kindsofpeople
4. Kattis - coast

Topological Sort

1. Entry Level: Kattis - builddeps
2. UVa 00200 - Rare Order
3. UVa 11060 - Beverages
4. Kattis - brexit

Bipartite or Cycle Check

1. Entry Level: Kattis - runningmom
2. UVa 10004 - Bicoloring
3. UVa 10505 - Montesco vs Capuleto
4. Kattis - hoppers

Finding Articulation Points/Bridges

1. UVa 00315 - Network
2. UVa 12363 - Hedge Mazes
3. Kattis - birthday
4. Kattis - intercept

Finding Strongly Connected Components

1. Entry Level: UVa 11838 - Come and Go
2. UVa 00247 - Calling Circles
3. Kattis - cantinaofbabel
4. Kattis - dominos

Ad Hoc Graph Traversal

1. Entry Level: UVa 12376 - As Long as I Learn, I Live
2. UVa 12442 - Forwarding Emails
3. Kattis - faultyrobot
4. Kattis - promotions

---

MINIMUM SPANNING TREE (MST)

Standard

1. Entry Level: Kattis - islandhopping
2. UVa 11228 - Transportation ...
3. UVa 11631 - Dark Roads
4. Kattis - cats

Variants

1. Entry Level: UVa 10048 - Audiophobia
2. UVa 01265 - Tour Belt
3. Kattis - millionairemadness
4. Kattis - muddyhike

---

SINGLE-SOURCE SHORTEST PATHS (SSSP)

On Unweighted Graph: BFS, Easier

1. Entry Level: UVa 00336 - A Node Too Far
2. UVa 10653 - Bombs; NO they ...
3. Kattis - buttonbashing
4. Kattis - grid

On Unweighted Graph: BFS, Harder

1. Entry Level: Kattis - lost
2. UVa 11352 - Crazy King
3. UVa 12826 - Incomplete Chessboard
4. Kattis - mallmania

Knight Moves

1. Entry Level: UVa 00439 - Knight Moves
2. UVa 10426 - Knights’ Nightmare
3. Kattis - grasshopper
4. Kattis - knightjump

On Weighted Graph: Dijkstra’s, Easier

1. Entry Level: Kattis - shortestpath1
2. UVa 01112 - Mice and Maze
3. UVa 10986 - Sending email
4. Kattis - flowerytrails

On Weighted Graph: Dijkstra’s, Harder

1. Entry Level: Kattis - visualgo
2. UVa 00589 - Pushing Boxes
3. UVa 12047 - Highest Paid Toll
4. Kattis - blockcrusher

On Small Graph (with Negative Cycle): Bellman-Ford

1. Entry Level: UVa 00558 - Wormholes
2. UVa 10449 - Trac
3. Kattis - hauntedgraveyard
4. Kattis - xyzzy

---

ALL-PAIRS SHORTEST PATHS (APSP)

Floyd-Warshall Standard Application

1. Entry Level: UVa 00821 - Page Hopping
2. UVa 10354 - Avoiding Your Boss
3. Kattis - allpairspath
4. Kattis - importspaghetti

Variants

1. Entry Level: UVa 01056 - Degrees of ...
2. UVa 10342 - Always Late
3. Kattis - arbitrage
4. Kattis - kastenlauf

---

SPECIAL GRAPHS

Shortest/Longest Paths on DAG

1. Entry Level: Kattis - mravi
2. UVa 00452 - Project Scheduling
3. UVa 10259 - Hippity Hopscotch
4. Kattis - 246greaaat

DP, Counting Paths in DAG, Easier

1. Entry Level: UVa 00825 - Walking on the Safe Side
2. UVa 11957 - Checkers
3. Kattis - robotsonagrid
4. Kattis - runningsteps

Converting General Graph to DAG

1. Entry Level: UVa 00590 - Always on the Run
2. UVa 12875 - Concert Tour
3. Kattis - cardmagic
4. Kattis - maximizingwinnings

Tree

1. Entry Level: UVa 00536 - Tree Recovery
2. UVa 12347 - Binary Search Tree
3. Kattis - adjoin
4. Kattis - flight