Wish everybody high rating

But Codeforces rating is a zero-sum game so you're wishing for impossible :/

And you should have used the past tense.

Well, participants can solve more problems before/after contest. In that case, their confidence level definitely will increase :)

Suppose your request is granted. What's to stop you from asking for an extra 30 minutes again, with the same logic? A line has to be drawn somewhere, and 2 hrs for 5/6 problems is where they decided to draw it.

You're in Div1. <1900's are Div2.

If the contests is div.1+div.2,you can only go to div.1 If the contests is “rated for div.2”,you are rated. (“you” means the coder who has rating between 1900 and 2100) Sorry for my poor English.

Python is slower than my grandma :D

Питон лучший язык. Победа на МОШе только на нём.

There will be 4 shared problems!

That's right!

You can consider each subtask as a separate problem, so score calculation will be independent. However, these two "problems" will have the same content except for the constraints.

Hacks for the first subtask will be disabled!

There will be two subtasks on problem D, and their scores are both 1000.

It means that Div-2 D will have 2 subtasks and as said above hacks for subtask 1 will be disabled. Just one more question as the time passes points for both the subtasks will decrease or what will happen?

What's new in that

Everyone wants so

You can use either a DSU or a DFS to find the connected components. Then a brute force search would suffice.

Run a flood fill to assign each land cell to a component. If the start and end position are in the same component, output 0. Else, try building a tunnel between every pair of cells in the components of the start and end positions and take the minimum answer over these.

Use dfs or bfs to find all spots reachable from the start and end. Then, find the cheapest tunnel you can make of all 50^4 possible tunnels that is has 1 side reachable from start, and 1 side reachable from end.

What I did, was to do BFS traversal, but instead of building a graph, I was using the 2D table that was given in the input. From there, you could either move in the 4 directions, such that you move to (i+1, j), (i-1, j), (i, j+1), or (i, j-1), without adding anything to the cost, or you could go to any other place which has land, and the cost would be as in the statement. In order to make sure that you only place a tunnel once, you can only build a tunnel when the previous cost was 0. Have a look at my implementation 50455831

If (r2, c2) can be reached from (r1, c1) the answer is 0.

Otherwise, put all land cells that can be reached from (r1, c1) (including it) in a vector, say v1. Also, define another vector, say v2, for all land cells that can be reached from (r2, c2).

Run an O(sz²) algorithm to calculate the minimum cost of building a tunnel between two cells, one from v1 and one from v2, where sz here represents the maximum size of v1 and v2.

Time complexity: O(sz²) = O((n²)²) = O(n⁴).

Build directed, weighted graph of 2*n^2 nodes and run dijkstra.

I'm not sure if my solution is correct, but it passed pretests: 50458735

I kept the shortest distance from A to B in a circle for every A(based on all M queries), we can call it dist[A]. Then I started with every i in [1;n] and went a full circle, while updating the answer with answer = max(answer, (q[current] - 1) * n + dist[current] + cnt), where q[A] is the number of candies on station A and cnt is the number of steps we already made, starting from i.

This solution should take O(N²) time.

UPD: It passed system tests

try 3 1 1 2 answer: 1 3 2

You can check it by trie

I did this, but instead of unordered_map, I first calculated the hashes of all intervals, then sorted pairs of the hashes, their startpoints and endpoints in the string. Then, I removed duplicate hashes, keeping only the occurence with earliest startpoint. Then, for every endpoint, I found the largest startpoint remaining in the vector of pairs, and put that startpoint into an array. Then when calculating the values, I started adding the DP values at the startpoint. What a mess, but it seems to be fast enough :/

Code: 50459140

I guess (just guess) that after each modification we could find largest suffix that appeared in this string before with Suffix Array or smth else.

I can make a wild guess that you once again submitted brute force — without even checking your code.

What is x here?

Yeah so Alice's algorithm will always return x, and the correct answer will be (x - (n - 1))n. So we want to find x, n such that (x - (n - 1))n - x = k, which is the same as (n - 1)(x - n) = k, which won't exist if k is a big prime, because we would have to have n = 2, x = k + 2.

Maybe not. k=n(a prime)*a big prime. If there is a number like prime1*prime2(>1e6) minus the number of your -1(maybe still a prime=that big prime) but you print -1

100000001 doesn't work

You can keep track of the position of the 2 people, and choose where to take them next greedily, such that the amount added to the answer (greedily)

I used DP[n x 2], on each step storing answer for "First takes from P[i][0] & Second takes P[i][1]" and interchanged. 50442447.

But also interested, if there is any greedy solution.

Same here. It's a bug most probably.

and he has done it.

congrats.

Yay!

try to change your int to long long int. Well at least this was my mistake when I was getting WA on test 10.

I also failed in pretest 10 because of overflow. I'm not sure if that's your issue, but I change my variable from an int to a long and it worked.

Just by know, what are the positions where we can reach from the first position and second position. and then check which two cells give minimum distance.

Run a flood fill and "color" in the pieces of land in the same region. Then you can brute force and check for the minimum distance between every piece of land in the same region as the start and every piece of land in the same region as the end.

if r1,c1 and r2, c2 in the same component print 0 else

for x in fields_in_first_component
  for y in fields_second_component:
    an = min(distance(y, x), an);

components can be found using dfs or something like that

For BFS, your vis vector should update when a point gets pushed onto the queue, not when it gets popped from the queue. Otherwise the same point will get pushed multiple times.

Исправлено

and all implementation tasks is a bad tasks ??

Implementation is a skill. ¯\_(ツ)_/¯

I am speak turkey

I believe WA on test 6 comes from the incorrect assumption that the last station to be satisfied is one of the stations with the highest number of candies. A counterexample to this would be where you have 4 stations, and say station 1 has two candies to deliver to station 2, and station 4 has a single candy to deliver to station 3. The candy at station 4 will be the last to be delivered, despite there only being 1 candy at the station. Because of this, you can actually brute force check over all the stations that have candy to see the latest time at which all candies will be delivered, and take the max of those.

Or more cleaner approach:

Let n=2000 and a[1]=a[2]..=a[1998]=0, a[1999]=-y and a[2000]=x.

Then (x-y)*n=x+k, in other words y=x-(x+k)/2000.

Iterate from 1e6 to 1 to find x such that (x+k)%2000=0, and output answer.

As soon as systest is complete

We're sorry for the weak tests, but we can't rejudge the solutions at this point. However, we'll add tests to the harder version for upsolving.

Sorry again.

Maybe now you'll get wrong answer in D2 too :D Just kidding, hope you get accepted on D1 as well

We're sorry for the weak tests, but we can't rejudge the solutions at this point. However, we'll add tests to the harder version for upsolving.

Sorry again.

We're sorry for the weak tests, but we can't rejudge the solutions at this point. However, we'll add tests to the harder version for upsolving.

Sorry again.

First of all, I really apologize for the weak tests. We'll add those tests to the harder version for upsolving.

Deeply sorry.