Confused about Complexity of Contest 362 Div. 1 Problem A:

→ Pay attention

Before contest
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

Confused about Complexity of Contest 362 Div. 1 Problem A:

Revision en2, by Noble_Mushtak, 2016-07-16 00:35:30

Here is my analysis of the solution to Contest 362 Div. 1 Problem A:

There are $\text{[math]}$ edges per query.
Each edge takes $\text{[math]}$ to process. There are $\text{[math]}$ added every query and O(q) queries, so we have $\text{[math]}$ edges, meaning each edge is $\text{[math]}$ to process.
Finally, there are O(q) queries.

This gives us $\text{[math]}$ overall. However, the editorial does not have the $\text{[math]}$ term and simply has $\text{[math]}$ . How did they get rid of the $\text{[math]}$ term in the analysis? Did I do something wrong here?

#362 (div. 2) c, analysis

History

Revisions

	Rev.	Lang.	By	When	Δ	Comment
	en2		Noble_Mushtak	2016-07-16 00:35:30	104	clarified answer
	en1		Noble_Mushtak	2016-07-16 00:33:09	666	Initial revision (published)