For me too !

Yep last year we got "Contest starts in 5 mins " repeatedly for about an hour and we were naive enough to think that the contest is actually getting delayed xD

Frantically hit F5. It always does the trick for me!

It's Codechef !

Now you can submit in mirror contest

Why did you make the solutions visible ? xD

In HIKARU we thought of the same approach but couldn't come up with a proof so as to why this would ensure that the flow through the edge i-->j and through the edge j-->i in the Bipartite graph would be the same? They should be same because the graph should be undirected (assumption based on problem statement. or else adjacent word would be ambiguous) but how is it ensured in the flow network formulated ?

LUFFY can be solved in O(N²).

First check if the point lies in some circle itself. If it does, answer is "NO". Otherwise continue. This can be done in O(N)

Now for every pair of circles that intersect, let's call them connected. Now for every connected pair of circles, join their centres using a line segment. If the result is a polygon that encloses the given point, then the answer is "NO", otherwise the answer is "YES".

To check if the point lies in a polygon, use radial sweep.

The same problem was in ASC1 | Problem F, with better constraints ( N ≤ 300 ).

Because palindromic tree guarantees O(n) time only in linear strings. During the construction of palindromic tree, when you make transitions over suffix links, to get the suffix link of newly observed palindrome, in total it would be O(n) for a string in general but can go up to O(n²) for the tree. To overcome that, you need to make another transition table for each palindrome that directly points to a suffix link when you see a new character that cannot extend the palindrome. Some contestants passed the TL by using trie (a hack I should have thought of during TC generation :( ), however such a solution might fail.

Nice solution: let's learn how to count good numbers  <  = X for some X, after that we can find the answer with binary search. In order to count good numbers for some X, we'll learn how to count numbers  <  = X with degree  >  = Y, and say that amount of numbers with degree exactly Y can be calculated as difference between  >  = Y + 1 and  >  = Y. Now in order to count such numbers we can say that for  >  = 1 all numbers are good (or maybe all except 1 which has degree 0, but it doesn't matter anyway), and for degree  > 1 we may take a look at prime divisors which have degree at least Y and for each possible set of these divisors (as they are at least squared now, we know that their product doesn't exceed sqrt(X), and X is only a few times bigger than 1e9 in worst case, so there are not too many of them to check) calculate in how many ways we can make a number divisible by such set raised to the power Y. In order to not count something multiple times you should apply inclusion-exclusion here.

"I had a hard day and don't want to think too much, just give me my AC" solution: precompute amount of good numbers below X, 2 * X, 3 * X, ...,  for some X and hardcode it into your solution, now to answer a query find the segment [K * X + 1, (K + 1) * X] which contains the answer and solve it with a sieve in order to find a degree of each number there.

ASYAPATH — EDITORIAL
ASYA2 — EDITORIAL

Break free can be solved using binary search and greedy. Let us binary search on the answer, now we have to find minimum number of edges to be broken to decrease all subtree sizes to less than X. The greedy idea is to DFS the tree, and whenever a sub tree has greater than X weight, remove the edge to the heaviest children. It is easy to see why this works. Complexity is where S = max sum of tree weights(2·10¹³).

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int lli;

const lli inf = 27070509170705;

vector<lli> W;
vector<vector<lli>> graph;

pair<lli, lli> dfs(lli node, lli par, lli alow)
{
	if(W[node] > alow) return {0, inf};
	else
	{
		vector<pair<lli, lli>> S;
		for(auto it: graph[node])
		{
			if(it != par) S.push_back(dfs(it, node, alow));
		}
		sort(S.begin(), S.end());

		lli cur_size = W[node], del = 0;
		for(auto it: S)
		{
			if(cur_size+it.first <= alow)
			{
				cur_size += it.first;
			}
			else del++;
			del += it.second;
		}
		//cout << node << " " << cur_size << " " << del << "\n";
		return {cur_size, del};
	}
}

lli f(lli v)
{
	pair<lli, lli> res = dfs(0, -1, v);
	//cout << v << " " << res.first << " " << res.second << "\n";
	return res.second;
}

int main(void)
{
	lli n, k, u, v;
	scanf("%lld%lld", &n, &k);
	W.clear(); W.resize(n);
	graph.clear(); graph.resize(n);
	for(lli i = 0;i < n;i++) scanf("%lld", &W[i]);

	for(lli i = 1;i < n;i++)
	{
		scanf("%lld%lld", &u, &v);
		u--; v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	lli L = 1, R = inf-1, mid;
	while(L <= R)
	{
		mid = (L+R)/2;
		//cout << mid << " " << f(mid) << "\n";
		if(f(mid) >= k)
		{
			L = mid+1;
		}
		else R = mid-1;
	}
	printf("%lld\n", R+1);
}

The test cases are indeed really weak. It seems there is no test case where D < dist[N].

See this submission for proof. The assertion which even fails on sample test 2 does not fail the main cases!

never , It's codechef .

Hey wineColoredDays,
Aseem starts from the entrance and each shop is located at a distance dist[i] from the entrance. Any dependency (a, b) represents that b cannot be visited before visiting a.

Here's the sample case 1:
10 3 100
9 14 16 21 34 45 56 64 75 98
9 6
5 2
5 4

Here you have to visit all the given shops, which are at distance dist[i]. After you're done visiting all these shops, you have to visit the ending point, that is at a distance 100 from the entrance.
(9,6),(5,2),(5,3) are dependencies meaning that, shop[6] cant be visited until shop[9] is visited, shop[2] can't be visited until shop[5] is visited and similarly for shops[5] and shop[2].

The optimal solution here would be:
Representing shop numbers (1 -> 4 -> 5 -> 3 -> 2 -> 7 -> 8 -> 9 -> 6) and then finally going to the shop at distance 100.
The total distance travelled in this order is 200.

You can find it here.