+2 nice

Hey man, good luck and stay safe!

I wish you all the best, son of Palestine, home of brave heroes

loved this round (happy emoji) (As cf don't allow to add emojis)

expectantly ^^

It's not, it's just people who at least once reached 1900 will not get in the official standings(though if their current rating is below 1600, the round still will be rated for them).

Your graph looks exactly like mine!!!! OMG :)

W tester = W contest

hack like 20 people and it is very possible predictor says you are 3 points short

did a problem similar to C yesterday, (a div4E), so i was able to solve it kinda quickly

Same here, i will never take that much time again, constructed an algorith to traverse clockwise lol,

Prime factorize every number and count all the primes. if all the prime count is divisible by n then yes

Find the prime factors of each element and count the total number of occurrences of each prime factor. If all the total number can be divisible by n, then output YES.

Ironically, it was quite the opposite

A was just bruteforce, that is usually the case, you can just add s to itself a few times until you get to a fairly big size where you are sure the substr won't appear again and use .find() to check if m is a substring. The strings can only get to like 100 so checking till 200 does the trick.

You could just naively check for at most $$$12$$$ operations or so. Time complexity would be $$$O(2^{12}nm)$$$ which is definitely not optimal, but anyways there are not too many testcases so it can't hurt to try too much

UPD: $$$k=12$$$ got hacked, maybe try something smaller like $$$k=6$$$

Problem F

Hint

Claim

You don't need to calculate distance from every marked vertex. Just calculate distance from the two marked vertices x and y, such that distance(x, y) >= distance(i, j) for all pairs i and j where 1 <= i, j <= n' and 'i ≠ j. This is sufficient.

Proof

Let's assume that x and y are the two marked vertices with the maximum distance between them.

Now, suppose there exists pair of vertices v and z in the tree such that distance(v, z) > max{distance(v, x), distance(v, y)}.

We can claim that: max{distance(z, y), distance(z, x)} == distance(z, v) + max{distance(v, x), distance(v, y)} > distance(x, y).

However, this statement contradicts the fact that x and y are the pair of marked vertices with the maximum distance between them. That means there's no such z and v.

So, you only need to calculate distances from vertices x and y to satisfy the given condition.

Formula

$$$f(i) = max(distance(i, x), distance(i, y))$$$ where $$$(1 \le i \le n)$$$ and $$$(x, y)$$$ are the two marked vertices with the maximum distance between them.

Time complexity: O(n) at most 4 tree traversal. two for finding (x, y). two for calculating distances.

I would say 1300

Can You explain what is tree trimming or can provide links of segment tree submissions.

coderdhanraj

Is there any approach to solve F using segment tree.

you should write clear code and use different variables , your loop conditions might get altered because of value of n.

You're only storing the factors which are <=1000. But there maybe factors >1000 for the given constraints. Try as an example [2182, 2186], the output should be NO, but your code gives YES.

most probably try larger value of i, like 5 or 10.

If x="abc", s="cabcab", your code will get a wrong answer.

How did you solve B >_<

ratings update is tmrw

Multi source bfs gives nearest red vextex not farthest

You need to calculate the diameter of tree (say $$$d$$$), considering the marked nodes as the ends. Now, intuitively the required node should lie in between this diameter, so distance would be $$$\lceil \frac{d}{2} \rceil$$$

Not as annoying as mine XD (227924103)

let ip= n-i-1 , jp = n-j-1. cells with indices (i,j) , (j,ip) , (ip,jp) , (jp,i) should be equal for each 0 <= i, j < n

He's definitely a cheater, I see no point int having an infinite while loop with a break statement.

True

It's fine. Input constraints guarantee there are at most $$$10^4$$$ values, each less than or equal to $$$10^6$$$, which means up to 20 factors per value ($$$2^{20} \gt 10^6$$$), so a total of ~200,000 prime factors to add to the map.

Yes, the idea is correct. Maybe you can use the fact that on the smallest tree spanning the marked vertices, every leaf node MUST be a marked vertex. So, root the tree on some arbitrary marked vertex, and trim the leaf nodes until all leaf nodes are marked vertices.