C# Coding Test Course, Delivering Gifts

Problem Description

You are planning an event to deliver Christmas surprise gifts to your friends.
There are N friends, and each friend has a list of gifts they would like to receive.
You need to ensure that as many friends as possible receive their desired gifts.
Each friend specifies one gift they want, and there is only one gift.
However, the gift can only be delivered to one friend.

Input Format

• The first line contains the number of friends N.
• From the second line up to the Nth line, the gifts each friend wants are listed.

Output Format

Output the maximum number of friends who can receive their desired gifts.

Constraints

• 1 ≤ N ≤ 100
• Gifts are represented by uppercase letters, with a maximum of 26 types.

Approach to the Problem

This problem is fundamentally similar to the maximum matching problem in graph theory.
Each friend can be represented as a vertex, and the gifts they desire can be represented as edges.
To solve this problem, we will take the friends’ gift requests as input,
create a list of friends requesting each gift, and then use an algorithm to find the maximum matching.

Algorithm Overview

– Construct a graph based on the number of friends and the requested gifts.
– Explore the graph to find assignable gifts for each friend.
– Use the DFS (Depth First Search) algorithm to attempt possible matchings.

Code Implementation

Below is the solution code for the gift delivery problem written in C#.

                
using System;
using System.Collections.Generic;

class Program
{
    static int N;                         // Number of friends
    static List friends;          // List of gifts friends want
    static Dictionary gifts; // Matching status of each gift
    static bool[] visited;                // Record of DFS visitation

    static void Main(string[] args)
    {
        N = int.Parse(Console.ReadLine());
        friends = new List();

        for (int i = 0; i < N; i++)
        {
            friends.Add(Console.ReadLine());
        }

        gifts = new Dictionary();
        int totalMatched = 0;

        foreach (var friend in friends)
        {
            visited = new bool[26];
            if (DFS(friend[0], ref totalMatched))
            {
                totalMatched++;
            }
        }

        Console.WriteLine(totalMatched);
    }

    static bool DFS(char gift, ref int totalMatched)
    {
        int index = gift - 'A';

        if (visited[index]) return false; // Gift already visited
        visited[index] = true;

        if (!gifts.ContainsKey(gift.ToString()) || gifts[gift.ToString()] == -1)
        {
            gifts[gift.ToString()] = totalMatched; // Gift matching
            return true;
        }

        return false;
    }
}
                
            

Code Explanation

The above code solves the gift delivery problem through the following procedures.

• Input Reading: Read the number of friends N and input the desired gifts for each friend.
• DFS Function Implementation: Check if the requested gift is available and attempt matching.
• Visitation Record: Manage visitation records to accommodate requests for each gift only once.
• Output Result: Output the maximum matching result.

Time Complexity

This algorithm has a time complexity of O(N^2).
Since DFS is called for each friend, and the number of gifts is limited to a maximum of 26,
it is efficient enough within the problem’s constraints.

Conclusion

The “Gift Delivery” problem is an interesting problem of distributing gifts among friends.
It demonstrates that it can be implemented through the principles of DFS and maximum matching in graphs.
This principle can be applied to solve similar problems in the future.

I hope this article helps you prepare for C# coding tests.
Please practice algorithms through various problems.