Hey Codeforces,

For a while I was wondering, what does the majority of people about having contest filtering in the contest tab? I think it would be helpful for people if they could filter all div. 1s, 2s, 3s, Edus or others in order to make searching for contests to VC and problems to solve.

I know there are websites that can do this for you, but I think it would benefit many people by having this filter without having to bookmark these websites.

I know the world is a little hectic right now, so it's fine if this doesn't get implemented due to the circumstances, but I believe it would be a cool suggestion, at least for me personally.

Thanks, have a good day

Hello, Codeforces community.

Today, I will be talking about a little known trick that allows you to search a graph with M^2 (or E^2) edges. This trick uses a set and BFS, and is named after the infamous USACO problem Pie for a Pie.

First off, I want to thank two orzosities who taught me this trick. Thank you, lunchbox and PurpleCrayon!

Prerequisites: - C++ Set / Graph Theory

Let's get into it.

First problem: 0-1 MST

Abridged problem statement:

You're given an undirected graph of n nodes with n(n-1)/2 total edges (it is complete). You are given m edges, where the length is 1, and the rest of the n(n-1)/2 — m edges are of length 0. Find the Minimum Spanning Tree (MST) of this graph.

Solution:

It can be shown that our MST will consist of as many edges of 0 that we can add (lets call a collection of nodes with the same length 0 connected to each other a connected component). Therefore, there will be a select number of 1s that we must use to connect these components. It turns out that the number of 1s we need to use is equivalent to the number of connected components in the graph subtracted by 1.

Now, our problem is reduced down to find the number of connected components with the length of 0. Naive DFS or BFS takes O(V + E) time, where V = n and E = n(n-1)/2. It can be shown then, that our current code would be in O(N^2). However, we can make the observation that whenever we visit an element, we don't need to check this element anymore in any of our future traversals. Therefore, we can try to erase this node in every visit. We can simply manage do this with a set.

Code:

// cool trick, thanks lunchbox & purple!!!

void solve(int test_case = 0)
{
    int n; cin >> n;
    int m; cin >> m;
    vector<set<int>> adj(n);
    set<int> toremove;
    queue<int> bfs;
    for(int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        adj[x].insert(y);
        adj[y].insert(x);
    }
    vector<int> todo;
    for(int i = 0; i < n; ++i)
        toremove.insert(i);
    int ccs = 0;
    for(int i = 0; i < n; ++i) {
        if(toremove.count(i)) {
            bfs.push(i);
            ++ccs;
            toremove.erase(i);
            while(bfs.size()) {
                int x = bfs.front();
                bfs.pop();
                todo.clear();
                for(int j : toremove)
                    if(!adj[x].count(j)) 
                        todo.pb(j);
                for(int j : todo)
                    toremove.erase(j), bfs.push(j);
                
            }       
        }
    }
 
    cout << ccs - 1 << "\n";
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    // C++ IO Stuff
    int T = 1;
#ifdef runcase
    cin >> T;
#endif
    // new test cases
    for(int nt = 0, i; nt < T; nt++) {
        solve(nt);
        ++i;
    }
}

Explanation: This is ordinary BFS, except we need to erase our node once we visit. However, we cannot simply erase this element from the set as we are traversing, so we need an extra array that will store our information for us (our what we have to-do). We will erase this information subsequently. Despite this, queue traversal is simple and checking if our element is in the set is the same as using a visited array. Our code is now at complexity O(N log N + N log M) because of our array of sets, and our insertion, erase, and count functions on the set we use to check for nodes (toremove). Submit!

Example Submission: 120517490

Other problems to try:

https://mirror.codeforces.com/contest/190/problem/E

http://www.usaco.org/index.php?page=viewproblem2&cpid=765

https://mirror.codeforces.com/contest/1508/problem/C

Thanks for viewing!

Lol

Hey orzosities. Sorry to create another blog which will most likely be catered to me and a select group of people.

I need help. I've been struggling for a while on practicing. In addition to the enormous demotivation I've been feeling recently due to a mix of covid, isolation, and the lack of improvement, I feel that I've hit a huge roadblock in problem solving. I'm in a crossroads in terms of what or how I should practice.

Towards the beginning of my competitive programming career, I spammed 800s. I feel like this is a common theme with beginners. This worked until I reached around 700 rating (I started hovering there). After, I felt like I was going nowhere and started to look for advice. I found a discord which helped me and met some really cool people there. I also found new youtubers and started to learn Data Structures and Algorithms. I started practicing harder problems (1100s and 1200s) and eventually they became trivial to me. My rating at that point started to improve as well. However, as I tried harder problems, they seemed at a completely different level of thinking and I started to become interested in Data Structures. Long story short, I learned and gained knowledge of various data structures over a couple of months. I also started to do USACO and started to practice silver problems. I have also learned many useful algorithms (I'm not going to list them here). So here I am. To conclude, although I am able to solve 1500 rated problems semi-consistently (and 1200s / 1300s consistently), I feel like I am not making any progress in terms of contests.

So to make a long, useless blog short, what are my next steps? Practice implementation, math, or what? 1200s and 1300s seem trivial to solve, and many data structure problems (within reasonable range — under 1800?) are also trivial. Yet, I am hardly making progress in contests. Any (and I mean literally any) advice would be helpful.

TL;DR (problems above my rating level seem trivial, yet I can't solve them consistently in contest. (Should be plural? Idk) Any advice?)

PostScript: Sorry for my terrible grammar.

It seems that many people had the same idea for B.

I got my code skipped during System Tests, even though I wrote it by myself. Although I submitted twice, it sucks that I'll get much fewer points than I had originally.

Has this happened to anyone else?

EDIT: I apologize for my idiocy, and for making a pointless blog. I was unaware that submitting a solution twice can get the first submission skipped.

Hey Codeforces!

I've been wondering this for a long time, but could never find a straight answer.

According to String substr on cplusplus.com, the complexity of substring is mostly linear but is unspecified. I thought this was interesting, but never thought much of it. After all, a string is just an array of characters?

I thought this at first until I found another post that claimed that C++ string was implemented with the Rope data structure.

So i tried the following code (on my Linux system).

#include <bits/stdc++.h>
using namespace std;


int main() {
	int t; cin >> t;
	string s=string(int(2e5), 'a');

	while(t--) {
		string v = s.substr(0);
	}
}

Surprisingly, this code took less than a second after entering t as 200000.

Now, I tried a true N^2 approach to test my code against the one above.

#include <bits/stdc++.h>
using namespace std;


int main() {
	int t; cin >> t;
	

	while(t--) {
		for(int i = 0; i <= 1e5; i++) {
			continue;
		}
	}
}

After entering t as 200000, the program takes 15 seconds (without compiler optimizations).

So, which one is correct — Rope or Char Array?

Thanks in advance.

As tensions in the Middle East grow, I want to strongly remind everyone to stay respectful on the website. People are struggling right now and being insensitive will only make matters worse. Racism is racism — stereotypes are stereotypes, no matter if the person is Arabian, Jewish, White, Black, Hispanic / Latinx, Asian, or any other ethnic group. We are all people, with different dreams, aspirations, and hopes. Please, don't bring up issues that aren't needed to be brought up on a competitive programming website.

Thanks, Have an awesome day

Dwight (tdpencil)

What the title says.

Like honestly, if you want them to learn their lesson, don't make a post about how justice is served and acting like Seryu Ubiquitous, report their submissions or message the contest administrators about cheating in the contest. Cheaters wondering why their plagiarized submissions are skipped every contest and they don't know why will probably be impacted more than making a post and giving them a platform to make excuses.

If you clicked on this, you must be thinking this must be related to the previous contest that happened, not hours ago.

2020 is a year that no one wants to relive and many of us have lost opportunities, our goals, our jobs, our livelihood and our family members. We have been stuck in quarantine and have watched the world turn from inside our living rooms.

I believe that the best way to end the year is to remember all the past experiences we've had, and to appreciate how this year could be a lot better instead of a lot worse. We could all make each others' years more enjoyable.

Maybe you could do this by saying "Hi" to the Neighbors, or making up with your petty husband, or perhaps making a card for your grandparents, maybe talking to your parents for the first time in five years. I'm not going to judge you if you don't, and this year has taken a lot from us regardless.

If you are feeling lonely, chances are someone else is feeling lonely. If you are homesick, chances are someone else is too. This year has changed the world forever, and left a scar that will never heal. The least we could do is live our lives out to the best that we can right now, because we only live once. Why not try to make it last?

PS: if you need someone to talk to, I found a post online with a link can connect you to others for free. Very Well Mind — Online Therapy