Alternative editorial to 2019 USACO Gold February, Problem 1 - Codeforces

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
26:37:33
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

→ 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	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

Alternative editorial to 2019 USACO Gold February, Problem 1

Revision en1, by nsqrtlog, 2022-09-06 16:22:47

The official editorial is not asymptotically optimal and involves an advanced concept that usually does not appear in USACO Gold. I derived a relatively "low-tech" and faster solution, which I will describe below.

Tags

usaco, segment tree, euler tour, lca

History

Revisions

	Rev.	Lang.	By	When	Δ	Comment
	en12		nsqrtlog	2022-09-14 02:47:08	177
	en11		nsqrtlog	2022-09-07 05:33:35	397
	en10		nsqrtlog	2022-09-07 02:00:34	0	(published)
	en9		nsqrtlog	2022-09-07 01:59:58	50	Tiny change: 'oiler>\n\n\nThank ' -> 'oiler>\n\nThank '
	en8		nsqrtlog	2022-09-07 01:57:22	64
	en7		nsqrtlog	2022-09-07 01:53:46	25
	en6		nsqrtlog	2022-09-07 01:52:48	16	Tiny change: 'b19.html) is not as' -> 'b19.html) to this problem is not as'
	en5		nsqrtlog	2022-09-07 01:52:24	4	Tiny change: '------\n\n[Problem l' -> '------\n\n### [Problem l'
	en4		nsqrtlog	2022-09-07 01:49:32	168
	en3		nsqrtlog	2022-09-07 01:46:30	4736	Tiny change: 'e std;\n\n\n#defin' -> 'e std;\n\n#defin'
	en2		nsqrtlog	2022-09-07 01:20:16	1353	Tiny change: 'ion:\n\n' -> 'ion:\n\nfor the sake of convenience, let $\sum\limits_u^v$ denote '
	en1		nsqrtlog	2022-09-06 16:22:47	407	Initial revision (saved to drafts)