Journey to the Moon

  • + 0 comments

    The answer seems wrong.

        long long int totalWays = n*(n-1) / 2;
        long long int sameWays = 0;
        
        for(i=0;i<numComponents;i++)
        {    
            sameWays = sameWays + (eachC[i]*(eachC[i]-1) / 2);
        }
        cout << (totalWays - sameWays) << endl;
        return 0;
    

    after finding components and number on each component, with the same syntax used in the editorial soln, the final calculation should be:

        int the_count = 0, total=0;
        for (i=0;i<numComponents;i++) {
            the_count += eachC[i] * total;
            total += eachC[i];
        }
        return the_count;
    

    This is basically keeping the property of the_count: it is the number of possible interactions until ith component. Addition of each new component creates itself times the total number of nodes; as an addition to previous possibilities.

    This changes half of the test cases.