Google-Kickstart-Round-F-Teach-Me(Short Editorial)

Link to the problem :-

Solution:-

1)If say for a given “i” , the size of i'th set is “3” and the elements are :- {2,4,7} …[You keep these elements in sorted order]

2)Now the answer of this set will be summation of count of all the sets whose size is less than “3” .We can easily store the counts of number of sets whose size was “1”, “2” , “3” , “4” and “5” using an array like :- int a[7];

3)In this particular case, answer is : - a[1]+a[2].

4)Now, for all the sets whose size>=3, example a size-4-set:- {2,4,5,7} …
We need to know the number of sets of size “4” which has {2,4,7} in it and the problem is solved!!!..[Same we do with sets of size-“5” and size-“3”]…

5)How do we do it?
We generate all combinations of set of size-“4” of 3 elements :–>
{2,4,5}
{2,4,7}
{4,5,7}
…and store their frequency in a map…We are done!!
Similarly, we generate all combinations of set of size-“4” of “1” and “2” and “3” and “4” elements!! :slight_smile:
6)We do the same thing for set of all sizes {1,2,3,4,5 only…}

7)Link to my AC code:- k2A2KB - Online C++0x Compiler & Debugging Tool - Ideone.com

8)Happy-Coding ! :slight_smile:

Note:- Final Answer:–> a[1]+a[2]+ f3 + f4 + f5 for our current set, calculate this value for all the “n”-sets and add them up!!

2 Likes

Bro i was Unable to solve the first one also i.e Flattening. Can You Give me a short editorial with your ac code for it. Please

1 Like

Yup, I’ve solved it, I’ll post its short editorial as soon as I get the time! :slight_smile:

1 Like

Thanks bro for giving your valuable time…

1 Like

What is the time complexity ?

2 Likes

Assuming log(N) time taken by a map,

Total Time Complexity:- O(N*T*28*log(N))

Time limit is :- 40 seconds per test-set

So it works :slight_smile:

It actually does not, it TLE’s, did you submit your code ?

1 Like

See it works.

For increasing one’s knowledge :- 5*(10^9) operations working in less than 2 seconds!? - Codeforces

It does. Do not use long long when it is not necessary!

1 Like

You are taking it far too personally.

Its a very genuine question on if the code passes or not. Its your editorial, if you jump out of discussions like this, then thats a very wrong stance.

1 Like

Its unofficial and short. Also, if I have written an editorial, it is safe to assume that I wrote AC code and submitted. To check if I was right. I guess everybody checks their code before making any editorial?
If they don’t, they are at fault.
And see, 40 seconds is the time-limit as well .

1 Like

Bro can u please tell me what that 40 sceonds means in comparison to normal codechef or codeforces time limit.
Because these are usualy 1 or 2 seconds but on Kickstart i see it 30 or 40 what is that equivalent to???

1 Like

An important thing to realize is that the time does not seem to be proportional as in, I have felt many times that if you increase the time limit by a factor K, the number of operations increases by a factor more than K.

2 Likes

Yup , I realized that if 10^8 operations take 1-second, it does not mean 10^9 operations will take 10-seconds :stuck_out_tongue: Realized this yesterday itself :stuck_out_tongue:

I repeat, I still feel you took that post in a wrong way. That puts all the arguments you gave to rest.

See, I have already edited all the wrong stuff hours ago already :slight_smile:

1 Like

I had a general solution for this problem. I mean, I did not solve it making different cases for size 3 and so on. So here is my idea:

  1. The only case when i^{th} person can’t mentor the j^{th} person is when the skills of the j^{th} person is the super-set of the skills of the i^{th} person.
  2. We can easily count this. For every person’s set of skills, generate all proper subsets and keep a count of these using a map M. Separately keep a count of every set as well in another map CNT.
  3. Now for each distinct set of skills that we have,
    a. We add N (the number of persons) to the answer.
    b. Now subtract the (count of this set - 1) from the answer (maintained in CNT).
    c. Now we subtract the count in M for this set as it has the count of all super-sets of this set.
    This passes if you use int everywhere except the answer.
map<vector<int>,int> M;
map<vector<int>,int> CNT;
int main()
{
    io;
    int TC;
    cin>>TC;
    for(int t=1;t<=TC;t++)
    {
    	cout<<"Case #"<<t<<": ";
        int n,s;
        cin>>n>>s;
        int c[n];
        M.clear();
        CNT.clear();
        for(int i=0;i<n;i++)
        {
            cin>>c[i];
            vector<int> v;
            for(int j=0;j<c[i];j++){
                int x;
                cin>>x;
                v.push_back(x);
            }
            sort(all(v));
            for(int k=1;k<(1<<c[i])-1;k++){
                vector<int> subset;
                for(int j=0;j<c[i];j++){
                    if(k&(1<<j)){
                        subset.push_back(v[j]);
                    }
                }
                M[subset]++;
            }
            CNT[v]++;
        }
        long long ans=0;
        for(auto vec:CNT){
            ans+=((vec.second)*(n-(vec.second)));
            ans-=(vec.second*M[vec.first]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}
1 Like

@anon55659401 , I believe your behaviour is a bit arrogant. this is not your personal blog, this is the public Codechef. who told you that we are interested of the fact/approach that you managed to solve, in practice mode, some problem from some external competition?

Nice Approach :slight_smile: :slight_smile: :slight_smile:

@hungrykoala People usually share their ideas about solutions to problems from Kickstart,etc. on Codechef and I did receive ton of requests to share the solution sketch of this problem, so I just shared it . I don’t think its any crime or something against the Code of Conduct of Codechef, and about the screenshot, Aman asked me if I solution is correct, so that was the only way to provide him the proof. And I really don’t care who cares and who doesn’t, I just wanted to contribute a bit so I did :slight_smile: