tejas.pandey's blog

sum of all elements of all the subsets in power set
By tejas.pandey, 10 years ago, In English

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;
}
  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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 .

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks now i am able to understand .

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what if there are duplicate elements in the array?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
Your code here...
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Ongoing Contest at hackerearth.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +15 Vote: I do not like it

          It seems like hackerearth took this decision partially while allowing few cheaters to pass for the tie-breaker round

          I still see few names that actually shows as Dis-qualified in the challenge but is in the list of winners

          (Winners list: https://drive.google.com/file/d/0ByHiAdvbqhWpY1QyQTgtYTFIaU0/view)

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it -6 Vote: I do not like it

            We should now end this discussion here, it's getting too off-topic for this blog.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              why the fuck you are saying this if anybody is cheating it must get revealed

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it +6 Vote: I do not like it

                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...."

                → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            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 : click

            And 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 2   Vote: I like it -12 Vote: I do not like it

              Ok :)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                ← Rev. 2   Vote: I like it +16 Vote: I do not like it

                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.

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it +16 Vote: I do not like it

                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.

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 4   Vote: I like it -24 Vote: I do not like it

              First, Let me clear your notion of "GOD". I am no GOD in programming. I am just a mediocre purple on codeforces. Even to achieve this much rating, I have had to solve 1000+ problems on codeforces itself. There are lots of legendary programmers in India (some of them left competitive programming, so you might not even know them) who really deserves this title of GOD and it's not me. The fact that I ended up winning just BMS gift card and not iPad confirms that I am just a mediocre programmer.

              Second, let me answer you why did I cheat. I had very bad experiences in this type of time window contests previously. I used to participate in a "fair and ethical" manner in this type of "time window contests" and used to end up not winning anything substantial just because others had cheated. I faced this scenario in 2-3 times in such contests. That's why, this time I really knew that everyone is going to cheat and I also knew that if I didn't cheat I am not going to win any prize this time too. Hence, real problem is not in your wrongly perceived GOD programmers, it's really in contest pattern.

              I can't really understand why hackerearth doesn't remove this type of contests which forces or encourages participants to cheat. Only thing it is trying to do in such contests is to find contestants who really cheated and blame them for cheating, instead of changing its contest rules in such a manner that its hard to cheat in first place. This type of time window contests don't appear in any other "highly successful programming platforms" due to same reasons. Hackerearth should try to learn from such programming platforms if it wishes to become one among them someday. Also, it should learn to consider the suggestions of its fellow moderators. No one even cared to reply to my comment in the facebook group which is essentially conveying the same point I described here about time window contests.
              r3gz3n, prat33k, Would you care to explain why hackerearth sticks to such time window contest patterns?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                Hackerearth started this type of contest only to give flexibility to the users, so that everyone can get enough opportunity to compete and win prizes, assuming that people will genuinely take part in the contest to judge their skills and to see where they stand. But we have faced enough number of plagiarism issues regarding the same, and have realized that people will any how misuse it in future instead of genuinely using their skills. So whenever the prizes will be there in the contest, we decided to discontinue the time window contest in the future. Along with this change, we are also adding other parameters to curb such issues.

                → Reply