Fibonacci numbers
If you write the sequence resulted from the description, you'll see that you have to find sum of the first n Fibonacci numbers + sum of the first (n-1) Fibonacci numbers.
Sum Fib( i ) = Fib(n+2)-1
----- i = 0...n
Use long long int and you just need to calculate the first 46 sentences of the Fibonacci numbers.
For more information about Fibonacci numbers read this :
http://en.wikipedia.org/wiki/Fibonacci_number
Monday, October 18, 2010
Sunday, October 17, 2010
11239 - Open Source - UVA
Data Structures - STL map or set - sorting
As shown in the problem description, you have to count the number of students who have signed up for each project. There are some important hints in this problem that you have to concern :
If someone has signed up for more than one project do not count him for any of them.
If someone has written his name for a project more than one time, It's OK, just count him once in that project.
Data structure I use in this problem :
map (string, set(string) ) === to save for each project which students want to attend
map (string, string) === to save this student is singed for which project previously
set (string) === to save which student has signed up and can not attend any other project, if a student want to sign up for more than one project I find the previous project he/she has signed up for and delete him/her from that list
vector (int, string) === to produce output and sort it by number of students attending each project and then alphabetically by the name of the project
As shown in the problem description, you have to count the number of students who have signed up for each project. There are some important hints in this problem that you have to concern :
If someone has signed up for more than one project do not count him for any of them.
If someone has written his name for a project more than one time, It's OK, just count him once in that project.
Data structure I use in this problem :
set (string) ===
vector (int, string) === to produce output and sort it by number of students attending each project and then alphabetically by the name of the project
10226 - Hardwood Species - UVA
Data Structures - STL map or set
In this problem you will read some tree names from input and must count the number of trees and at the end print the percentage of trees.
What can we do? We read tree names one by one, when reading a tree name, you have to increment the number of that tree counted till now, so you have to find the index of that tree to increment it. If you use linear search to find the index you will get a TLE (Time Limit Exceeded), so you have to use a binary search. using set or map data structures that have a binary search with them is appropriate. MAPs and SETs are always sorted.
I use a map data structure from string to int and each time I read a tree name I increment the counter of that tree.
map mp;
while( getline( cin, tree ), tree != "" )
{
mp[tree] ++;
total ++;
}
and at the end I print (each counter/total).
In this problem you will read some tree names from input and must count the number of trees and at the end print the percentage of trees.
What can we do? We read tree names one by one, when reading a tree name, you have to increment the number of that tree counted till now, so you have to find the index of that tree to increment it. If you use linear search to find the index you will get a TLE (Time Limit Exceeded), so you have to use a binary search. using set or map data structures that have a binary search with them is appropriate. MAPs and SETs are always sorted.
I use a map data structure from string to int and each time I read a tree name I increment the counter of that tree.
map
while( getline( cin, tree ), tree != "" )
{
mp[tree] ++;
total ++;
}
and at the end I print (each counter/total).
10928 - My Dear Neighbours - UVA
graph representation or Ad Hoc
In this problem you have to count the OUT-DEGREE of each node and find the minimum OUT-DEGREE and print nodes with the minimum OUT-DEGREE sequentially.
What you have to concern is type of input. I get input using stringstream and getline and count the neighbors of each node.
In this problem you have to count the OUT-DEGREE of each node and find the minimum OUT-DEGREE and print nodes with the minimum OUT-DEGREE sequentially.
What you have to concern is type of input. I get input using stringstream and getline and count the neighbors of each node.
599 - The Forrest for the Trees - UVA
graph search algorithm - DFS
In this problem you have to find the number of components in a graph and you have to distinguish which components are isolated vertices. Easily run DFS for each unvisited node and count the number of components, set a counter before running DFS to find the number of vertices in a component, increment it at the beginnig and if this number was 1, it is an isolated vertex.
In this problem you have to find the number of components in a graph and you have to distinguish which components are isolated vertices. Easily run DFS for each unvisited node and count the number of components, set a counter before running DFS to find the number of vertices in a component, increment it at the beginnig and if this number was 1, it is an isolated vertex.
924 - Spreading The News - UVA
graph search algorithm - BFS
In this problem you have to run BFS from a source, and find out that in the BFS-tree in which level you have the most nodes and in which level the most nodes come to BFS-tree.
I run BFS from the given source and find out the depth of each node from the source and then calculate which depth has the most nodes and what the level is.
if d[i] is the depth for node i from source then
for(int i = 0; i < n; i ++)
output[ d[i] ] ++;
find max from output and print the index of maximum as depth and output[index] as size of the maximum.
problem sample test case :
http://www.4shared.com/photo/va73oUQD/924_spreading_the_news.html
In this problem you have to run BFS from a source, and find out that in the BFS-tree in which level you have the most nodes and in which level the most nodes come to BFS-tree.
I run BFS from the given source and find out the depth of each node from the source and then calculate which depth has the most nodes and what the level is.
if d[i] is the depth for node i from source then
for(int i = 0; i < n; i ++)
output[ d[i] ] ++;
find max from output and print the index of maximum as depth and output[index] as size of the maximum.
problem sample test case :
http://www.4shared.com/photo/va73oUQD/924_spreading_the_news.html
439 - Knight Moves - UVA
graph search algorithm - BFS
In this problem you are going to find out the shortest path between two cells of a chess board for a knight. I don't know how, but you have to prove that in a 8x8 chess board if you place a knight in a cell then it can reach any cell you want. So the shortest path problem works here.
The neighbors of a cell are these cells, if the cell is (x, y):
(x+1, y+2)
(x+1, y-2)
(x-1, y+2)
(x-1, y-2)
(x+2, y+1)
(x+2, y-1)
(x-2, y+1)
(x-2, y-1)
In this problem you are going to find out the shortest path between two cells of a chess board for a knight. I don't know how, but you have to prove that in a 8x8 chess board if you place a knight in a cell then it can reach any cell you want. So the shortest path problem works here.
The neighbors of a cell are these cells, if the cell is (x, y):
(x+1, y+2)
(x+1, y-2)
(x-1, y+2)
(x-1, y-2)
(x+2, y+1)
(x+2, y-1)
(x-2, y+1)
(x-2, y-1)
Sunday, October 10, 2010
10610 - Gopher and Hawks - UVA
graph search algorithm - BFS
You are given some points in a grid and have to calculate whether you can reach a end point from a start point or not. When you leave a point to reach another point you can just run for m*60 seconds, if you run more you will disappear ;-). So "distance between pi and pk / V < m*60" must satisfy to be sure that you can go from pi to pk, in this way I create adjacency matrix and then easily run a BFS on the graph to find the shortest path from the start point to the end point.
You are given some points in a grid and have to calculate whether you can reach a end point from a start point or not. When you leave a point to reach another point you can just run for m*60 seconds, if you run more you will disappear ;-). So "distance between pi and pk / V < m*60" must satisfy to be sure that you can go from pi to pk, in this way I create adjacency matrix and then easily run a BFS on the graph to find the shortest path from the start point to the end point.
10926 - How Many Dependencies? - UVA
graph search algorithm - DFS
In this problem you have to find that if you start DFS from a node how many nodes are under this node in the DFS-tree and choose the maximum value of these for output.
Cause the input size is small and you are facing a DAG, don't think of complex algorithms to solve this problem, easily run DFS for each node and count how many nodes are invoked from this DFS and don't worry about cycles(there are no cycles in this problem). O(n^3)
data structures:
mat[101][101] = adjacency matrix
mark[101] = to mark which nodes are visited
In this problem you have to find that if you start DFS from a node how many nodes are under this node in the DFS-tree and choose the maximum value of these for output.
Cause the input size is small and you are facing a DAG, don't think of complex algorithms to solve this problem, easily run DFS for each node and count how many nodes are invoked from this DFS and don't worry about cycles(there are no cycles in this problem). O(n^3)
data structures:
mat[101][101] = adjacency matrix
mark[101] = to mark which nodes are visited
928 - Eternal Truths - UVA
graph search algorithm - BFS
According to the problem description, you have to find the shortest path between two points in a grid, 'S' & 'E'.
data structures :
triple = a structure with 3 elements( x, y, length ), 'length' is the length of the last jump that has entered this cell
grid[301][301] = an array of strings with size of more than 300 for input grid
mark[301][301][4] = a 3d array to mark and save the distance from the start cell in a jump with size of 1, 2 or 3
After I get input, I find the position of the start and end point, then set all the members of mark to -1, and then create a queue of 'triple', push start to queue and set it's length to 1, because the next jump I can do from this point is a jump with length 1.
Then in a while loop I retrieve the last triple that I have pushed to queue and continue jumping from this point to the neighbor points, before I push the new triple into the queue, I set the length of it to "1 + the current triple's length" to save that how I can continue jumping from this point.
What you have to be careful of is that you can't jump through obstacles, for example assume that you can make jumps with size of 3 at this level. S.#E but you can't reach from 'S' to 'E', so check whether there are any obstacles in your jump or not.
At the end check mark[end.first][end.second][1,2,3], any of them that is not -1 and is the smallest one is the answer otherwise the answer is 'NO'.
According to the problem description, you have to find the shortest path between two points in a grid, 'S' & 'E'.
data structures :
triple = a structure with 3 elements( x, y, length ), 'length' is the length of the last jump that has entered this cell
grid[301][301] = an array of strings with size of more than 300 for input grid
mark[301][301][4] = a 3d array to mark and save the distance from the start cell in a jump with size of 1, 2 or 3
After I get input, I find the position of the start and end point, then set all the members of mark to -1, and then create a queue of 'triple', push start to queue and set it's length to 1, because the next jump I can do from this point is a jump with length 1.
Then in a while loop I retrieve the last triple that I have pushed to queue and continue jumping from this point to the neighbor points, before I push the new triple into the queue, I set the length of it to "1 + the current triple's length" to save that how I can continue jumping from this point.
What you have to be careful of is that you can't jump through obstacles, for example assume that you can make jumps with size of 3 at this level. S.#E but you can't reach from 'S' to 'E', so check whether there are any obstacles in your jump or not.
At the end check mark[end.first][end.second][1,2,3], any of them that is not -1 and is the smallest one is the answer otherwise the answer is 'NO'.
Subscribe to:
Posts (Atom)