contest link : http://acm.hust.edu.cn/vjudge/contest/view.action?cid=103408#overview
I was gonna write an editorial anyway. Thought here would be easier and some CF users might benefit from these too. Here goes:
Problem A:
This is a dynamic programming problem. Suppose i am to find number of pattern of wall length N and i have already calculated pattern all values for x < N. Now if i place a vertical brick after any pattern of length N - 1, we get a pattern of length N. Again if i place two horizontal brick (one above another) after any pattern of length N - 2, we get a pattern of length N. It is apparent that there is no double counting.
Say dp[N] denotes the number of patterns of length N. So dp[n] = dp[n - 1] + dp[n - 2].
Base cases are for n = 1, dp[n] = 1 and for n = 2, dp[n] = 2 ; which can be calculated manually or from the given test cases. Make sure to use long long, as int will not hold the answer.
solution : http://paste.ubuntu.com/14401595/
Problem B:
This is a dynamic programming problem.
First observation is that you actually have unlimited number of each type coin. You need to make K and you have K coin of each type. So you will never run out of coin.
say dp[x][y] is the number of way to make y using first x coin. The recurrence relation is:
dp[x][y] = dp[x - 1][y] + dp[x][y - valueofXthcoin]
This means that, I have two option:
I dont take the xth coin ( dp[x - 1][y] ) to make value y.
I take the xth coin to make dp[x][y] from dp[x][y - valueofXthcoin].
I hope, you can figure out the base case here. value 0 can be made only one way.
solution : http://paste.ubuntu.com/14401682/
Problem C:
After some thinking and seeing some example, you can realize that, the solution is the LCS between the string and its reverse string. Its straightforward to get LCS of two string. Be careful of empty string.
solution : http://paste.ubuntu.com/14401762/
Problem D:
This is a bitmask dp problem. Make a "oo-" -> "--o" or "-oo" -> "o--" and recursively calculate. Here o/- can be represented by the 0/1 bit of a number, which gives a recursive dp.
solution : http://paste.ubuntu.com/14401916/
Problem E:
This here is a very good explanation :
https://www.quora.com/How-do-I-solve-Mixtures-MIXTURES-on-SPOJ
solution: http://paste.ubuntu.com/14402002/
Problem F:
Simulate stack,queue and priority queue. If it satisfies more than one DS-> "not sure". If satisfies none "impossible". Otherwise print the name of the DS.
Solution: http://paste.ubuntu.com/14402150/
Problem G:
This problem can be solved by DFS/BFS. But the intended solution (as part of DS contest), union_find AKA Disjoint_set_union. Initially every node has size 1. When combining two component x and y, say i am gonna point from x to y. so add size of x to size of y.
Solution: http://paste.ubuntu.com/14402226/
Problem H:
Standard range sum query problem with update. Read about segment tree/BIT.
Solution: http://paste.ubuntu.com/14402317/
Problem I:
Similar to range maximum query with update, the only difference is that you need to also maintain the 2nd largest number with the largest number.
Solution: http://paste.ubuntu.com/14402614/
Problem J:
This is the hardest problem of the set. This problem requires the mixture of both DP & DS. Different DS can be used depending on the approach. But i am gonna discuss the approach with stack. This problem is a great example that even such a simple DS as stack can solve tough problems.
calculate from right to left of the array. suppose i am at index x of the array and rightside of this index, all values are calculated. A Stack will maintain whoever is alive on the right. Now x will try to kill to whoever is alive on right of him ,suppose y. If x can kill y, then dp[x] = max(1 + dp[x], dp[y]). Because x requires one extra second to kill y who survived thus far (thats why 1 + dp[x]). But stable time of y, dp[y] was calculated before and may have killed many psychos, but y might have been killed before that time by x. So if y killed more psychos than 1 + dp[x] that means x have to kill extra dp[y] - (1 + dp[x]), which means time required is dp[y] - (1 + dp[x]) + (1 + dp[x]) = dp[y]. The value of dp[y] will not be needed later (as dp[x] will be atleast as large as dp[y]), so dont have to worry about updating it. Pop y from stack and calculate again.
Solution: http://codeforces.com/contest/319/submission/15081127
Problem K:
Count the number of 1 bit in a numbers binary representation. Print Odd/Even.
Solution: http://paste.ubuntu.com/14402661/
Thank you.
Comments (0)
