tejas.pandey's blog

By tejas.pandey, 3 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  

»
3 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 .

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

    Thanks now i am able to understand .

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what if there are duplicate elements in the array?

    • »
      »
      »
      14 months 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.

    • »
      »
      »
      14 months 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.

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

    what is the complexity if i want to just generate the sum of every possible subset not whole sum ?

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Your code here...
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Ongoing Contest at hackerearth.

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How can i see this list..?

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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

          • »
            »
            »
            »
            »
            »
            3 months 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.

            • »
              »
              »
              »
              »
              »
              »
              3 months 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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months 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...."

          • »
            »
            »
            »
            »
            »
            3 months 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.

            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
                Vote: I like it -12 Vote: I do not like it

              Please read this post completely. I don't really lose my patience easily, but thanks to you I did.

              Let us begin with how I managed to submit so quickly. It is all because of my "big status and fame". Not kidding! Innumerable times people have pinged me with questions from live contests (read this too), seeking some form of help. It's not possible for me to always know if it is a part of an ongoing contest or not. I received help messages from a friend, who pasted the 1st and 3rd question of this contest, and I ended up giving him the solutions for both the questions.

              When I started the contest in evening, I realized what I had done. The task in front of me was very simple, type an already tested logic as fast as you can. The 2nd and 3rd questions didn't even require that, I just had to add 4-5 lines in my library code and get an AC. Would I have won if I didn't know the two questions in advance? Tough to say, I think maybe not. But if you think speed of coding is an issue here, please look at the last two Topcoder India qualifiers leader board which I have been winning solely because of my speed in solving trivial problems. When the problems become tougher, I do suck.

              Now, why did I rant? To me, it doesn't look like I cheated. I had a look at the questions, but it wasn't in my hand to avoid them. Last year, I went to some college contest onsite and all I had to do there was to paste my AC codes from SPOJ with trivial modifications as solutions. Is that cheating too? I don't really think so, unless it is mentioned that I can't use library codes or old codes. Also, I was considered plagiarized some time back on hackerearth when I hadn't submitted a single code. So I wanted to know how actually their plagiarism thing works. Another reason for the rant is the existence of contests with time window. Most of the programmers don't like it, because it gives smart cheaters a better chance. And this is the exact rant harshil had posted in the comment. Also, if there is a problem I speak about it as effectively as I can. I didn't want to post it secretly, but then that is the designated group for effective communication on this topic.

              Now, let me touch a bit on the point of "big status and fame" and "don't deserve respect". Given a chance, I don't really want any of these. I gladly accept I am one of the dumbest competitive programmer to be in div 1. I believe most of the programmers don't really care about their status or fame, but look at the tasks they have in front of them. I have had to solve around 2500+ problems across various online judges to somehow become a div 1 programmer. I have a long way to go before I can really justify my "big status and fame".

              As for your next contest, good luck and have fun!

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months 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.

            • »
              »
              »
              »
              »
              »
              »
              3 months 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?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                This is absolute shit...You should have written instead of whole paragraph "Others cheat,so I would also cheat".By the way ,Before pointing fingers at HackerEarth,you should have considered yourself.I think no one can stop you from cheating unless you yourself have to courage to not join the malpractice ...

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months ago, # ^ |
                  Vote: I like it -9 Vote: I do not like it

                You still haven't explained, how were you able to take part in 2nd round ? Did you had some backdoor talks with HackerEarth :P ?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months 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.