1007. Code words.
Simple ad-hoc problem.
1008. Image encoding.
Problem is easily solvable using BFS. The only trick is that you problem statement doesn't really specify which (one of two) input format is going to be used... :)
1009. K-based numbers.
1012. K-based numbers v.2.
1013. K-based number v.3.
The three upper mentioned problems are solved using the exact same DP: dp[i][j] - number of valid K-based numbers of length i and last digit j. The only difference is the latter two have to be implemented using long arithmetic or java's BigInteger class.
1014. The product of Digits.
Simple math problem. There should be formula for it, but I solved using iterations, because given input is specified up to two decimal points...
1015. Test the Difference!
The problem requires to be able to generate all possible rotated states of the die and then determine dice are same. Pretty straightforward.
1017. The staircase.
Classical DP problem. Asks to find number of ways to represent a given integer N as an increasing sum of at least two integers. You have to use long arithmetics again or BigInteger, since N can be up to 500.
Showing posts with label acm. Show all posts
Showing posts with label acm. Show all posts
Monday, May 4, 2009
Sunday, May 3, 2009
Simple Case of Directed Steiner Network Problem.
3570 - Routing (acm icpc live archive).
I was amazed how beautiful and simple solution to this problem actually is. I got stuck on this problem, even though at the first sight it seems easy. Then I asked Prof Mikhail Atallah (our spiritual coach) for help and he pointed out this paper, which explains the solution to this problem and even describes an algorithm for a more general case. I was reading this paper during my flight from Indianapolis to Boston and after I understood it, I was excited to do the actual implementation :-) So, I did implement it and got AC from the first attempt.
The problem is reduced to constructing another graph and finding minimum path in it. You have to use Dijkstra's algorithm with priority queue, because number of nodes in the new graph can be up to 10,000.
I was amazed how beautiful and simple solution to this problem actually is. I got stuck on this problem, even though at the first sight it seems easy. Then I asked Prof Mikhail Atallah (our spiritual coach) for help and he pointed out this paper, which explains the solution to this problem and even describes an algorithm for a more general case. I was reading this paper during my flight from Indianapolis to Boston and after I understood it, I was excited to do the actual implementation :-) So, I did implement it and got AC from the first attempt.
The problem is reduced to constructing another graph and finding minimum path in it. You have to use Dijkstra's algorithm with priority queue, because number of nodes in the new graph can be up to 10,000.
Tuesday, April 28, 2009
Bruteforce problem
1005. Stone pile (acm.timus.ru).
Just a bruteforce problem. Generate all possible splits of the stones into two piles and select the best.
Just a bruteforce problem. Generate all possible splits of the stones into two piles and select the best.
Couple of DP problems
1018. A Binary Apple Tree (acm.timus.ru)
This was an easy DP problem. The state of the DP is the following: root of the subtree and how many edges we need, in other words dp[node][need] - is the maximum amount of apples that we can preserve if the root of our tree is at the node and we will leave "need" edges. The only tricky part of this problem is that the given input is not necessarily a rooted tree and so after reading the input you have to construct the tree properly.
1002. Phone number (acm.timus.ru)
Another simple DP problem. Let's say S[1..L] is the first L digits of the call number. Let D[L] be the minimum number of words that we can use to split S[1..L]. Obviously, D[0]=0 and D[L]=INFINITY, if we cannot split S[1..L]. In order to compute D[L] we look at S[L..L], S[L-1..L], S[L-2..L], .. up to S[L-49..L] (because there are no words of length more than 50) and check if there are words that match these substrings. For every word matched we try to improve our D[L] in the following way D[L]=min(D[L],D[J]+1), where J=L-(length_of_currently_matched_word). You also have to figure out a fast way to check whether there exists a word that matches certain S[I..J]. This can be done by either creating a c++ map that associates a certain digit sequence with a word or coding your own hashing in pascal.
Also in order to construct the answer we need remember for each L the value of J that D[L] archives the minimum.
This was an easy DP problem. The state of the DP is the following: root of the subtree and how many edges we need, in other words dp[node][need] - is the maximum amount of apples that we can preserve if the root of our tree is at the node and we will leave "need" edges. The only tricky part of this problem is that the given input is not necessarily a rooted tree and so after reading the input you have to construct the tree properly.
1002. Phone number (acm.timus.ru)
Another simple DP problem. Let's say S[1..L] is the first L digits of the call number. Let D[L] be the minimum number of words that we can use to split S[1..L]. Obviously, D[0]=0 and D[L]=INFINITY, if we cannot split S[1..L]. In order to compute D[L] we look at S[L..L], S[L-1..L], S[L-2..L], .. up to S[L-49..L] (because there are no words of length more than 50) and check if there are words that match these substrings. For every word matched we try to improve our D[L] in the following way D[L]=min(D[L],D[J]+1), where J=L-(length_of_currently_matched_word). You also have to figure out a fast way to check whether there exists a word that matches certain S[I..J]. This can be done by either creating a c++ map that associates a certain digit sequence with a word or coding your own hashing in pascal.
Also in order to construct the answer we need remember for each L the value of J that D[L] archives the minimum.
Monday, April 27, 2009
First AC-s
Welcome everyone!
I plan on posting here most of the ideas, approaches or hints to the problems that I will solve in near future on any online judge.
Here is the first and problem that I solved today:
1000. A+B Problem (acm.timus.ru).
Basically you have to find sum of two integers. Luckily those integers aren't negative, but unluckily they might not fit into 32-bit variables. So, you should recall your school method for adding two numbers or you can use java's nice BigInteger class(No cheating - I did the former:) .
1001. Reverse Root (acm.timus.ru).
Just do what the problem asks. Beware of the reverse order though...
I plan on posting here most of the ideas, approaches or hints to the problems that I will solve in near future on any online judge.
Here is the first and problem that I solved today:
1000. A+B Problem (acm.timus.ru).
Basically you have to find sum of two integers. Luckily those integers aren't negative, but unluckily they might not fit into 32-bit variables. So, you should recall your school method for adding two numbers or you can use java's nice BigInteger class(No cheating - I did the former:) .
1001. Reverse Root (acm.timus.ru).
Just do what the problem asks. Beware of the reverse order though...
Subscribe to:
Posts (Atom)
