Still not announced fifteen minutes before the contest begins..

So what?

2:00 hrs

It's not overlapping at all. 25 minute difference between the two.

You will see them when the contest starts. Good luck!

What's the guess ?

It took me more time to think than to code in A. You can just connect all points to the point (mid-x, mid-y) any way you want (with minimum manhattan distance), where mid-x is the middle one of their x-coordinates, and mid-y is the middle one of their y-coordinates. 47401109

Totally agree on C though, what a horrible problem. Also, I feel so dumb for initially trying to find a DP solution to B :P

C also makes me very scared of the systests :O

I haven't submitted it yet since i'm out of contest, but what i thought of was finding some point D that has minimum (manhattan) dist(A,D) + dist(B,D) + dist(C,D), and then rebuild the paths by starting from D.

I implemented it by drawing a horizontal line at the coordinate of the point with the median y-coordinate (from the min x to max x). Then, for each point, draw from that line up or down to the coordinate.

You are given with three points, A,B and C . just align them in increasing X-coordinate form by sorting the pair of points. Take a set ANS. Let A be the leftmost point, B the middle one and C be the rightmost one. Now traverse from A to B first in horizontal direction and then in vertical direction while adding the coordinates to set ANS. After this move from point C to B similarly and add the coordinate in set ANS. Duplicate elements would be added once as we are using a set. set ANS is your solution.

Code: https://mirror.codeforces.com/contest/1087/submission/47447385

If x of all points are same, then draw a horizontal line.
If y of all points are same, then draw a vertical line.
Otherwise,
Find the point whose y is medium among the y of all points. Let it be point M. Then Draw a horizontal line through M.y. Now if any point is upper than that horizontal line, then draw a vertical line from the horizontal line upto to this point. if any point is lower than that horizontal line, then draw a vertical line from the horizontal line down to to this point.

Hi..I bruteforced..:) and it works. i just found one point (x,y) ,which the absoulte difference abs(x-A.x)+abs(y-A.y)+abs(x-B.x)+abs(y-B.y)+abs(x-C.x)+abs(y-C.y) minimum; -Then just made any route from A,B,C to (x,y),seperately;

First, create a Point structure and sort the 3 points by x component. Then, let's name A, B and C the leftmost, the middle and the rightmost elements, respectively. After that, find the minimum and maximum y components of them. Using a boolean array plot[1001][1001], check all the elements from minY to maxY with the middle point x component, which is B. To connect A and C to the vertical line that passes through B, check all elements from A.x to B.x that have A.y component. Repeat that with B and C but using C.y. Finally, iterate over plot[][] counting the number of elements that are checked and print them.

Traverse through the string s. We will jump on a few cases:

I> If a[i] == b[i]:

• If s[i] was mapped as exactly a[i], ignore this position and continue.
• If s[i] was not mapped and a[i] was not used in mapping, map s[i] as a[i].
• Otherwise, output NO and terminate.

II> Otherwise:

IIa> If s[i] was mapped:

• If s[i] was mapped outside of the bounds [a_i, b_i], output NO and terminate.
• If s[i] was mapped inside of the bounds (a_i, b_i), the template will already be correct regardless of how the remaining characters are being mapped.
• Otherwise, go to phase III.

IIb> If s[i] was not mapped:

• List all possible mapping candidates for s[i] (being inside of the bounds [a_i, b_i], and not being used to map any other characters).
• If the list is empty, output NO and terminate.
• If the list contains any elements within the bounds (a_i, b_i), we can pick such element and the template will be immediately correct.
• Otherwise, go to phase III.

Regardless of the results, as long as the program wasn't terminated, we'll temporarily stop the traverse if jumping into this case.

III> Cases with s sticking to either a or b:

We will jump into this case when during the last traverse, a_i ≠ b_i and s_i was mapped to either a_i or b_i. From here, you can continue solving like above, only with one difference:

• If s sticks to a, if any mapping convert s_i to a character lexicographically greater than a_i, the template will immediately be correct.
• Similar to the case of s sticking to b, only the criterion becoming the mapped character is lexicographically lower than b_i.

If the program wasn't terminated yet after finishing all these scenarios, search for any unmapped characters and map them (in case there are some), and output the template, finishing the problem.

P/s: I can't believe I could map all these things in my head in 30 last minutes. Yet, still failed pretest for some idiotic mistake hidden beneath the messy code. Heck, the problem is a complete bane.

Div2 E = Div1 C

Find the lexicographically smallest string that is larger than or equal to a and check whether it is smaller than or equal to b.

To do so, write a helper function that checks whether any string exists such that it is larger than or equal to a and conforms to a pattern of letters and jokers. At each step you have a partly determined permutation that corresponds to a partly filled in string s and you want to choose what the leftmost joker will turn to. Example: let's solve it for s=bbcb, a=aada as in the sample test. Does a string exist for ????? Yes, just greedily fill in the jokers with the highest available symbol: ddcd >= aada. Does the string exist for aa?a? Again, yes, aada >= aada. It means that the first joker will turn into the letter a and we will have to fill in the pattern aa?a. There, aaba and aaca will fail but aada will fit. And we know that something will eventually fit because otherwise we would go for bb?b or even something larger.

Time complexity is O(n·k²).

Code: https://mirror.codeforces.com/contest/1086/submission/47418603

How to find the lexicographically smallest string that is larger than or equal to a:

You can do binary search for the length of the matching prefix after applying the template . Check for fixed length can be done in O(n * k).

After that you can just check that our string less or equal b.

Time complexity is O(n * k * log(n)).

Code: 47481574

The (X MOD K) part of the formula is between 1 and K-1. So for each of these possibles values you need to calculate the minimum X for the formula to be true. Turns out the original formula can be written as ((X-X%K)/K)*(X%K) = N, making the first term the smallest X possible. Given that you'll set the (X%K) part, you can say:

R = (X%K)

X = (N/R)*K — R

So for every possible R you find X and check. Complexity O(K)

My solution is kinda bruteforce. for (int i=1; i<=sqrt(n);i++) { if (n%i==0) { if (i<x && ((n/i)*x+i)<min)min=(n/i)*x+i); if (n/i<x && (i*x+n/i)<min)min=(i*x+n/i); } } cout<<min;

Complexity sqrt(n)

You want to find the minimal possible value. Note that increasing the first term (X/K) by 1 will cost K, and you can change X%K to any value for a cost less than K, so we want to minimize the X/K term and thus, maximize the X%K term. Both terms should be divisors of N, and X%K can be any number less than K, so we must set it to be the largest divisor of N less than K. To do this we can just check, for each number from K-1 to 1, if it divides N. Once this is found, we can find the solution easily.

https://mirror.codeforces.com/contest/1087/submission/47431845

Complexity is O(K)

Hello, Can someone explain Mathematically what is the problem with the below solution :

The solution fails on Test Case 5. Herein I have modified the equation by multiplying k to both sides, as a result I am checking if(n*k%"possible mod values starting from k-1") rather than checking if(n%"possible mod values"). I got Accepted solution when I am keeping the original equation and just checking n%mods but not with this code.

import java.util.*;
import java.io.*;
import java.lang.*;
public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s[] = br.readLine().split(" ");
        int n=Integer.parseInt(s[0]);
        int k=Integer.parseInt(s[1]);
        int p = n*k;
        long ans = Long.MAX_VALUE;
        for(int i=k-1;i>=1;i--){
            if((p%i)==0){
                ans=Math.min(ans,(p/i)+i);
            }
        }
        System.out.println(ans);
    }
}

From your code, it is not guaranteed that both c and d can be result of modulo operation. (0 ≤ c, d < k) Think of the case when n is larger than k². Then, c ≥ k.

That's right. I've been through the same thing.

I don't know the meaning for such a boring problem with lots of cases to handle. It's too much harder on coding than thinking.

I was solving it for more than ~1 hour and 10 minutes. After 1 hour I finally managed to get correct answers but received TLE which I didn't know how to fix ( ͡° ͜ʖ ͡°) So, my inability to code such simple problem is one thing, but even when not taking this into account, this is still a terrible problem.

The main idea of the problem is to skip it as soon as possible.

I agree. It seems that a lot of people do not have sufficient time finishing C,D,E (including me).

It's such a boring problem that the most difficult part of the problem is even coding. I don't know what's the problem settet doing

Is it possible that you say so because you have missed a simpler solution? Please read https://mirror.codeforces.com/blog/entry/64006?#comment-478340

The problem is on the more standard side, that's true, but I did not find anything especially hard neither in the solution nor in the implementation. There are no special cases, it is just a straightforward "find the lexicographically minimal something" exercise.

47417705 Overkill:

Segment tree with cnt[type][left_mask][right_mask], mask stands for losing and winning move.

If my reduction is correct, the amount of winning rocks is just

total amount of rocks — amount of rocks in interval (leftmost paper, leftmost scissors) — amount of rocks in interval (rightmost scissors, rightmost paper)

You can store amount of rocks in interval in a segment tree, and get leftmost paper and scissors from normal sets. Using ordered sets might be easier though.

You can use BIT. With BIT, you can find the first index x with pre(x)>=some number in O(logN). I didn't do this tho.

It's not like using ordered sets instead of most basic interval/Fenwick tree makes this problem trivial.

for(int i=y[0]-1; i<=y[1]; --i)

There is a better solution. You just need to find a point which minimizes the sum of Manhattan distances from all the points.

BTW, SUPERFAST systemtesting!! Thanks

Define a maximal path as a path that can't be extended any further (equivalently, a path from a leaf to another leaf)

Observation 1: It is always best to put edge weights on leaf-edges. If you put an edge weight in a middle segment of the graph, there will exist a leaf such that any maximal path through that middle segment will also go to that leaf, as well as potentially other paths. So all weights must be assigned to leaf-edges.

Observation 2: All maximal paths will go through exactly 2 leaf-edges (if the graph has more than 2 nodes). Hence, the optimal strategy is to minimize the 2 greatest leaf-edges, which can be done by setting all leaf-edges to the same value. Then, the weight of any path is the sum of the two maximal edges: s/leaves+s/leaves = 2s/leaves. In the case where the graph has 2 nodes, just return s

You should equalize all diameters (because decreasing one diameter necessarily means increasing another one to maintain the given sum). Each possible diameter contains two leaf nodes. Therefore, all leaf edges should have the same weight so that the maximum diameter is minimized. We can ignore non-leaf edges and set them to 0. Thus, the answer is 2 * (sum / # of leaf nodes).

I don't know how real proofs work, maybe someone else can give a more formal answer.

Do you mean taking the voronoi diagram under manhattan distance? The division isn't a simple half plane and these regions aren't convex.

I tried to understand this solution https://mirror.codeforces.com/contest/1086/submission/47429292 and here's what I got:

f(i) = squares covered at time i, g(i) = f(i) — f(i-1) = squares covered at exactly time i. g(i) is actually a piecewise linear function with decreasing slope. You can use binary search to find the events where the slope changed and do some math with faulhaber's formulas to calculate i * g(i). In code, f(i) is getNumCovered(i). You might note that an event of changing slope is actually an event where 2 boundaries merge in the chebyshev distance voronoi diagram, so there will be O(N) such events. Edit: other way to see that it has O(N) events is because the slope starts at <= 4 * N

You only need to bruteforce all possible modulos and generate minimum possible answer for each. My solution runs in O(k).

ll n, k;
cin >> n >> k;
ll ans = numeric_limits<ll>::max();
for (int mod = 1; mod < k; mod++) {
    if (n % mod) continue;
    ans = min(ans, k * (n / mod) + mod);
}
cout << ans << endl;

Note that any diameter will have two leaves as ends. Consider a tree full of 0-weight edges. Since the diameter the problem considers will be the worst possible, first observation is that we must distribute the weight equally among all leaves. Second observation is that, if you put some weight into some non-leaf edge, the only thing you're doing is increasing the chance of that there is an even worse diameter.

The solution comes from these two observations, you must distribute the given S among all leaves, that is sum/leaves. Any diameter will have two leaves as ends, so the worst diameter possible will be 2 * (weight of leaves) = 2 * (sum / leaves)

nice proof, but the other 'normal' way looks more intuitive to me, I cannot image myself ever thinking about edges as walls, so to me it looks like this is a general technique that comes up in math competitions and that's where you get the idea from,

Can you give me some sources to learn about more applications of these, some examples, very cool way to solve this problem though!

Thank you! To me that's a much better proof.

Ham aapke mannaniya pradhan mantri "NaMo The Great" hai. Hamare baare me aur janne ke liye play store se Namo app download kare. Apna vote kamal ko hi de. Jai Hind !

If you check the status in the Div. 1 version of the contest, you'll find some Java solutions to it

It's just you required better output methods than just standard System.out.
You can see this Quora question for an example of fast I/O in Java.

I think you swapped your answer and jury answer.