Hi, Codeforces!

I'm delighted to invite you to the best/second best/third best round of 2025 so far! Codeforces Round 997 (Div. 2) will be held on Jan/17/2025 17:35 (Moscow time). You will be presented with at least $$$6$$$ and at most $$$6$$$ problems, one of which might be divided into two subtasks, and $$$2$$$ hours to solve them.

Many of you may not believe it, but the problems were authored and written by nifeshe with a great help from maomao90. Moreover, I would like to thank:

• maomao90 for coordinating the round and helping with tasks ideas/preparation.

• Alexdat2000 for translating the problems to Russian.

• All of our testers: errorgorn, A_G, LipArcanjo, _istil, Markadiusz, Error_Yuan, Intellegent, mwen, LMeyling, hazzlek, iLoveIOI, Rideris, DilshodbekX, chromate00, tibinyte2006 for, believe it or not, testing.

• MikeMirzayanov for the Codeforces and Polygon platforms.

• Bliznetc for playing chess with me.

• And You for participating!

The score distribution is as follows: $$$500-1250-1500-2000-2250-(2750+1250)$$$.

I hope you will find a non-empty subset of problems to be interesting. Good luck!

Yesterday some guy posted a blog about accidentally submitting a solution to a problem in the most recent round meaning to do it after the contest ends. He entered a competition, lost 233 rating and then requested to make the contest unrated to him. As it is already clear to probably everyone, he participated from an alt and meant to submit from it, but for some reason logged in from his main.

I quickly found his alt and made a comment. Shortly after that he deleted the blog.

Here is a guide on how to find alts!

Look at the submissions

This method works very frequently. What do people oftenly do after participating in a contest from an alt? They resubmit all the problems from their main. This is how it looks like in the example above:

5 problems were submitted in 1 minute. It means that the guy was either the tester in that round, or participated from an alt. If we know that it is the latter, there is a high probability that we can find his alt already. Go to any problem that he submitted there (prefferably the one with less solves), sort all the submissions on it by the execution time and check all the solutions that have that exact execution time and memory usage. You can also try to only look for the submissions that use his language, but it might not work (as seen below).

If we get lucky, we can find the alt from the first try. In this case we didn't, because his submissions from the alt and the main had different execution times:

We should try again! After 2 more attempts, we find this:

After seeing that, we verify that is it indeed his alt from his name and codestyle. This is how I initially found it.

Search the handle

You would be amazed to know how many alts I found like that. Just look up the handle or any part of it. In this case we find his unrated alt:

Search the handle harder

Since searching handles manually is hard, we can try to do something with code. There are (probably) many clustering algorithms, we can try to use them on the list of handles and check the cluster the handle is in. I have no idea how to do any of that, so I simply asked ChatGPT to make something in Python and it worked. It produced the following after some of my modifications:

import requests
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.cluster import KMeans
from collections import defaultdict

# Function to fetch all users from Codeforces API
def fetch_users():
    url = "https://codeforces.net/api/user.ratedList"
    response = requests.get(url)

    if response.status_code == 200:
        data = response.json()
        if data["status"] == "OK":
            return data["result"]
        else:
            print("Error in response: ", data["comment"])
    else:
        print("Error fetching data: ", response.status_code)
    return []

# Function to filter users by max rating
def filter_users_by_rating(users, min_rating):
    return [user for user in users if user.get('maxRating', 0) > min_rating]

# Function to cluster users by the similarity of their names
def cluster_users_by_name(usernames, num_clusters=10):
    # Vectorize the usernames using TF-IDF with character n-grams
    vectorizer = TfidfVectorizer(analyzer='char', ngram_range=(2, 3))
    X = vectorizer.fit_transform(usernames)

    # Perform k-means clustering
    kmeans = KMeans(n_clusters=num_clusters, random_state=42)
    clusters = kmeans.fit_predict(X)

    clustered_users = defaultdict(list)
    user_cluster_map = {}
    for username, cluster_id in zip(usernames, clusters):
        clustered_users[cluster_id].append(username)
        user_cluster_map[username] = cluster_id

    return clustered_users, user_cluster_map

# Main processing function
def process_users(min_rating, num_clusters):
    # Fetch users
    users = fetch_users()

    # Filter users by max rating
    filtered_users = filter_users_by_rating(users, min_rating)
    print(len(filtered_users))
    # Extract usernames
    usernames = [user["handle"] for user in filtered_users]

    # Cluster users by the similarity of their names
    clusters, user_cluster_map = cluster_users_by_name(usernames, num_clusters)

    return clusters, user_cluster_map

# Fetch and process users (run this once)
clusters, user_cluster_map = process_users(min_rating=1599, num_clusters=5000)

from google.colab import files

def save_clusters_to_file(clusters, filename="clusters.txt"):
    with open(filename, "w") as file:
        for cluster_id, user_list in clusters.items():
            cluster_size = len(user_list)
            file.write(f"{cluster_size} {' '.join(user_list)}\n")
    return filename

output_file = save_clusters_to_file(clusters)

# Provide a link to download the file in Google Colab
files.download(output_file)

def get_user_cluster(username):
    cluster_id = user_cluster_map.get(username, None)
    if cluster_id is not None:
        return clusters[cluster_id]
    else:
        return "User not found"

# Example usage
username = "nifeshe"
user_cluster = get_user_cluster(username)
if user_cluster != "User not found":
    print(len(user_cluster))
    print(f"The cluster for user '{username}' is: {user_cluster}")
else:
    print(user_cluster)

I don't know (and, frankly, don't care) how this all works, I just tweaked the constants so it produced a reasonable result after running for 1 hour. Here is a download link if someone is interested. Only active users who have the highest rating of at least 1600 are included. As we can see, the cluster my handle is in is: ['nifeshe', 'nifes', 'knifeman', 'iamnifer', 'coniferousdyer'], which indeed contains similar handles to mine.

There are some other ways to find an alt, such as looking through the standings and getting HTML pages of the submissions, but they will rarely work and the 3 methods above are already enough in most cases. Good luck on losing your friends!