Submission #160028

#	Time	Username	Problem	Language	Result	Execution time	Memory
160028		rama_pang	Friend (IOI14_friend)	C++14	100 / 100	37 ms	3320 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
using namespace std;


/*  Protocols: add new vertex i at step i, with following types:
    1.  type 0 = IAmYourFriend : edge between vertex i and host[i]
    2.  type 1 = MyFriendsAreYourFriends : edge between vertex i and 
                 all friends of host[i], not includeing host[i]
    3.  type 2 = WeAreYourFriends : IAmYourFriend + MyFriendsAreYourFriends

    Answer is the maximum cost independent set. There are 3 cases for each protocols:
    1.  alternate[v] = alternate[v] + confidence[i], confidence[v] = confidence[v] + alternate[i]
    2.  confidence[v] = confidence[v] + confidence[i], alternate[v] = alternate[v] + alternate[i]
    3.  confidence[v] = max(confidence[v] + alternate[i], alternate[v] + confidence[i]), alternate[v] = alternate[v] + alternate[i]

    Then if alternate[v] > confidence[v], confidence[v] = alternate[v].

    Proof 1:
        Denote current graph as G. The solution for this graph is costG, before i is
        added to the graph (and this is true for the next proofs). There are two
        cases: either i is picked, or not. If i is picked, then v cannot be picked,
        and vice versa. Thus we can solve this problem by keeping another array
        alternate, denoting the cost if i is not picked.

    Proof 2:
        Denote current graph as G. The solution for this graph is costG, if v is not
        picked, or costG + confidence, if v is picked. Thus it is exactly the same as
        solving the graph G, with confidence[v] = confidence[v] + confidence[i].

    Proof 3:
        Denote current graph as G. Let the solution for this graph is costG. Then if 
        we pick v, the we cannot pick i. On the other hand, if we pick i, we cannot
        pick v. If we pick either i or v, then their neighbours couldn't be picked.
        So the optimal way is by max(i, v) or not picking it.Thus this is exactly the 
        same problem as finding costG with confidence[v] = max(confidence[v], confidence[i]).

    For the transition, just alternate between the array alternate and confidence. The answer
    is the maximum of alternate and confidence at vertex 0, after starting from the end of
    protocols added.

*/


int findSample(int n, int confidence_[], int host[], int protocol[]) {
    vector<int> confidence(n, 0), alternate(n, 0);
    for (int i = 0; i < n; i++) confidence[i] = confidence_[i];
    for (int i = n - 1; i > 0; i--) {
        switch (protocol[i]) {
        case 0: // IAmYourFriend
            confidence[host[i]]  = confidence[host[i]] + alternate[i];
            alternate[host[i]]   = alternate[host[i]] + confidence[i];
            break;
        case 1: // MyFriendsAreYourFriends
            confidence[host[i]]  = confidence[host[i]] + confidence[i];
            alternate[host[i]]   = alternate[host[i]] + alternate[i];
            break;
        case 2: // WeAreYourFriends
            confidence[host[i]]  = max(confidence[host[i]] + alternate[i], alternate[host[i]] + confidence[i]);
            alternate[host[i]]   = alternate[host[i]] + alternate[i];
            break;
        }

        confidence[host[i]] = max(confidence[host[i]], alternate[host[i]]);
    }

    return confidence[0];
}

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31