Qualified's blog

By Qualified, history, 7 hours ago, In English

Recently, I stumbled upon Rascal's Triangle. You can read more about it here. Basically it is very like Pascal's Triangle but a bit different. I know that there is a $$$O(n)$$$ solution for Pascal's Triangle. I would want to calculate the $$$nth$$$ row in $$$O(n)$$$ mod $$$998244353$$$. Help?

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By Qualified, history, 3 days ago, In English

NOTE: This problem is NOT interactive
I was doing some problems of SlavicG and ssense's Unofficial Div 4 round. This problem was causing me with some weird Idleness Limit Exceeded. 99582268. After being Sherlock Holmes for a few minutes, I fixed the problem and 99582838 is AC. The weird thing is the $$$dbg$$$ macro. After commenting all of the dbg's out, it got AC. I am wondering why is this. Shouldn't it be outputted to the standard error stream? Why am I getting this idleness limit exceeded?

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By Qualified, history, 5 days ago, In English

With school starting around the world, that means less time to participate in contests! The weekends are the best time for us students to participate and many times the time slots are left blank! Contest writers should consider moving contests to weekends where more people could participate and have fun! I could point to many contests where Sunday has a contest but Saturday doesn't or vice versa. Contest writers, if you see this, please consider moving contests to the weekends.

Read more »

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

By Qualified, history, 8 days ago, In English

What is the relation between ABC's and ARC's. Like ARC's problem A is idk ABC's problem D. Help is appreciated.

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By Qualified, history, 12 days ago, In English

If you ever used AtCoder, you should know about its many features. One of the features is running your program on all of the testcases and then displaying how much WA's, how many AC's, how many RE's, etc. I think that this feature should be implemented in Codeforces. You can have the option to turn it on or turn it off.

Why Would I Want It

I recently saw Errichto use this feature of AtCoder to check if his thought process is right before trying to optimize the code. I think that he was trying to do Problem E from AtCoder Grand Contest 48. I also believe that many people like Errichto would also want to see if their thought process is right before continuing on to optimize the code.

Please share your thoughts in the comments below.

Read more »

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

By Qualified, history, 2 weeks ago, In English

Here is the problem.

Code

The factorization algorithm is taken from KACTL, same with the Miller-Rabin and the modmul and the modpow.

My thought process:

If we take each pair and then prime factorize each of the numbers in the pair. Then take the union of those prime factors and then for each union, we count the number of primes and if there are $$$n$$$ of those primes in the pairs then, at least one number from each pair will be divisible by that number.

Complexity

Since the prime factorization is $$$O(n^{\frac{1}{4}})$$$, and we are doing $$$O(n)$$$ of them and there are at most 30 prime factors for a number $$$\le 2 \cdot 10^{9}$$$, the complexity is about $$$O(n \cdot n^{\frac{1}{4}})$$$ or $$$O(n^{\frac{5}{4}})$$$. Also, I didn't add in the set's insert which works in $$$O(log(n))$$$, but I don't think that that would matter much. This complexity should suffice for $$$n \le 150,000$$$

Please let me know if there is a section where it is not clear. Thanks for reading the blog.

Read more »

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

By Qualified, history, 2 weeks ago, In English

The title prolly ain't clear at all. You are given a string $$$s$$$ and a string $$$t$$$. For every substring $$$s$$$ of length $$$|t|$$$, you are to find the number of different characters between the substring of $$$s$$$ and $$$t$$$ in $$$O(n \cdot log(n))$$$ or less. It is guaranteed that $$$|t| \le |s|$$$.

Example: s: abac t: ag output: [1, 2, 1]

s: adfjaasd t: asdf output: [3, 4, 4, 4, 3]

Don't just downvote, tell me where I should improve or what the answer to my question is. Pls, my contribution is already too low (-75).

Problem statement: 1196D2 - RGB Substring (hard version)

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By Qualified, history, 5 weeks ago, In English

Note: Factors and prime factorization are two different things. The factors of a number are the numbers that are divisible by it. Example: 12: {1, 2, 3, 4, 6, 12}.

Read more »

 
 
 
 
  • Vote: I like it
  • -20
  • Vote: I do not like it

By Qualified, 6 weeks ago, In English

When I urgently need help with a question that I am having, this message appears frequently when I try to write more than 1 comment in 10 minutes. Although I understand that this rule is put in place to stop spammers from spamming too much comments, I do believe that it could help many people if we change the time of this feature. Maybe we could reduce from 10 minutes to 5 or even 3. Thoughts?

Read more »

 
 
 
 
  • Vote: I like it
  • -25
  • Vote: I do not like it

By Qualified, history, 6 weeks ago, In English

I know that using Manacher's algorithm, we can find all pairs ($$$i$$$, $$$j$$$) such that s[i $$$\dots$$$ j] is a palindrome. This article on cp-algorithms uses 2 vectors, one in which the $$$i$$$ is the center of an odd length palindrome, the other in which the $$$i$$$ is the latter of the 2 middle elements of an even length palindrome. But how do we convert this information into a vector<pair<int, int>> where the pair represents the boundaries of the palindrome substring?

Read more »

 
 
 
 
  • Vote: I like it
  • -23
  • Vote: I do not like it

By Qualified, history, 7 weeks ago, In English

I want a data structure(range maximum query with lazy updates) that supports 2 queries. One of them is an update in which we update all the elements from position $$$l$$$ to $$$r$$$ to be equal to $$$k$$$. The second query is getting the index of the maximum element in the range $$$[l, r]$$$. For the second query, if there are 2 elements with the same value and that value is the maximum, output the minimal index. Examples: Initial array = [5, 4, 3, 9]. Do first query $$$2, 3, 3$$$. array = [5, 4, 3, 3]. Do second query(0, 3). Answer = 0. Do first query $$$0, 1, 100$$$. array = [100, 100, 3, 3]. Do first query $$$3, 3, 1000$$$. array = [100, 100, 3, 1000]. Do second query(0, 1). Answer = 0.

Read more »

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it

By Qualified, history, 7 weeks ago, In English

I have been seeing this used in people's codes and wondered what are the uses of this in Competitive Programming? I am genuinely curious.

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By Qualified, history, 2 months ago, In English

I very much like $$$cin » $$$ but want to have this fast reading integers function. How to do it? For example, I want to input multiple integers in this $$$cin » a » b » c;$$$ but the reading of integers is using the comment above.

I tried this but it didn't work.

istream & operator >> (istream& os, int x) {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		os >> -result;
	else
		os >> result;
	return os;
}

But I got this error

 error: ambiguous overload for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and 'int')
  124 |   os >> result;
      |   ~~ ^~ ~~~~~~
      |   |     |
      |   |     int

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By Qualified, history, 2 months ago, In English

I want a data structure that keeps elements in the way that you inserted them and allows erases in $$$O(log(n))$$$ or less. For example, if the initial array is empty and you insert 5, 2, 4, then the array would be [5, 2, 4]. Erase 4 and it is [5, 2]. Insert a 3 and it is [5, 2, 3]. I know that set allows erases in $$$O(log(n))$$$ and insertions but it keeps the elements in sorted order, not in the way that I inserted them.

Read more »

 
 
 
 
  • Vote: I like it
  • -20
  • Vote: I do not like it

By Qualified, history, 2 months ago, In English

KACTL ModMul. It says that it runs around 2x faster than naive

(__int128_t)a * b % M

When I ran my benchmarks with -O2, the results were similar. Am I mistaken?

Read more »

 
 
 
 
  • Vote: I like it
  • -29
  • Vote: I do not like it

By Qualified, history, 2 months ago, In English

Take a look at these two submissions

93514862, 93514890

The only difference between these two was that the data types for variables $$$n, k$$$, and vectors $$$a, hld1, hld2$$$. Instead of having them be long doubles, they were int. Now, look at the execution time! The difference is huge! The one with the ints has around 12 times better time than the one with long doubles! I knew that working with floats led to higher constant factors but didn't know that it would be that big.

Read more »

 
 
 
 
  • Vote: I like it
  • -13
  • Vote: I do not like it

By Qualified, history, 3 months ago, In English

For a lot of us, when we are introduced to a new concept, trick, or algorithm, it would be easier to learn if the editorialists would provide sample codes using the method explained. This would be very beneficial to us beginners and wouldn't take much effort. Please consider my request.

Read more »

 
 
 
 
  • Vote: I like it
  • -58
  • Vote: I do not like it

By Qualified, history, 3 months ago, In English
 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By Qualified, history, 3 months ago, In English

You are given a number $$$n$$$ and a number $$$m$$$ and an array $$$a$$$ of $$$n$$$ numbers and 1 type of query. All of the numbers below are 0 based indexing.

1) Given 3 numbers, $$$l$$$, $$$r$$$ , $$$x$$$. You add all the numbers from l to r(inclusive) by x. For example if the initial array was {5, 4, 3, 9, 2} and the query was {0, 2, 5} then the array would become {10, 9, 8, 9, 2}. Also, print the array.

After each query, store the new array as array $$$a$$$.

At the end print the array a.

m describes the number of queries being asked.

Example:

4 3
1 9 2 2
2 2 3
0 3 5
2
Output:

10
6 14 10 7

Should be less that $$$O(n)$$$

Read more »

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

By Qualified, history, 4 months ago, In English

Compare these 2 submissions, 89583867 89743418. There is no difference between them. But one that is submitted today (August 12) has 4200 KB memory improvement. Is there something that I should know?

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By Qualified, history, 4 months ago, In English

You are given a number $$$n$$$ and a number $$$m$$$ and an array $$$a$$$ of $$$n$$$ numbers and 2 types of queries. All of the numbers below are 0 based indexing.

1) Given 3 numbers, $$$l, r, x$$$. You add all the numbers from $$$l$$$ to $$$r$$$(inclusive) by $$$x$$$. For example if the initial array was {5, 4, 3, 9, 2} and the query was {0, 2, 5} then the array would become {10, 9, 8, 9, 2}

2) Given 1 number $$$y$$$, output $$$a[y]$$$. This should be self explanatory.

At the end print the array $$$a$$$.

$$$m$$$ describes the number of queries being asked.

Example:

4 3
1 9 2 2
2 2 3
0 3 5
2

Output:

10
6 14 10 7

Should be less that $$$O(n^{2})$$$

Read more »

 
 
 
 
  • Vote: I like it
  • -24
  • Vote: I do not like it

By Qualified, 4 months ago, In English

I am solving 181B - Number of Triplets. With the constraints being $$$n <= 3000$$$ and my solution supposedly running in $$$O(n^{2})$$$. Am I missing something? 88909110.

Read more »

 
 
 
 
  • Vote: I like it
  • -37
  • Vote: I do not like it

By Qualified, history, 4 months ago, In English

Long double holds 22 digits while long long holds 18 digits. Why not use long double over long long? More space, that's for sure.

Read more »

 
 
 
 
  • Vote: I like it
  • -25
  • Vote: I do not like it

By Qualified, history, 4 months ago, In English

I see this article and at the bottom, it says that modulus operators are expensive so they implemented a slightly faster version of Euclidean Algorithm. Why not make a more efficient mod?

int mod(int a, int b) { // computes a % b;
	return (a - b * (a / b));
}

Read more »

 
 
 
 
  • Vote: I like it
  • +87
  • Vote: I do not like it

By Qualified, history, 4 months ago, In English

I know that set doesn't contain duplicates, but it sorts the elements. I want a data structure that doesn't sort the elements and doesn't contain duplicates.

For example if the data structure contains ints,

Input: 5 4 1 2 5 4 9

Elements in data structure

5 4 1 2 9

Please help.

Read more »

 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it