### tejas.pandey's blog

By tejas.pandey, 4 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;
}


•
• +4
•

 » 4 years ago, # | ← Rev. 2 →   +8 Each of the numbers can exist in 2^(N-1) different subsets. So let's define sum=2^(N-1) the answer is sum*1+sum*2+...+sum*N = sum*(n*(n+1))/2 .
•  » » 4 years ago, # ^ |   0 Thanks now i am able to understand .
•  » » » 15 months ago, # ^ |   -8 more cool jokes in my standup
•  » » 2 years ago, # ^ |   0 what if there are duplicate elements in the array?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Find the summation of all elements in the array and multiply it with 2^(n-1) . Each element in the set will occur 2^(n-1) times in the power set.
•  » » » 2 years ago, # ^ |   0 Then it won't work, as we can clearly see with array [1 1 1].In this case, one way is to generate subsets,remove duplicates and add them up.
•  » » 22 months ago, # ^ |   0 what is the complexity if i want to just generate the sum of every possible subset not whole sum ?
 » 15 months ago, # | ← Rev. 2 →   0 Your code here... 
•  » » 15 months ago, # ^ |   +1 Ongoing Contest at hackerearth.
•  » » » 15 months ago, # ^ |   +6 You show yourself as a very fair participant every freaking time but you yourself do such prohibited things behind the curtain. But this time that curtain raised and everyone knows your truth as HackerEarth publicly released the list of cheaters :Also, I am pretty sure that you get someone else's help or copy codes from Ideone in CodeChef long challenges because only cheating can justify your 43 world rank in long challenge while you even struggle to remain in blue color on Codeforces.Everyone is fed up with you. Go get a life and moderate anything when you yourself are a fair participant. Peace.
•  » » » » 15 months ago, # ^ |   +4 The list contains some big names including ICPC world finalists of this year.These guys are excellent competitive programmers and can easily win these contests.They should know that many of newbies coders including me are following them. They are inspiration for us and we want to be like them, but then they are doing these things just for some Gift vouchers. Here is my tweet after which hackerearth took this action
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   +15 It seems like hackerearth took this decision partially while allowing few cheaters to pass for the tie-breaker roundI still see few names that actually shows as Dis-qualified in the challenge but is in the list of winners AND LOL Lets look at timing of top 2 winners of tie breaker round in qualification round: These cheaters finished contest in 10 mins. No doubt the problems were on easy side but this is rampant cheating. And these cheaters are winning ipads as prize...Even though it was declared "Who solved all the problems in less time (less than 10 mins)" would be disqualified: I don't get how cheater abhay45 (abhaygarg) survived after this rule too....Do you have any explanation on this hackerearth admins? r3gz3n belowthebelt
•  » » » » » » 15 months ago, # ^ |   -6 We should now end this discussion here, it's getting too off-topic for this blog.
•  » » » » » » » 15 months ago, # ^ |   0 why the fuck you are saying this if anybody is cheating it must get revealed
•  » » » » » » » » 15 months ago, # ^ |   +6 I said to end this discussion here(on this particular blog).We should better discuss it on a separate blog with a name related to hack a heart contest.Our target audience is those who participated and not those who enter this blog for reading "sum of all elements...."
•  » » » » » » 15 months ago, # ^ |   +10 Actually the problem is with us guys who participate fairly. We regard these so called best coders from India as Gods and give them that much respect which they don't even deserve. This himanshujaju guy after being caught in plagiarism went on to rant on HackerEarth Moderators FB group which is a secret group btw. And due to his this big a status and fame, HackerEarth re-conducted the contest by removing him from plagiarism list so that he would get another chance to win.Here is a screenshot : clickAnd the funny thing is Harshil Shah who is world finalist this year commented on his post also doing the same rant.Now, lets see the time taken by Harshil Shah to solve problems in 1st round.You Sir, are a GOD (what an irony). You entered the contest, opened 1st problem, read the problem statement, thought your logic, coded up 24 lines of solution and then submitted it, all that in freaking 24 SECONDS !!And still you are talking about fair contests.Now, since he is going to ICPC WF, HackerEarth thought that, he can't cheat. It's impossible. But still let's give him a chance to participate in next round and now he is getting a BMS voucher.slow claps for HackerEarth and all these so called Gods of Indian Programming Community.
•  » » » » » » » 15 months ago, # ^ | ← Rev. 2 →   -12 Ok :)
•  » » » » » » » » 15 months ago, # ^ | ← Rev. 2 →   +16 THEN IT'S OK SOLVE MORE 2500+ PROBLEMS THEN CHEAT ON BIGGER LEVEL(it's jutified)GO TO WF AND GET AROUND 40-60 RANK AND COME BACK TO SUCK MY DI*K.
•  » » » » » » » » 15 months ago, # ^ |   +16 The only thing which I can infer from your post is that harshil is a "smart cheater" and if possible would you care to explain how harshil was still able to participate in the next round despite of the fact that he still remains disqualified on the round 1 leaderboard.