Archives: July 2015
UVa 10226: Hardwood Species abridged problem statement: Given a list of species of trees, print out each species followed by the percentage of the total tree population it represents. Each species should be on a new line and percentages should be printed to four decimal places.
UVa 11286: Conformity is another problem that can be solved in a simple manner using a map.
I found UVa 11926: Multitasking to be a tricky problem to get right.
UVa 11136: Hoax or what is a simulation problem using multisets.
UVa 11572: Unique Snowflakes problem description: Given a list of snowflakes (integers), print the length of the longest sublist in which all of the snowflakes are unique.
UVa 11849: CD is
an easy problem, as long as you use a set.
UVa 1203: Argus was a sort of poorly written problem, and I thought it was a lot harder than it actually turned out to be.
I solved UVa 978: Lemmings Battle! with a multiset. A multiset has the same underlying implementation as a regular STL set (BST), but it can store multiple copies of the same value, which makes it perfect for modelling these lemmings.
UVa 10895: Matrix Transpose simplified problem statement: Given a matrix, print its transpose.
The correct way to do UVa 10954: Add All is to use a priority queue.
UVa 11235: Frequent values simplified problem statement: You are given an array of integers and a number of queries. Each query is in the form of two positive integers i and j, and your program must print the number of occurances of the most frequently occuring value in the array between indicies i and j, inclusive.
UVa 11991: Easy Problem from Rujia Liu? simplified problem statement: You are given an array of integers and asked to answer a series of queries. Each query is of the form: “What is the index in the array of the ith occurance of the number j?”
UVa 11995: I Can Guess the Data Structure! simplified problem statement: Given a sequence of push/pop operations, state whether the operations are valid for a queue, stack, priority queue, or some combination thereof (including none thereof).
When solving UVa 599: The Forrest for the Trees I was introduced to a new data structure: the UFDS
UVa 10507: Waking up brain simplified problem statement: There are several areas of the brain, each of which is connected to other areas of the brain. All the regions but 3 are “asleep”, but if a region is connected to 3 awake regions for a year, that region wakes up. Given the connections between various parts of the brain and the 3 regions that are initially awake, determine how long the entire brain takes to wake up.
UVa 11503: Virtual Friends simplified problem statement: Several people are friending each other on social media. Every time two people become friends, print out the current size of their social network.
UVa 793: Network Connections is a good UFDS implementation practice problem.
UVa 12532: Interval Product involves a clever application of segment trees. Abridged problem statement: You are given a list of integers and a number of queries. Each query can either change one integer in the list, or ask for the sign of the product between a range of indicies. Print out a string with the answers to all the queries concatenated together.