Editorial for Berf's Game

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

English

This question is about Eular Path. According the Eular Path theorem, "a connected graph has an Euler cycle if and only if every vertex has even degree" or "The number of the odd degree vertices should be zero or two".

Here, each level can be represented as a connected graph (It is guaranteed in the question). Therefore, it is enough to calculate the degrees of the vertices/islands. Then, we will check for the degree of vertices/islands to determine the validation.

Türkçe

Bu soru Eular Path hakkındadır. Eular Path teoremine göre, "bağlı bir grafiğin Euler Path'i olması için her köşenin derecesi çift" veya "Tek dereceli köşelerin sayısı sıfır veya iki" olmalıdır.

Burada, her seviye bağlı bir grafik olarak temsil edilebilir (bu soruda garanti ediyor). Bu nedenle köşelerin/adaların derecelerini hesaplamak yeterlidir. Ardından, doğrulamayı belirlemek için köşelerin/adaların derecesini kontrol edeceğiz.

Codes

C++

#include <bits/stdc++.h>

using namespace std;

string solution() {
    int number_of_islands, number_of_roads;

    cin >> number_of_islands >> number_of_roads;

    int degrees[number_of_islands] = {0};

    // Getting the roads inputs and increase the degrees of islands
    for (int is_1, is_2; number_of_roads; number_of_roads--)
    {
        cin >> is_1 >> is_2;
        degrees[is_1]++;
        degrees[is_2]++;
    }

    int odd_degree_vertex = 0;
    for (int i = 0; i < number_of_islands; i++)
    {
        if (degrees[i] % 2)
            odd_degree_vertex++;
    }

    return ((odd_degree_vertex == 0 || odd_degree_vertex == 2) ? "VALID" : "INVALID");
}


int main() {
    cout << solution() << endl;

    return 0;
}

Python 3

def solution() -> str:
    number_of_islands, number_of_roads = [int(x) for x in input().split()]

    degrees = [0]*number_of_islands

    for _ in range(number_of_roads):
        is_1, is_2 = [int(x) for x in input().split()]
        degrees[is_1] = degrees[is_1] + 1
        degrees[is_2] = degrees[is_2] + 1

    odd_degree_vertex = 0
    for i in range(number_of_islands):
        if degrees[i] % 2:
            odd_degree_vertex += 1

    if odd_degree_vertex == 0 or odd_degree_vertex == 2:
        return "VALID"
    else:
        return "INVALID"


print(solution())