Yeah Ofcourse !! good luck man.

This was really interesting round !! it has created confidence to continue competitive programming...

brilliant, bro!

+1

Could anyone explain me about what happened in the last round?

VERY UNPAIR

It would be nice to recalculate the rating for honest users.

Can you create a blog for this problem??

no, rating distribution will be updated later most likely.

And now you're 1599 lol

Can't say I understand but I guess I can

it says it'll be rated anyway. we're just being excluded from the official standings, i don't think it'll affect us in any way tho

That's impossible.

Only if You're able to solve Problem G (XD)

both, my dear friend! There are still more language available for you :)

Wish u Happy birthday and High ratings too.

Happy birthday!Good luck!

Wish you a very happy birthday! May you acheive high rating!

You are an inspiration truly! You are trying hard and didn't give up! [user:Khedr_]Best of luck!

You're old in this platform.

lắc lắc con cac nha anh

I think it can be solved using digit dp.

btw G felt too easy for its position...

you should just get the difference of between every 2 elements in the array and try all of their divisors

My method:

If any element appears >= n/2 times, answer is -1.

Otherwise: for each choice of reference value a(i) from the array, consider the set of differences abs(a(j) — a(i)) for all j. Where the difference is 0, increment a counter z. Otherwise find the factors of abs(a(j) — a(i)), which can be done in O(sqrt(max(a))) time. Keep a count of how many times each factor occurs. Any factor such that count(factor) + z >= n/2 is a possible answer, and the max of these candidates is the final answer. Remember to reset the factor counter for each choice of reference value a(i). Total time complexity O(N^2 * sqrt(max(a)) )

Solution: link

first find the minimum element, then take GCD on the difference between the minimum value and each element (except the ones with minimum value).

output -1 if all elements are same.

I guess you forgot to sort array

You are also required to check if all items are equal. In such case, answer is -1(Infinite)

I checked your solution here https://codeforces.net/contest/1593/submission/131802472

and you have an integer overflow issue as you use vll a(n); which expands to vector<ll> of which ll expands to unsigned long long int.

When you perform a[i] - a[j] and it is unsigned, you must take extra precaution.

How did you do it?

Edge case when $$$n <= 2$$$, output should be 0

have you checked?

1
1 1

me and my friend have lost this case:)

n = 5, k = 1; 1 5; 1 5; 2 5; 3 5; 4 5;

That helped me

Case when 3(or more edges are outgoing from a single edge). Consider the case: 7 2 1 2 2 5 5 6 2 3 3 4 4 7 Removing the first set of leaf nodes, shall not make node-2 as leaf. Your solution does. I had the same problem, figured out but couldn't implement. Your Answer — 1 Expected Answer — 2

Draw the following case on paper.

consider this example.

n=6 k=2

Correct answer:

• step 1 -> 1 4 6 removed
• step 2 -> 2 5 removed

Answer is 1

Your answer

• step 1 -> 1 4 6 removed
• step 2 -> 2 5 3 removed

Answer is 0

Following up on this, problem E did not have limit of sum of K over test cases, neither had tests which had this large sum. I don't understand why authors didn't put max tests? Weak tests in general on many problems, as you can see from the number of hacks and FSTs.

1
6 2
1 2
2 5
5 6
2 3
3 4

Your answer should be 1, but using the above logic, you will get 0

the cat moves exactly $$$n-1$$$ times, so the total times you can move a mouse is also $$$n-1$$$.

To save as many mice as possible, always move the mouse nearest to the hole first. You can sort the array of the distance of each mouse to the hole, then try to save the mice from the nearest until the total distance exceeds $$$n-1$$$.

If done smartly this approach is fine. Only perform updates when a node is trimmed, and the total number of updates is equal to the total number of edges, which is N-1. Why should that TLE?

samples are not supposed to be strong lol... what's next? all tests are opened?

Wow, very simple and efficient code. But I write all possible way with if else statements that what newbies do.

Because you are including death[0] in your answer. death[0] is not set anywhere, so its value on your local machine may differ to that on the server.

Reading your code, your method appears to be "ans(node) = min distance from node to any leaf". This method is not correct. Consider why this is incorrect with the below case, to which the answer is 1 but to which your code gives 0. During the 2nd iteration, node 1 remains.

1

6 2

1 2

1 3

3 4

1 5

5 6

You also fail the case mentioned in this comment

I don't use java much but Arrays.sort(a) in java has worst-case time complexity of order n^2. Therefore the worst-case time complexity of your program is n^2 which gave tle.

You can read more here

I have this WA too, but i did dfs from a random leave

1
1 0

Yours gives 0. Ans should be 1

Edit: My bad k >= 1

1 6 2 1 2 2 5 5 6 2 3 3 4 The ans should be 1. Multisource bfs gives 0

try only pushing those nodes which are connected to the current node being processes(u) after removing u from the tree in the multisource bfs. If you didn't do it this way!

Try with language GNU G++17 9.2.0 (64 bit, msys 2) .

Nice idea :)

I think your algorithm is actually O(K + N log N) though. You use set (insertion log N). I think this explains your long run time — set is slow and you perform a lot of insert and erase operations.

If you wanted this to be truly O(N) you could store, for each node, just the two greatest distances you currently have, and update them in place without need for actually sorting (either through use of set or otherwise).

Yup! I did just now

The majority of hacks seem to be time limit related, where the user has, K times over, created a whole new queue which could have size of up to N.