Currently, blogs on Codeforces are sorted by the most recent comment. This system causes highly irrelevant blogs that might be ten years old to be shown on the Recent Actions tab, just because some random user necroposted. I believe Codeforces should improve its blog algorithm to ensure that only the most relevant and trendy topics are shown. Who is with me!

Two contests are scheduled six hours apart this Sunday. Is this for real or will one of them be eventually rescheduled? I've never seen something like this before...

I'm not sure if it's just my wifi, but I've noticed that submissions are taking a bit longer to process recently. Even when I'm not in a competition, it can take over a minute to get a verdict, which is quite frustrating. I understand that during a competition, it's expected for submissions to be slower due to the high volume of participants, but even during practice sessions, the delay persists. I'm curious if anyone else has noticed this issue?

EDU Round 146 is unrated which means there will be many downvotes. I got up at 7:00 AM to take this contest and was extremely frustrated when it took me more than twenty minutes to submit my solution to problem B. Even so, the authors put a ton of time and effort into the contest and were still willing to make it unrated when it became clear that there were substantial issues. This is admirable, and we shouldn't downvote them to hell for doing what is right after encountering issues that were mostly beyond their control.

Hi everyone,

I've been trying to solve this problem for a while, but keep getting TLE.

The problem requires a range-assignment segment tree, which I copied almost exactly from CP Algorithms.

And yet I keep getting TLE. Can anyone please help? This is my most recent submission,

Thank you,

• Simon

You have months to prepare the contest. Why isn't the editorial written beforehand?

Can anyone please help me understand why my code gives TLE?

https://mirror.codeforces.com/contest/1796/submission/195509093

I basically followed the editorial exactly but used memorization instead of bottom-up.

In general, is bottom-up faster, or is my implementation just flawed?

Does anybody know how to use the g++ compiler in XCode IDE? I have a version of g++ on my local device but I can't seem to switch the compiler in XCode. When I look at build options only the default compiler is available and I can't switch it.

I'm trying to use the <bits/stdc++.h> header and policy-based data structures so if anyone knows a way to do that without switching the compiler, that would be cool too.

Thanks!

Hi Everyone!

I hope you're all having a great day!

Last week, I participated in NAQ 2023. After the contest, I've been trying to upsolve Problem J (Platform Placing), but I keep getting WA on test case 6.

Here is a link to my code.

And here is a high-level summary of my code (problemB()):

1. Read the input. Add (1e18) and (-1e18) to the set of platforms to represent extra space for the first and last platforms.

2. Sort the array.

3. Iterate through and expand the current platform as much as possible.

4. Add the length to our result and record the increased size of the platform.

This is similar to the greedy approach that the contest authors offer, but for some reason, it continues to fail! If anyone could help me out with what is going wrong here, it would be very appreciated.

Thanks!

Simon

Hello Codeforces!

After Tuesday's contest, I decided to learn a little bit more about Sparse Tables. While solving this problem on Codechef, I came across some code that has been heavily confusing me for the past few hours. Basically, when I initialize the sparse table "table" as an array, everything works great. But when I initialize it as a 4-D vector inside the function "build_table", the code gives segmentation fault on large test cases! I've attached both submissions below. Any help would be extremely appreciated!

Submission 1 (Array, AC)

Submission 2 (Vector, Seg Fault)

Thanks! -Simon

Hi everyone,

I was recently working on the Timus problem "The Debut Album". While doing so, I came across something very odd: my nlog(n) algorithm is way too slow! To summarize the problem:

1. You must assign n elements either 1 or 2
2. There can be no more than "a" 1s in a row or "b" 2s in a row
3. How many assignments can we make?

The solution I came up with was DP, where each state = {element number, count of the previous 1s in a row, count of the previous 2s in a row} --> {i, cntA, cntB}. Now, I understand why, in the worst case, this algorithm is ineffective. "n" can grow as large as 50,000, and "a" and "b" can get as large as 300 --> 50000*300*2 states (multiply by 2 because if cntA is positive, cntB must be 0 and vise versa) --> 3*10^7 * log2(3*10^7) is clearly way too much. But even when I reduce "n", "a", and "b" on my own computer to 50000, 30, and 30 respectively, the program still takes upwards of 10 seconds to run, which is ~10 times longer than you would expect (3*10^6 * log2(3*10^6) < 10^8). What's going on here?

Note: I do know the correct solution, I'm just wondering why this implementation takes so long for the future.

Here is my code: https://codeshare.io/loWmNR

Hey everyone,

During today's contest, I realized something weird about the new test case format: when you copy a test case by pressing the "copy" button, there's no newline at the end! This means that your first output will be on the same line as the last input, and you need to hit enter to get the last output to work. While this is obviously not a huge deal, it was a little weird to me and personally, I much preferred the old format.

Am I just a fool? Please tell me if so, I want to go back to the way things were! If this is just a feature of the new format, then please MikeMirzayanov: bring the newline back!

Hey Everyone,

I'm trying to solve problem 1679D, but I'm getting TLE despite using the strategy suggested by the editorial. The basic idea behind this problem is that you have a graph and each node has a weight. You need to find the path with the minimum-maximum weight, where the path must be at least k vertices. The strategy suggested by the editorial is to:

1. Binary search for the optimal weight
2. Verify potential weights by creating a graph of only nodes with that weight or less...
3. Perform a topological sort on that graph, use that sort to calculate the maximum path, and return true if that maximum path exceeds the minimum vertices k.

Unfortunately, when I implemented this strategy, I got TLE. Any help in understanding this problem would be greatly appreciated!

Code: https://mirror.codeforces.com/contest/1679/submission/166858130

Hey everyone,

First off, I'm finally an expert! Thank you to everyone who has responded to my previous blog posts, your input helped me grow as a competitive programmer greatly!

Now, onto the actual question. What is the time complexity of using the "union" and "find" operations with an array-based union-find algorithm? First, let me put some pseudo-code of the union-find algorithm so that my ramblings will make more sense.

// We initialize the array such that each node is its own parent

 array = [0, 1, 2, 3, 4, 5... n]


 // Find the "root" of a node

 function find(index):

      while (array[index] != index)

           index = array[index]

      return index


 // Join the "roots" of two nodes

 function union(a, b):

      array[find(a)] = array[find(b)]

Please someone correct me if my implementation is wrong or if there's any way I can improve my pseudo-code. Now, onto the actual question.

Let's imagine you have a straight, directed graph with randomized node order. For example: 3 --> 5 --> 1 --> 2 --> 4. I speculate that the time complexity of generating the union-find array is at worst O(n^2) and that once the array is generated, the time complexity of finding the root from any given node is at worst O(n). Let's go through the example I provided, assuming that we join nodes starting from the lowest node (1), then the second lowest (2), etc.

Init: [0, 1, 2, 3, 4, 5]

Step 1: [0, 2, 2, 3, 4, 5] // Join 1 and 2

Step 2: [0, 2, 4, 3, 4, 5] // Join 2 and 4

Step 3: [0, 2, 4, 5, 4, 5] // Join 3 and 5

Step 4: [0, 2, 4, 5, 4, 5] // 4 has no outward connections

Step 5: [0, 2, 4, 5, 4, 1] // Join 5 and 1

At this point, if we want to query the third node for its connected component, the complexity will be O(n), because we must traverse the array 3 --> 5 --> 1 -- > 2 --> 4. Furthermore, if every node was connected to every other node, then preprocessing would take O(n^2) complexity!

This is really bad, but union-find is such a popular algorithm, I feel like I must be missing something! What is going on here?

Hey everyone,

I recently wrote my first segment tree program. While it works properly, the tree itself is extremely slow, especially in the build phase. For instance, with just a sample size of 20,000, the tree takes 3.9 seconds to build on Codeforces! I'm wondering what I can do to speed it up, or if slow build times are the natural result of using object-based trees. Also, any general tips for writing trees and increasing their speed would be greatly appreciated!

Here is my code. It takes two numbers as input: t (the number of queries) and n (the size of the dataset). Both queries and the dataset are generated randomly. Please let me know if you have any questions about how the code works.

Code: https://codeshare.io/8pBOLZ

Hello Codeforces friends,

I am currently befuddled by a TLE I received on Problem 365A, "Knight Tournament". Essentially, the problem provides the user with a series of range queries, Each range query represents a set of "knights" that participated in a "tournament round", with a "winning knight" conquering every other knight in the range. The problem asks the user to spit out a list of the conquerers of each knight. The critical difficulty is that multiple queries might have overlapping ranges. My solution was to keep a constantly updating set of knights in the tournament. Each time a knight was conquered, I'd remove them from the set. Unfortunately, while my solution passed the correctness tests, I got a TLE on test #11. Could anyone please tell me what I did wrong?

You can find my code here: https://mirror.codeforces.com/contest/356/submission/162602701

Hi Everyone,

Yesterday I made a post about getting a TLE on Codeforces round #788, problem B. Today I'm making another post, about getting a TLE on Codeforces round #788, problem C :). Once again, I have what I think is a nlog(n) solution, and while it's able to pass the first two pre-tests, it doesn't solve the third in a short enough period of time. I posted my solution below along with a short description of how it works, and I would highly appreciate any feedback on what I did wrong and how I can improve.

Thank you.

Solution: https://mirror.codeforces.com/contest/1670/submission/156244281

Explanation:

1. Read the input into three vectors, "a", "b", and "c"

2. Create an adjacency list ("graph") between the elements of "a" and "b"

3. While doing so, mark any elements of "c" with values other than 0 as "bad" in hash_map

4. Count the # of cycles in the "graph" using DFS and a stack; don't count cycles that include "bad" nodes

5. Iteratively calculate 2^(# of cycles) and use modular arithmetic to guard against overflow

I think the primary issue with my code is inside the DFS, but I don't know why because I think that by marking visited nodes, the complexity shouldn't exceed nlog(n).

Hi All,

I recently competed in Codeforces Round #788 (Div. 2). I was confused by Question B, in which I got two TLE failed submissions. I managed to eke out a solution almost two hours in, but it just barely passed the time constraints, with a runtime of ~900 ms on a 1-second limit. The reason I'm confused is this: from my perspective, my initial solutions were O(n)log(n) (using a set) and O(n) (using a hashmap), and both failed the pre-tests with only 2*10^5 inputs. In addition, from what I can see my final solution is also O(n) (using a character-mapping array), and it just barely passed the tests. I've linked my 3 solutions in this post, and would highly appreciate any feedback on why my solutions were so slow, and how I can improve for the future.

Thank you

Successful:

• https://mirror.codeforces.com/contest/1670/submission/156116681

Failed:

• https://mirror.codeforces.com/contest/1670/submission/156104237

• https://mirror.codeforces.com/contest/1670/submission/156111007

If you're wondering about the differences between these submissions, the primary change I made was the data structure used to represent "special" characters. In the successful submission, I used an array ("letters"), while in the failed solutions I used a set and a map (both named "v") respectively.