### SAT2020's blog

By SAT2020, history, 5 weeks ago,

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

• +4

By SAT2020, history, 4 months ago,

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!

• +184

By SAT2020, history, 4 months ago,

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!

• +6

By SAT2020, history, 5 months ago,

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?

• 0

By SAT2020, history, 5 months ago,

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.

• +5

By SAT2020, history, 5 months ago,

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://codeforces.com/contest/356/submission/162602701

• +2

By SAT2020, history, 7 months ago,

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.

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).

• -2

By SAT2020, history, 7 months ago,

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:

Failed:

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.

• +3