SansPapyrus683

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

SansPapyrus683

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

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& vec) {

SansPapyrus683

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

SansPapyrus683

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.

SansPapyrus683

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?

SansPapyrus683

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

SansPapyrus683

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)

SansPapyrus683

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

a simpler problem

SansPapyrus683

hi i'm back with another solution thing
whatever you like to call it

so this time it's this problem from the codeforces educational portal or whatever

so this is a standard dsu problem, except this time you need to

1. get the value of a certain node
2. increment all the values of a set (given by a certain node) by some value

SansPapyrus683

first editorial that i can be informal in hooray

anyway the editorial is for this problem it's kinda misleading- they say that the prominence is h_min, when it's really the elevation - h_min

but anyways, this is a dsu problem, if dsu was awful and something you wanted to rage at every night (the 2d aspect doesn't make it any better)
i'll assume you know enough about dsu to not die on a simple problem about it

so you add the squares in one at a time from highest to lowest and link them to any previously added squares with some