I really hope it doesn't happen today

Why don't stay up late XD

I think we would just say "Bonne chance !" in french. We don't add anything comparable to "wish you high ratings", it would be redudant :)

what's COCI?

I'm very sorry for this issue, I knew it too late :( It would be very difficult and annoying for me to reschedule the round. Still, good luck for the contest you'll choose to do.

Also with CSP 2nd Round, or the OI in China

When you said "I really dont wanna skip Round where McDic is tester". Was it sarcasm?

Round also clashes CSP in China, which is the biggest contest for teenagers in China.

chsv

Lol

Problems made in France. Statements will be only available in english and russian, as usual.

You're OneSubmitMan you should be legendary grandmaster all problems are accepted in one submit

I did Silly Mistakes on both A and B =)

declare 1005 elements of array when it actually has 100000 elements

My silly mistake in finding representative for sets — par[i] = par[par[i]] instead of par[i] = root(par[i])

Become Master =)) congratulate!

Can you explain your idea a bit?

I don't think the dp was of the form where you can do divconq.

1. Find distances between every two of centrals using Dijksta-like algo.

2. After that sort all central-to-central distances.

3. Construct DSU where for each component you maintain set of queries not yet answered.

4. Then just merge distances from (2) in increasing order. Use small to large technique: and if query from small is present in large set that means that this merge is first moment when queries vertices is reachable one from another

I was 2 minutes to slow to finish this in contest, so I'm waiting up-solving to submit. 65211806

This might be super complex, but I think it works:

1) Find minimum distance to every vertex from a vertex that has a station (Dijkstra), denote as d[v]

2) Transform the graph, so that each edge has now cost c[u, v] = c0[u, v] + d[u] + d[v], where c0[u, v] is cost at the beginning

3) Now each query is equivalent to — what is the heaviest edge on path in this graph between a and b.

4) Find minimum spanning tree of this graph, and on that MST perform LCA to find heaviest edge from a to LCA(a, b) and b to LCA(a, b).

I got RTE13, but I think it should do okay.

If $$$x_i < x_j$$$, you only extend $$$x_i$$$ enough to cover the uncovered left part because it's always better to cover the right part with $$$x_j$$$.

Use dsu Find min and max in every component, save these as segments, sort them If seg[i] crosses seg[i -1] then combine them and ans++

how do we find intersecting segments.?

I made the same idea, I hope this idea pass the system test

i got TLE using union find

It is somehow about counting the components and count the missing connections between them. Still not fully sure about which ones to connect to each other.

I used different approach, https://codeforces.net/blog/entry/71442?#comment-558303 .

Do DFS from 1 to N for every currently unvisited node and store the maximum visited node so far. Before doing DFS if the maximum visited node is greater than this unvisited node that means u need to connect these components, and hence increase answer by 1.

for(int i = 0; i < n; i++){
	if(!vis[i]){
		if(i < maxi)
			ans++;
		dfs(i);
	}
}

Yea union find worked for me.

Edit. But now that I think about it — simple dfs or bfs would be enough for me.

Process the connected components (either bfs, dfs or union find) and identify the max element for each component. Then check for each element 1 through n what component it belongs to and the max of this component. If you see an element of a different component and you haven't reached the max, update the max and add 1 to the answer. $$$O(m+n)$$$ overall.

Sad :((((((((((

I don't know what is the corner case in test 13

I shouldn't make such a comment. My B FST now......

You have done only 2 contests so far. It is too early for you to get frustrated.

You even didn't submit neither A nor B. How could you have contest if you haven't participated?

I'm guessing something like

6
1 -1 2 1 -1 -2

would make it fail, as you end a day when 2 is still in the office.

Trying to minimize the number of days like you're doing is actually something none of the testers thought about, hence the lack of pretest designed to make this solution fail. There will most likely be a lot of systests on that problem, and we sincerely apologize for that.

Lol, I did same thing((( I think smth like this: 1 -1 2 1 -1 -2

what does FST means?

OK MAY

6

2 -2 3 2 -2 -3

try this case

My submission I use dsu first and then sort And do the greedy approach

I used the same approach, but I stored maximum vertex of each component. So merge all components from i to i + 1 ... mx[i] for all i. You can see it in my 65211671 submission. Overall complexity is O((n + m) * DSU)

My explanation on the editorial blog

The inner min query of DP transitions can be converted to segment tree, though it's unnecessary.

Create segtree of size m+1. You start index 0 with cost 0, and indices 1...m with cost inf. Then we iterate through each antenna i in increasing order of position. Now we iterate through all possible sizes j for antenna i, such that it reaches interval [i-j,i+j]. The cost, denoted by cst, for this interval is max(0,j-s_i). Now we add this interval in the following way: we find the min cost x on interval [i-j-1,i+j] and then set index i+j to cst+x. In this way, we are "extending" the configuration from [0,i-j-1] to [0,i+j]. Now answer is index m in segtree.

The solution to C involves dynamic programming. However, we must make some observations first.

If you want to eat exactly $$$k$$$ sweets, it is optimal to always eat the ones that will result in the least sugar penalty. So, we will sort the sweets from lowest to highest sugar penalty, and for each possible $$$k$$$, we will eat the first $$$k$$$ candies in our sorted array.

Next, we realize that the optimal way in which we eat these $$$k$$$ candies is to take as many as we can each day, starting from the largest ones. For example, if we had $$$k=5$$$ sweets from $$$(1, 2, 3, 4, 5, 6, 7)$$$ and can eat $$$m=2$$$ each day, we would eat $$$(5,4)$$$ on Day 1, $$$(3,2)$$$ on Day 2, and $$$(1)$$$ on Day 3.

So there is our $$$O(n^2)$$$ approach! For each $$$k\leq n$$$, we greedily take sweets in this manner. To improve this to $$$O(n)$$$, we make some more observations about the patterns in these calculations. Let's consider the same example as above. For $$$k=5$$$, we have a minimum sugar penalty of $$$1(5+4)+2(3+2)+3(1)=22$$$. How about for $$$k=7$$$? Then we would have $$$1(7+6)+2(5+4)+3(3+2)+4(1)=50$$$, which looks suspiciously familiar...

The expression for $$$k=7$$$ can be broken down into the result of $$$k=5$$$, plus the sum of first $$$7$$$ sweets. As a matter of fact, the result of any $$$k=i$$$ will be equal to the result of $$$k=i-m$$$ plus the sum of the first $$$k$$$ sweets in our array, as long as $$$i>m$$$. We can calculate the sum of the first $$$k$$$ sweets in constant time by using a prefix sum array. Let's store our results in an array called $$$dp$$$.

Our transition is as follows:
- for $$$i\leq m$$$, $$$dp[i]$$$ is simply the prefix sum of all elements up to and including $$$i$$$.
- otherwise, $$$dp[i]=dp[i-m]$$$ plus the prefix sum of all elements up to an including $$$i$$$.

I hope this helped! If not, the official editorial should help you get somewhere. Cheers!