# Archives: 2015

# This is a test post!

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Rotated Square is a great problem to tackle if you want practice implementing and manipulating 2D arrays.

Here’s a problem I had in my early UVa days: I attempted to access the online judge using google chrome, but was met with this:

UVa 10920 Spiral Tap gave me quite a bit of grief. What appeared to be a simple simulation pproblem resulted in several TL submissions and many hours of banging my head against my desk before I could find a fast enough solution. Thus my new philsophy: “The more bruises on your head, the more progress you’re making”.

I really liked UVa 11581 Grid Successors because it is a perfect example of the good things that can happen if you don’t let the problem statement scare you.

I did not think that UVa 10258: Contest Scoreboard was a well-written problem. The problem statement did not specify the expected behavior well. I imagine this problem was the subject of many clarification requests when it was used in competition. Then again, I probably just need to practice reading problem statements carefully.

I thought UVa 10264: The Most Potent Corner was a fun problem. Short problem description: Given the weights of all of the corners of an n-dimensional unit cube (1 < n < 15), print the maximum sum of the “potencies” of two neighboring corners.

UVa 11933: Splitting Numbers problem summary: Given a number n, print out a and b, where a is the number constructed from every other set bit of n and b is constructed from the other half of the set bits. This problem is simple to implement, but in my case I screwed the implementation up and made things a lot harder for myself.

UVa 11988: Broken Keyboard is a very rare linked list problem.

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.

UVa 12086: Potentiometers is a classic Fenwick Tree problem.