Problem A: Two Friends

There are two possible scenarios:

1. There exists a pair where person A's best friend is B, and B's best friend is A. In this case, just inviting these two individuals suffices.
2. No such mutual friendship exists. If person A's best friend is B, and B's best friend is C, then inviting A, B, and C ensures both A and B attend.

Simply output 2 or 3 based on these conditions.

#include<cstdio>
using namespace std;

const int MAXN = 55;
int n, friends[MAXN];

int main()
{
    int t; scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &friends[i]);
        
        bool found = false;
        for(int i = 1; i <= n; i++)
            if(i == friends[friends[i]]) { found = true; break; }
        
        printf("%d\n", found ? 2 : 3);
    }
    return 0;
}

Problem B: Shifts and Sorting

Apply a greedy approach by moving consecutive sequences of 1s one at a time. Each move costs one more than the current length of the sequence being moved.

Repeatedly shifting 1s to the right will eventually group all 1s together on the right side.

The implementation skips leading zeros and groups consecutive 0s and 1s. For each group of 1s, the cost equals the number of preceding 0s multiplied by (total count of 1s so far + 1).

A critical oversight during the contest was not using long long, causing a wrong answer.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 200005;
int n; char str[MAXN];
int segments[3][MAXN], segment_count;

int main()
{
    int t; scanf("%d", &t);
    while(t--)
    {
        scanf("%s", str + 1);
        n = strlen(str + 1);
        
        segment_count = 0;
        for(int i = 1; i <= n; i++)
        {
            if(str[i] == '0' && segment_count == 0) continue;
            if(i > 1 && str[i] != str[i-1] && str[i] == '1') 
                segment_count++;
            segments[str[i] - '0'][segment_count]++;
        }
        
        long long total_cost = 0, ones_so_far = 0;
        for(int i = 1; i <= segment_count; i++)
        {
            ones_so_far += segments[1][i];
            total_cost += 1LL * segments[0][i] * (ones_so_far + 1);
        }
        
        printf("%lld\n", total_cost);
        
        for(int i = 1; i <= segment_count; i++)
            segments[0][i] = segments[1][i] = 0;
        segment_count = 0;
    }
    return 0;
}

Problem C: Minimizing the Sum

Multiple edge cases and incorrect interval ranges caused two wrong answers. This problem can be solved efficiently using dynamic programming.

Problem D: Shop Game

An inocrrect greedy strategy was used during contest. After reviewing the correct approach, it was quickly implemented and accepted.