Artificial Intelligence is one of the fastest growing sectors in the world, and with that, comes an unfathomable level of scaling. To attract investors and accommodate their massive spending, tech giants have turned to an interesting strategy: Reinvesting!
There are $$$n$$$ companies numbered $$$1$$$ to $$$n$$$, and $$$m$$$ reinvestment package. Package $$$i$$$ belongs to company $$$c_{i}$$$ and has a leniency value of $$$l_{i}$$$. A package $$$i$$$ can be reinvested into company $$$x$$$ if $$$|c_{i} - x| \leq l_{i}$$$. Each package must be reinvested to exactly one valid company, and it can be reinvested into its owner (Don't ask us how that works).
Since all of these companies are greedy cooperate giants, They don't want a single company to receive significantly more reinvestment packages than the others. Your task is to calculate the minimum number of packages $$$Z$$$ such that, under optimal assignment of the reinvestment packages, no company receives more than $$$Z$$$ packages.
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t\leq 4000$$$) — the number of test cases. Then follows the descriptions of the test cases.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n,m\leq 2\cdot 10^{5}$$$) — the number of companies and the number of reinvestment packages.
The second line of each test case contains $$$m$$$ integers $$$c_{1},c_{2},\ldots c_{m}$$$ ($$$1\leq c_{i}\leq n$$$), representing the owner of the $$$i$$$-th package.
The third line of each test case contains $$$m$$$ integers $$$l_{1},l_{2},\ldots l_{m}$$$ ($$$0\leq l_{i}\leq n$$$), representing the leniency of the $$$i$$$-th package.
It is guaranteed that the sum of $$$n$$$ and sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.
For each test case, output $$$Z$$$ — the minimum number such that no companies receives more than $$$Z$$$ packages under optimal distribution.
33 61 1 2 3 3 30 1 1 1 1 26 121 2 2 1 4 4 4 3 3 4 1 45 0 0 6 1 1 1 2 2 1 1 03 53 3 3 3 31 1 1 1 1
223
In the first test case, one optimal assignment is to reinvest the $$$6$$$-th package to company $$$2$$$. The rest of the packages can be assigned to their owners.
In the third test case, one optimal assignment is to reinvest the $$$2$$$-nd and the $$$4$$$-th packages to company $$$2$$$. The rest of the packages can be reinvested to their owners.
Oh no! Amy the pink cat is stuck in a time loop! To save her, Rover the black cat has to make a journey to The Origin to defeat Aleph-1 the evil cat!
Define a multiverse as a network of $$$n$$$ universes numbered from $$$1$$$ to $$$n$$$, with The Origin located at node $$$1$$$. These universes are connected by a set of $$$n-1$$$ undirected tunnels, each taking $$$w_{i}$$$ time to traverse. It is guarantee that all universes belongs to the same component (in other words, a multiverse is a tree).
At the start of his journey, Rover can choose to teleport to any universe $$$s$$$. Define $$$d_{i}$$$ as the number of tunnel Rover has to traverse from universe $$$i$$$ to get to The Origin. At any point during his journey, if Rover is in universe $$$v\neq1$$$, he can perform a Super Jump and teleport to any universe $$$u$$$ such that $$$d_{u} = d_{v}$$$. Super Jump cost no time and can only be performed once during the entire journey.
Unfortunately, Rover the black cat is not good at math. Therefore, he asked you to find the minimum time needed to traverse from universe $$$s$$$ to The Origin satisfying the given constraint for every starting universe $$$s$$$ from $$$1$$$ to $$$n$$$.
Each test consists of multiple test cases. The first line contains an integer t ($$$1\leq t\leq 10^{3}$$$) — the number of test cases. Then follows the description of the test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq5 \cdot 10^{5}$$$), denoting the number of universes.
Each of the following $$$n-1$$$ lines contains three integers $$$v_{i}$$$, $$$u_{i}$$$, $$$w_{i}$$$ ($$$1 \leq u_{i}, v_{i} \leq n, 1 \leq w_{i} \leq 10^{9}$$$), denoting the endpoints and the time needed to traverse the tunnel. It's guaranteed that all universes are connected via tunnels.
For each testcases, print $$$n$$$ integer $$$t_{1},t_{2},\ldots,t_{n}$$$, denoting the minimum time taken to get from universe $$$i$$$ to The Origin if Rover starts his journey at universe $$$i$$$.
331 2 671 3 3651 2 32 3 61 4 24 5 1051 2 32 3 31 4 24 5 10
0 36 360 2 8 2 90 2 5 2 6
In the first testcase:
In the second testcase:
Munir is building his new bed from IKAE! He has already dumped all his wood of lengths $$$a_1,a_2,\dots,a_n$$$ on the floor. Now the first step is to build the bed frame.
The bed frame should consist of two pieces of length $$$x$$$, and two of length $$$y$$$ (possibly with $$$x=y$$$). Unfortunately, IKAE does not have very good quality control, so he finds that he might not have two pairs of wood with the same lengths.
Instead, he tries to build an almost perfect bed frame. Specifically, he should pick distinct indices $$$i,j,k,l$$$ to minimize the deviation $$$|a_i-a_j|+|a_k-a_l|$$$.
Unfortunately he has too many pieces of wood, so he cannot do this by himself. Help him!!
Each test contains multiple test cases. The first line contains the number of test cases $$$t\ (1\le t\le 10^4)$$$. The description of the test cases follows.
The first line of each test case contains a single integer $$$n\ (4\le n\le 2\cdot 10^5)$$$ — the number of wood planks Munir has.
The second line of each test case contains n integers $$$a_1,a_2,\dots,a_n\ (1\le a_i\le 10^{18})$$$ — the lengths of each wood plank.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$
For each test case, output a single integer: the smallest possible deviation of a bed frame given the wood lengths.
341 2 3 4710 20 80 160 320 640 4052 1 2 1 2
2 50 0
This is the harder version of the problem. In this version you need to pick $$$4\cdot k$$$ indices instead of 4, and the constraints are higher.
Munir is building his new beds from IKAE! He has already dumped all his wood of lengths $$$a_1,a_2,\dots,a_n$$$ on the floor. Now the first step is to build the bed frame.
Each bed frame should consist of two pieces of length $$$x$$$, and two of length $$$y$$$ (possibly with $$$x=y$$$). Unfortunately, IKAE does not have very good quality control, so he finds that he might not have two pairs of wood with the same lengths.
Instead, he tries to build almost perfect bed frames. Specifically, he should pick distinct indices $$$i_1, i_2,\dots,i_{4k}$$$ to minimize the deviation $$${\sum_{i=1}^k{|a_{4i}-a_{4i+1}| + |a_{4i+2}-a_{4i+3}|}}$$$.
Unfortunately he has too many pieces of wood, so he cannot do this by himself. Help him!!
Each test contains multiple test cases. The first line contains the number of test cases $$$t\ (1\le t\le 10^4)$$$. The description of the test cases follows.
The first line of each test case contains two integer $$$n, k\ (4\le n\le 5\cdot 10^5, k\le \lfloor \frac{n}{4}\rfloor)$$$ — the number of wood planks Munir has and the number of beds he will build, respectively.
The second line of each test case contains n integers $$$a_1,a_2,\dots,a_n\ (1\le a_i\le 10^{18})$$$ — the lengths of each wood plank.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$5\cdot 10^5$$$.
For each test case, output a single integer: the smallest possible deviation of a bed frame given the wood lengths.
44 11 2 3 48 210 20 80 160 320 640 40 9999995 12 1 2 1 220 356 100 8 19 25 46 18 19 9 15 10 7 11 5 24 5 77 12 99 23
2 999569 0 4