Kevin Sheng SansPapyrus683

"Domination". Look it up.

— Scout, TF2

after the dec contest, i have come to the conclusion that i suck a** at dp
so i was grinding cf and i came upon this problem that had the tag dp
but my solution was anything but that, so lemme just share my sol

hi
december contest ptsd again
this problem again

since the problem explanation is too complicated, i'll just let you read the problem yourself, there's no way i'm going to explain it myself

ok i'll assume you read the thing

anyway just the first thing i did was write a brute force python script to

AHAHAHAHA I THREW DEC GOLD SO HARD
only managed to cumulatively solve one problem, that's how sad i am

my friends kept on asking me for help on this one silver problem, and to be fair, it is pretty hard
the fact that benq's editorial reads like some post-college math paper doesn't help either

(my solution requires knowledge of prefix sums tho)

but without further ado, here's my solution

usaco time
i've been doing some old problems that i failed at before
and one of them was this problem, and i thought the solution was hot garbage (no offense benq) so i'm deciding to write my own that actually makes sense

so
we have 10^5 line segments, standard stuff
and we want the sum of the complexities of each segment, where the complexity is the number of connected components in the union of a segment

Translation credit to Kaz Nakao

In the country of IOI, there was a railway mogul JOI that owned all of the railroads.
However, JOI has passed away and the railways he owns are to be distributed as a split inheritance.

In IOI, there are $N$ cities and there are $M$ railroads that connect the cities.
The cities are numbered $1$ to $N$, and the railroads are numbered $1$ to $M$.
A railroad $i$ runs between city $A_i$ and $B_i$ in both directions and generates a distinct profit of $C$ yen.
There may be several lines between the same two cities.

Translation credit to Kaz Nakao

You are ordering $N$ matryoshka dolls. They each have a diameter $R$ and a height $H$. A matryoshka doll will only fit inside another if the former's height and width are both strictly less than the latter's.

You also have $Q$ queries. Each of these $Q$ queries has two arguments: $A$ and $B$. For each of the queries, you need to answer the following question: Among the set of dolls that have minimum diameter $A$ and maximum height $B$, how can you fit these dolls in each other, making "towers" of dolls, so that the total number of "towers" is minimal?

alright
time for this unholy problem

oh my god i want to kill the author of this

not even joking
this problem was so hecking hard

but anyways, i want to make you suffer less on this problem if you decide to give up
so we have a normal tree w/ at most 400 nodes and we want to find a subtree of k nodes such that the number of edges connecting it to the rest of the tree is minimal

hi it's me again

i should probably make a cf blog or something but the people on there are more unpredictable than my history teacher

so i came upon this problem and god the editorial was awful

so we have a tree with nodes and values, normal crap
and they want us to find how many subtrees have a sum of t (t <= 100)

wow another solution in just a day
_{(does anyone even read these)}

but anyways i did this, and it basically gives you an array of 1e5 elements and a target n <= 1000
and then it asks you to find the smallest segment that has a subset which sums to that given target

this problem is really stupid because it asks for like this one really niche method of using two pointers

	#include <deque>
	#include <iostream>
	#include <map>
	#include <set>
	#include <unordered_map>
	#include <unordered_set>
	#include <vector>

	template <typename T1, typename T2>
	std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& pair);

Kevin Sheng SansPapyrus683

oh my god i want to kill the author of this

a simpler problem