Learning to problem solve (or, notes on olympiads)

usaco third contest plat! 2026-02-21 here we go. nonzero score fr

12:26 start. don't stop exhausting ideas.
hm is the complex notation just to specify shape/plane formally? or actually need to work in complex
2e5 points
find sum across all pairwise distances
uh

12:31 let's read on for now
N=2e5 enemies in a line
v=[0,1e9] health
find minimum operations clear all
one oper = decrement i-1, i, i+1 if alive 

for 4/10 tc, just output min # of oper
for 4/10 tc, output construction of runs, where R<=2N (always exists?)
- yea makes sense w/o min constraint you can always just use N runs max
for last 2/10 tc, R capped at max_allNlists(min run count)

let's find min # first w/ no constraint on runs
seems like a simple problem, prob deceptive
order doesn't matter. can group all opers on same i together. <- FALSE
anything that *has* to happen?
- v[0]<=ans[0]+ans[1]
sample is 6,1,7: 1+11=12
no order does matter. we can only choose i when v[i]>0
any other first move would give 13

12:56 third statement short
constructive too lmao
create n=2e5 arr satisfying Q=2e5 constraints of the min (or max) over a subarray
i feel like this would be a canonical problem
lets assume min. should be symmetric.
sort from biggest to smallest constraint?
sort by right endpoint?

1:25 back from walk. made some progress
- visualize as grid of squares N wide, up to 1e9 tall.
- start out blank. we must construct array in gray
- Q horizontal 1 block tall strips of red at varying heights
- in construction, there cannot be white below a red. must fill up to red. and at least one exactly at the red.
- so higher reds take precedence. if one above another, must fill up to top one.
- so if higher red entirely covers lower red, it's impossible.
then we can just sort by lowest to highest, greedily update since later ones must be reached, and track for each N spot which constraint it represents
then at the end check if all constraints are represented.
can't be this simple right??
oh yea it's QN to update the N spots every constraint
then just use range update BITS?
simulate on samples
OH bro i misread. EACH constraint has a DIFFERENT type (max or min).
- ok let's add green to represent max constraints
- should be symmetric. lower ones take precedence
- how do reds greens interact?
- if they overlap and red higher than green, no solution
- what if equal heights? oh yay all k[i] distinct
- reminds me of HILO. for that, i thought needed complicated DS but really js maps enough.
- helps to imagine with motion. green is blockade that cant raise elements to pass
oh cool the only reds solution is enough for 4/10. impl that when 90 min left if not else.
2:13 back again
	still unclear: how to balance reds and greens?
	ideas:
		instead of looking at intervals, consider at every x individually
		can simplify to only use the tallest red and lowest green at each point
			the picture this paints is dashes of red below and green above. never flipped
		but a red cut in segments by a red above doesn't mean we have to satisfy every segment. one is enough to satisfy entire constraint
		so how to balance which x to use for its red constraint and which green?
		dp?
lets impl the 4/10 for now. go fast.
	easy way to handle min/max? can we just flip everything from x'=1e9-x then flip back at the end?
	process constraints from lo to hi
		update a[l[i]...r[i]] to k[i]
	for all i, check if all constraints are represented.
	wait this is too simple doesn't need range update impl. 
	initialize a[] to -1
	process hi to lo
		only update the empty columns so far
		keep track of unseen in set of indices
		can just bsearch for first j where j>=l[i] then iterate until r[i]<j
			set a[j]=k[i]
	that's amortized Q+N with some log factors
	run through and check if all k met
	set the rest -1s to 0
	done ok impl fast
	

3:07 ok 4/10 as expected. REMEMBER SPACE SENSITIVE THIS ISN"T CF
back to p2
lets visualize as grid of blues this time
default way is attack every single hp so total would be sum(v[i])
but we can reduce by 2 every time we oper at i where either side is also nonzero
seems like dp

3:15 maybe continue p3. i feel like closer.
at every x there's the tallest red L and lowest green R as bounds, and can choose to set a[x]=one of L or R
the issue is how to choose which of L or R, so that overall we satisfy every k
what about consider for single constraint instead of by x?
	we have to find somewhere from l to r to set to exactly k
	this has to be a place where L[x] is EXACTLY k <- considering t is 1 rn
	still have to assign in a way that each k appears at least once
what about iterate through x, assign, then backtrack?
so default we use a[x]=L[x]
but no clean way to backtrack
dp? maybe encode with graphs somehow?
we just need to decide at each point to either set it to L[x] and R[x] i feel like this is canonical

3:35 continue p2 
is there anywhere to anchor? what HAS to happen?
we have to end up reducing all to 0
so guaranteed i=0 must end up with 0
what if we try to flatten all in a given prefix first. bc long range won't affect anything.
so left to right reduce to 0.
assuming 0..i-1 are all gone, we need to flatten i
but we'd prefer to flatten i+1 because that also reduces opers in the future
wait so is it just greedy??
keep using i+1 until i or i+1 is gone?
3:09 nope
oh didn't impl right
still nope
but why tho?
	this should work by induction (?)
	sample passes
	edge case?
bruh
its alright at least nonzero today. hopefully get to go us open.

2026-01-31 usaco gold feb
solve 1 pb by 1pm, 2nd by 2pm, 3rd by 3pm. ONLY attempt subtask if need in last hour
12:07 lock in

p1 
N=5e4 barns
a_i, b_i<=1e9
can oper exactly k=1e18 times: --a_i, ++b_i
minimize max(a)-min(b)

dp or sorting?
what why'd you want to oper at all it only makes things worse
so we want to minimize damage after k opers
nvm we want to minimize a maximize b
visualize
if just a, sort by a and keep decrementing from the back
if just b, sort by b and increment from front, or smallest
like haircut across the top (negate b)
the order we apply oper on one of them is more or less set (except within a single haircut)
if a,b independent, we apply oper onto whichever of a or b has cheapest next haircut greedily
since not independent, sometimes single oper contributes to both
binary search on the final imbalance? 
but that's silver
to make any progress, we *have* to apply next greedy haircut
it's just sometimes we can save opers

how to balance?
at each cell in a, quantify how many it would take for the corresponding decrement in b to help?

12:26 let's read on first
N=2e5 undirected connected graph
M=2e5 edges, w/ weight c in a..z
f(a,b)=smallest string by weights from a to b, including cycles
- wait is aaa or dd smaller? can you just keep prepending "aa" in a cycle to lower order?
find length of f(1,i) for 1...N or -1 if infinite
- ohh yes it can be infinite sometimes
try samples
ok we want to avoid all later letters at all costs if possible
if path ever increases in precedence it can always be made infinite
as long as there exists?
not unless there's an even lower precedence one
so we look for the minimum path *not* using cycles, and it's -1 if either:
- along the path it ever increases
- has an edge right along the path that is lower than what would be next on that path
so dijkstras from root to find min path, and stop exploring one route if either condition met
and unvisited nodes end up with -1
does this work?
first cond easy to check but how to check 2nd, if don't know path yet
wait we just ONLY go down paths that're strictly decreasing
oh and this can contain the first case too?
- since if we only advance frontier where next node is smallest, 
- and global smallest contains a visited node
- then it ends up stopping naturally
so this is just simple bfs where we only advance frontier with weights equal to global min in entire frontier
impl fast quick
YES
broo already 1:46 cmonm cmon

1:47 
simulate p1? 
the main thing i have to balance is how many opers to use in a vs b
to make any progress i have to haircut a layer either a or b
make pref sum for every number of haircuts how much it'd save for the other?
if the other had to use the remaining in k
how much is saved still depends on how much is eventually used
binary search? 
hm how check given final diff, possible to achieve with k opers?
have to distribute among a and b
imbalance is x=max(a)-min(b)
so find aa and bb where aa-bb=x and a<=aa and b>=bb
bb=aa-x
a<=aa, b>=aa-x
so we want to find cheapest aa to achieve and see if costs less than k
what's cost?
given aa it's sum over max(a-aa,bb-b,0)=max(a-aa,aa-x-b,0)
how to find aa that minimizes that? 
afford to simulate? 
log2(1e18)=60
we can simulate the summing but range of aa is still too wide
broo adfsf 2:25
so close ummmmm
aa is like distance to a and x+b so visualize?
except have to deal with signs and 0
how
is cost monotonic wrt aa so binary search again?
no def not the best aa occurs somewhere between extremes
so is cost like parabola?
- ^^^^^ CHECK BACK ON ASSUMPTION 
- this only feels right
can we binary search for min on this?
actually yes wait derivative is monotonic so find first aa where f(aa+1)>f(aa)
so we can do 
- binary search on x
- bs on aa
- iterate through N to sum
60x60x5e4=1.7e8 that's tight but should work hope
bruh 2:38

3:19 pls pls
cmon where's gradngi server
p3
N=5e5 farms with directed edges 
F<=farmers 

noo wa 4/13
bruh how
is it not parabola?
at least didn't tle
but it's only the later testcases huh
OH OVERFLOW??
summing over 5e4 1e18 would
pls pls

N=5e5 farms with directed edges from each farm
F<=farmers each starting at distinct farms
for all starting bessie locations b, find max number of rests without getting caught
just get subtask
simulate all nights?

LETS GO LMAO IT WAS OVERFLOW

need at least subtask 2, just 1 is not even 700
bruh 30 minutes

we only need to look at bessie's current component
if no farmer obv -2
directed graph must be cyclic?
permutation has to be, but didn't specify all a_i distinct
has to be there's still finite states
but only evenually
like 2,3,4,4
so we can simulate farmer movements until they repeat
and track for each farm for what times it's safe for bessie to stay
once reach cycle, does she have to follow a farmer's movements?
wait as long as she's ever caught we say -1 so she has to reach a cycle
she can't reach if the safe intervals for all farms don't overlap at some point
as long as they overlap she can keep moving
and as long there's an interval that's long enough to rest in the cycle she has inf -2
only when she has to move every night the answer is her rest times before entering the cycle
so this is like simulation with dfs
bruh it'll take so long to impl
wait is there no dp this contest?
is this dp possibly?

man too slow again