Problem tags, which are supposed to help people categorize problems, some of them doesn't make much sense and need revamp.

For example, take a look at 2057E2 - Another Exercise on Graphs (hard version). At the time of this blog, it has tags "binary search" "brute force" "dp" "dsu" "graphs" "shortest paths" "sortings". Some of them doesn't make much sense to me.

"dsu" "graphs" "shortest paths" are fine imo. They either describe the core idea or the main techniques the problem use.

Then "dp" might be a bit controversial, it is probably about the fact that the modified Floyd algorithm is based on DP. It could be reasonable, especially if you didn't recognize that you are using Floyd algorithm when adding edges dynamically. The editorial also agrees with this idea. This trick seems rather classical to me. I don't think this is a big problem.

However the rest of them does not make much sense imo. For "binary search", I guess it's about the binary search approach for E1. That is too slow and cannot pass E2. And for "sortings", the only place to use "sorting" is the process of calculating the MST (you need to sort the edges), which isn't really related to the main idea of this problem. I guess a more suitable place for this tag for example, would be a problem that involves some greedy observation, and the conclusion ends up to be "sorting the elements in some order" as the key part. "brute force" makes absolutely no sense. Again, a better place for this tag might be some problem with a brute-force like approach that turns out to have a good complexity.

There is no fixed criterion to sort problems, and there is much space to argue. But in my opinion, problem tags are for helping people categorize problems (and decide which problems they will practice with, for example). The examples listed above don't serve this purpose well. I suggest revamping some of the tags and writing a brief guide about what each tag means, so people can have a common understanding of them.

If you have doubt regarding any of my opinions above, please comment in comment section and discuss. Thanks for reading.

UPD: 2057E2 - Another Exercise on Graphs (hard version) now has another tag "dfs and similar". What the hell? I don't know a single reasonable solution using DFS or similar things. I guess people are just adding tags randomly without thinking. Maybe we need to limit the users which can modify tags and/or a voting system.

I made my own script to filter problems in CF problemset. If such script with same function already exists you can ignore my post or downvote it.

This is a python 3 script that fetches all problems from CF problemset and allows custom filtering. It supports custom filter criteria in python expression format. After you input the filter function, it filters the problems and choose a random one. More details can be found in spoilers below.

id - The ID of the problem, in the format e.g. 1234H, 2024A.
rating - The CF rating tag. Can be absent.
contest - The contest id of this problem. Equals to contest.id.
index - The problem index in its contest, such as A or C.
pts - The problem points worth in its contest, 1500 for example.
tags - Problem tags. Used to filter out 'data structure' or 'geometry'.

id - The ID of the contest. It is different from the round number.
type - The scroing rules of such contest. Enumeration of "CF", "IOI" and "ICPC".
name - The contest name. Example, "Codeforces Round #7744 (Div. 10)".
division - The contest division in string. Enumeration of "Div. 1+Div. 2", "Div. 1", "Div. 2", "Div. 3", "Div. 4", "Educational" and "Unknown". (Wanna know how it works? Just do string matching in the contest name dummy)

import urllib.request as request
import json,random

class Problem:
    def __init__(self, apiobj):
        self.id = f"{apiobj['contestId']}{apiobj['index']}"
        self.rating = apiobj['rating']
        self.tags = apiobj['tags']
        self.contest = apiobj['contestId']
        self.index = apiobj['index']
        self.pts = apiobj['points']

class Contest:
    DIV_NAMES = ["Div. 1+Div. 2", "Div. 2", "Div. 1", "Educational", "Div. 3", "Div. 4"]
    def __init__(self, apiobj):
        self.id = apiobj['id']
        self.type = apiobj['type']
        self.name = apiobj['name']
        self.division = "Unknown"
        for div in Contest.DIV_NAMES:
            if div in apiobj['name']:
                self.division = div
                break

contests = {}
problems = []

def strawberry(problem,contest): # A test filter function
    return problem.rating == 2400 and contest.id >= 1000 and contest.division == "Div. 1" and "geometry" not in problem.tags

def fetchall():
    global contests, problems
    contests = {}
    problems = []

    try:
        contests_raw = request.urlopen("http://codeforces.net/api/contest.list?gym=false").read().decode()
        problems_raw = request.urlopen("http://codeforces.net/api/problemset.problems").read().decode()
    except:
        print("Codeforces API playing Genshin Impact at the moment")
        return False
    
    contests_obj = json.loads(contests_raw)
    problems_obj = json.loads(problems_raw)

    if contests_obj["status"] != "OK" or problems_obj["status"] != "OK":
        print("Codeforces API thinks your skill is too mediocre to use it")
        return False

    for problem_obj in problems_obj["result"]["problems"]:
        try:
            problem = Problem(problem_obj)
            problems.append(problem)
        except:
            pass

    for contest_obj in contests_obj["result"]:
        try:
            contest = Contest(contest_obj)
            contests[contest.id] = contest
        except:
            pass

    return True

print("Fetching problems...")
if not fetchall():
    exit(0)
candidates = []
schema = input("Enter filter expression ")
for problem in problems:
    try:
        if eval(schema,None,{'problem':problem,'contest':contests[problem.contest]}):
            candidates.append(problem)
    except Exception as e:
        print ("Error evaluating filter expression:",e)
if not len(candidates):
    print ("No problems matches your filter.")
else:
    result = random.choice(candidates)
    print(f"Your problem is: {result.id}")

I can use segment trees well, and I've done some basic scanline problems. But whenever these two algorithms appear in the same problem I will 100% fail to solve that one. I've been solving 930D - Game with Tokens and I was able to reduce it to "count the amount of integer points with at least one black point in each quadrant in terms of $$$(x+y, x-y)$$$". Then I stuck on the next move for 40 minutes. It turned out to be a stupid "scanline on $$$(x+y)$$$ build segment tree on $$$(x-y)$$$" thingy. Now I'm mad.

Sorry for asking this 69 IQ question for yet another time, but I really have no idea what situation I'm in.

I started solving CF problems in a fixed difficulty range every day recently. From what I've heard, as a thumb rule you should solve X+200 (where X is your rating) difficulty problem, so I tried to solve problems rated from 2300 to 2400.

After solving a few problems, I discovered that I could solve about 90% of the problems I open. And it only costs me around 20 minutes to come up with an idea. So I think they might be too easy for me.

However, I feel that I'm usually still able to learn some new idea after I solved each problem. I enjoyed maths and construction problems more than I ever did before. Also, it's really tough for me to try 2500-2600 problems, as I can only solve 20% of them. I guess these are signs that their difficulty is probably OK.

So can anyone describe what situation I'm in and give me some help?

This idea has came out lots of times but still sadly no changes has been made. So I'm confused and decided to make a blog about it.

Upvote (or downvote I don't care) if you support this. If you have any different ideas you can also comment in comments section.

Hello, everyone. I'd like to share an issue I met recently of which passing an STL container as a parameter through a function call caused MLE.

Look at this submission: 244198211. I was debugging it when I realized such line is causing MLE.

void insert (int p, string str, int len, int i, int id) {

I thought passing a string as a parameter might be the problem, so I changed my code and passed the index instead, and it got AC (there are other bugs but they don't matter): 244220216

So why is the problem?

The problem is, passing a parameter in non-reference calls the copy constructor and the destructor of the object each once, which means the object is being copied once every function call until it's finished. In normal situations it doesn't seems to be a big problem, but when you try to pass the object multiple times (especially if you're calling the function recursively) the memory usage is getting stacked up.

Note that this situation is the most common that people prefer to pass STL containers, especially string and vector in function parameters.

To make it clear I did some experiment, shown below:

#include<iostream>
using namespace std;

struct node {
	node () {
		cout << "Constructor called" << endl;
	}
	node (node &obj) {
		cout << "Copy constructor called" << endl;
	}
	~node () {
		cout << "Destructor called" << endl;
	}
};
node x;
void normal (node y) {
	cout << "Normal function body" << endl;
}
void reference (node &y) {
	cout << "Reference function body" << endl;
}
int main () {
	cout << "Calling normal function" << endl;
	normal (x);
	cout << "Finished calling normal function. Calling reference function" << endl;
	reference (x);
	cout << "Finished calling reference function" << endl;
	return 0;
}

And the result is:

Constructor called
Calling normal function
Copy constructor called
Normal function body
Destructor called
Finished calling normal function. Calling reference function
Reference function body
Finished calling reference function
Destructor called

From upon you can see that passing object as normal parameter calls copy constructor and destructor each once, and passing as reference does not do anything to the object.

So here are some suggestions to avoid this:

1. Pass indices or pointers instead of the original object. The straightforward way, though it might makes the code look bad (imo).
2. Use arrays instead of strings or vectors. Arrays are passed as pointers of the initial address (in other ways, they are passed as references automatically).
3. Pass reference if you can. It makes the code more readable compared to 1.

EDIT: The idea was originally wrong, but thanks to the guy in comment I've corrected. The point is still valid, but the description needs a bit changing.

Thanks for reading.

I'm trying to improve by solving problems Codeforces, but I'm quite unsure about whether it really helps me improve or not. The question is, the problems I meet are either problems that I can solve in my first sight, or else problems I can't solve in an hour. How to fix this? I'm using the problem difficulty filter but it doesn't work because the actual difficulty for me still varies a lot even in a fixed difficulty number.

For example, if a successful hacking attempt on Div.2 is added to the system test data, will that case be added to Div.1 too?

Only ICPC scoring is available in virtual participation now. So please make Codeforces Scoring an option for virtual participation too.

Several advantages:

1. It will be easier to see one's speed of doing a contest, as speed is far more effective in Codeforces scoring than ICPC.

2. It will be even closer to a real contest.

When I participate Div.2 contests, I always solve the easy problems(such as A, B or C) quickly, but then I can't even move on other problems. What should I do in that case?