### tejas.pandey's blog

By tejas.pandey, 5 years ago, ,

Today I was learning Trie from topcoder tutorial Topcoder Trie Tutorial.

I am having confusion in countPrefixes function in topcoder tutorial , i am not able to understand last line of this function.
return countWords(edges[k], prefix)
If someone can explain use of above line.
So i modified countPrefixes function and have written this code for trie following topcoder tutorial . Not sure it is correct way of implementing or not.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int  MOD=1000000007;
const int  INF= int(1e9),ALPHA=26;
string s;
int n;
struct Trie {
int words,prefixes;
Trie *edges[ALPHA];
Trie() {
words=0;
prefixes=0;
for(int i=0;i<ALPHA;i++) {
edges[i]=NULL;
}
}
};
Trie root;

void addword(Trie *vertex,int cur) {
if(cur==n) {
vertex->words=vertex->words+1;
} else {
vertex->prefixes=vertex->prefixes+1;
if(vertex->edges[s[cur]-'a']==NULL) {
vertex->edges[s[cur]-'a']=new Trie;
}

}
}
int countWords(Trie *vertex , int cur) {
if(cur==n) {
return vertex->words;
} else if(vertex->edges[s[cur]-'a']==NULL) {
return 0;
} else {
return countWords(vertex->edges[s[cur]-'a'],cur+1);
}
}
int countPrefixes(Trie *vertex , int cur) {
if(cur==n) {
return vertex->prefixes+vertex->words ;
} else if(vertex->edges[s[cur]-'a']==NULL) {
return 0;
} else {
return countPrefixes(vertex->edges[s[cur]-'a'],cur+1);
}
}
int main()
{
ios_base::sync_with_stdio(false);

int q;
cin>>q;

while(q--) {
cin>>s;
n=s.size();
}
cin>>q;
while(q--) {
cin>>s;
n=s.size();
cout<<countWords(&root,0)<<" "<<countPrefixes(&root,0)<<endl;
}

return 0;

}



• 0

By tejas.pandey, 5 years ago, ,

Ankit has a set of numbers and has recently studied set theory. He has created a power set of this set and is writing a program to compute sum of all elements of all the subsets in power set. Power set of a set S is defined as set of all possible subsets of S.

Set S consist of all the number from 1 to N.

You need to calculate this sum for a given n.

Example:

Given N=3, S={1,2,3} P(S) = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} answer = (1)+(2)+(3)+(1+2)+(1+3)+(2+3)+(1+2+3) = 24

Input First line has T, the total number of test cases. The next T lines contains a number N in each line.

Output T lines giving answer as defined in the question for each N.

Constraints 1<=T<=42 1<=N<=42

Sample Input 1 3

Sample Output 24

I have used bitmask to generate all the subsets to calculate the sum but it is giving tle.

But i have seen people using below code but unable to understand the logic.

#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,i;
scanf("%d",&n);
long long int ans=1;
for(i=0;i<n-1;i++)
ans=ans<<1;
ans=ans*(n*(n+1))/2;
printf("%lld\n",ans);
}
return 0;
}