notbad
BAN USERStudent
Hash all the symbols from Chemistry Periodic table. For any given words, use DP to test whether the word can be formed by the hash table. dp[i][j]: whether the sub sequence word[0,...,i-1] can be created.
dp[i][j] = dp[i][j-1] word[i] in the hash table or
dp[i][j-2] word[i-1,i] in the hash table.
The first step is to normalize the chemical equation. Such as: Equation->{compound+}*compound={compound+}*compound, compound->{element}*element.
Element->Uppercase{lowercase}. Then you use a grammatical analysis to analysis this to build a symbol table(a hash table maybe). At last, make sure the element in the left equals to that in the right.
We can store the number of node in each sub trees. It will be easy to find the kth element in tree like that. Each time we rand a number k between 1 and N, where N is the total number of the element.
struct Node {
int val;
int cnt; // number of nodes in the tree
Node *left, *rigth;
}
Node * find_kth(Node *root, int k) {
if ( root == NULL || root->cnt < k) {
return NULL;
}
int lc = 0;
if (root->left != NULL) {
lc = root->left->cnt;
}
if (lc >= k) {
return find_kth(root->left, k);
} else if (lc == k -1) {
return root;
} else{
return find_kth(root->right, k - lc - 1);
}
}
We can use intervals to store all the numbers possible. For examples, min=0, max=10 and the forbidden list is {1,5,8}, then we get an array of interval {[0,0],[2,4],[6,7],[9,10]}.We need sort the list to create the array of interval. Rand a number in [0,max-min-|forbidden list|],Next we only need to find the k-th in the array of interval. We can use binary search to do this. The complexity if O(ln(max) + |list|ln(|list|)) in time, and O(|forbidden list|) in space .
- notbad January 06, 2013To get the square root of a number if a float operation, it will be slower than other operation.What we need is an integer which is close to it's square root.We can use an algorithm like binary search to do this.
int get_closest_int_root(int n){
int low = 0 ,high = INT_MAX;
while(low < high){
int mid = ((low + high) >> 1);
if (mid * mid > n){
high = mid - 1;
}else if ( mid * mid < n){
low = mid + 1;
}else
return mid;
}
if (high*high > mid){
return (high*high - mid < mid - (high-1)*(high-1))?high:(high-1);
}else{
return ((high+1)*(high+1) - mid < mid - high*high)?(high+1):high;
}
- notbad August 03, 2012@bond I'm not quite sure how to process duplicate numbers.If the duplicate numbers can only be counted once,we should sort the numbers first and uniq them. If we should count every number no matter whether they are the same or not, the code above is Okay.Off course, promising no duplicate numbers will be appreciated.
- notbad July 29, 2012I think it can be less than O(N*N).Because the order defined in this problem is transitivity, which means if A<B and B<C ,then we get A<C.That is to say when we have compared A and B ,B and C, and get the result A<B and B<C ,we needn't compare A and C at all. But now, I don't know how to use it effectively.
- notbad July 23, 2012Because the time limit is 1sec.It may fail if the algorithm is O(N^2) where the max N is 10^4.the following alg is O(K^2) where K = (1<<11)=2048,it can insure the time limit 1sec.
1)represent each number with a integer from 0 to (1<<11)-1.where ith bit of the integer will be set 1 if the number contains the digit i.for instance 11330 will be represented by (1<<1)|(1<<3)|(1<<0)=11.
2)we have an array to accord the count of each integer
3)two for loops the array of the integer to count.
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
size_t const NN = (1<<11);
int cnt[NN];
int main()
{
int T;
cin >> T;
for (int t = 0 ;t < T ;++t){
int N;
cin >> N;
memset(cnt ,0 ,sizeof(cnt));
int res = 0;
for (int i = 0 ;i < N ;++i){
long long v;
cin >> v;
stringstream ss;
ss << v;
string digits ;
ss >> digits;
int hv = 0;
for (int j = 0 ;j < digits.length() ;j++){
hv |= (1<<(digits[j]-'0'));
}
++cnt[hv];
}
for (int j = 1 ;j < NN ;j++){
if (cnt[j] > 0){
//update here.
res += (cnt[j]*(cnt[j]-1))/2;
for (int k = j + 1 ;k < NN ;k++){
if ((j & k) != 0){
res += cnt[j]*cnt[k];
}
}
}
}
cout << res << endl;
}
}
Not Eulerian cycle, Hamilton cycles.
- notbad December 13, 2013