gl

Bruh !! Why after even commenting, you didn't participate. Believe me you would have easily made it to the specialist!. Anyway next round is coming soon. All the Best , don't afraid , just believe in yourself. I am saying this because i was also in your situation a while ago. But Now i am a solid specialist trying for expert... got a +99 delta too in today's round just +100 points away.

How to prove A?

CM in VNOI + CF is great :>

congrats!!!

Congratulations on becoming CM

Congratulations! I am so happy for you.

Congratulations bro :-)

ooooooof

Harder than AK

Confident man, I'm sure you'll be the Legendary Grandmaster after tonight's contest.

Believe in yourself. Even if you are demoted to pupil after this contest, there are chances in the upcoming contests to be promoted again. If you deserve to be a specialist, you will remain a specialist.

Take it easy and don't start to panick or get upset if everything is not going well. At the end, it's just a title, skills are more important than titles. And right, if you deserve this title, you'll keep it or achieve it soon later on, if you fail today. Wish you good luck!

Thanks a lot mahirlabibdihan and M_bolshakov for boosting my confidence . And yeah I have seen progress and sooner or later I will achieve it if I fail today .

i became a specialist in dec 2020 and still a specialist

Take a look at this post. It talks about the fear of rating loss and shows it's no big deal.

Yea, I ate so fast in my mess to give contest, only to realize contest is 10 minutes delayed

This post downvotes counts such stupid people

Probably technical issues. Codeforces was really slow for me 5 minutes ago.

All the best :)

You can use mirror. I use it, when sending A, because very slow loading.

noted

What a contest.

Pretty much, but LCA is not needed since the sum of path lengths is O(N).

Mine was harmonic-like where we notice that units and monsters are basically h * d, group units by cost, and loop over all possible number q of units of each cost (works fast coz sum of C/i for i <= C is O(C log C)); then for each q binary search for max monster that we can kill and compute suffix minimums of costs

DP
We want to select our troops such that (health / my_damage) < (my_health / damage). (Here my_damage is sum of damages).
Thus we can compute a dp array where dp[i] = max value of my_health * my_damage if there are i coins.
You can view my submission here 150514511

There is a solution with parallel binary search. Essentially binary search on $$$C^\ast_j$$$ for each monster $$$j$$$, the minimum coins needed to kill them.

If $$$i$$$ kills $$$j$$$ then it must be that $$$H_jD_j < h_i d_i \lfloor \frac{C}{c_i} \rfloor$$$. So you binary search in the range $$$[l,r]=[0,C]$$$. Then consider $$$mid$$$. You calculate $$$g=\max_i h_id_i \lfloor \frac{mid}{c_i} \rfloor$$$. Then you partition the monsters, those with $$$H_jD_j < g$$$ and those with $$$\geq g$$$. For those with $$$<g$$$, you recurse on them in interval $$$[l, mid]$$$ and those with $$$>g$$$ you recurse on them in interval $$$[mid, r]$$$. You stop when $$$l=r$$$. Total work would be $$$O(n\log C)$$$

The complexity of erase is $$$O(n)$$$.

Your code's time complexity is o(n^2),where as given string size has limit upto 10^5. So expectime time complexity becomes o(nlogn).That's why it gives you tle

This one you can apply similar technique to prime Sieve. presumably, d, h is the type you select and D, H is that of monster, if you select n unit then this is true n*d*h > D*H. it's easy to see that d,h individually doen't matter, what matter is d*h.

C is at most 10^6, so what if we calculate the maximum d*h we can get for each cost from 1 to 10^6. Turns out this can be precompute similar to Sieve, and the complexity is cheap.

From there just binary search for each monster to see what's the cheapest cost such that the max d*h you get at cost ith is larger than D*H of monster

You can draw 2 circles, one centered at (0, 0), the other centered at (x, y) such that they intersect.

If x = 0, y = 0 then ans = 0 If you can reach x, y directly, using 1 step, ans = 1 else you can always reach using 2 steps. By going (0; 0) -> (0, y) -> (x, y)

DP. The given condition can be rephrased as: for any two vertices X and Y other than 1, the weight of edge X -> Y should be no lesser than the weight of edge 1 -> X and 1 -> Y. We have N — 1 edges starting from vertex 1 which could form (N — 1) * (N — 2) / 2 groups. So, DP from weight 1 to K, dp[i][j] means, when we have assigned weights to j edges from vertex 1 and the max weight of them is i, how many choices we have. The transistion is:
dp[i][j] = sum(dp[i — 1][l] * C(N — 1 — j, l — j) * power(K + 1 — i, j * (l — j) + (l — j — 1) * (l — j — 2) / 2) for all l < j which means, select l — j edges from N — 1 — j edges and assign them with weight i. combining them we have j * (l — j) + (l — j — 1) * (l — j — 2) / 2 groups of edges, weight of each group should be in [i, K]. The final answer is dp[K][N — 1]. https://codeforces.me/contest/1657/submission/150515462

You can draw 2 circles, one centered at (0, 0), the other centered at (x, y) such that they intersect and do 2 jumps (0, 0) -> intersection -> (x, y).

Travel parallel to x-axis first to reach the x coordinate and then travel parallel to y-axis or vice-versa to reach the final destination. This way it can be done in at max 2 moves

If we can't reach (x,y) in 1 or 2 move then we will first make move such that the x coordinate becomes equal to X coordinate of target(as y coordinate will be same so it will be valid) and in next move we will make y coordinate equal to Y coordinate of target (it will also valid as x coordinate will be same).So in minimum moves we can reach (x,y)

I almost decided to use Manacher's algorithm before I realized that the first time a character re-appears, it must be a palindrome.

Not worse than using DP in A. That's what i did :(

XD

How did you do O(nc)?

why did you use O(nC) but ?and your o(nc) runs in 358 ms how is that possible

0 , 0 -> 0, integer distance -> 1, other -> 2, because you can always go (0,0) -> (x, 0) -> (x, y)

0，0 -- a, 0 -- a, b

maximum answer can be 2 if a*a + b*b is not a perfect square because you can go from 0 to x and x,0 to x,y, else ans is 1 or if both x and y are 0 answer if 0

Store all squares till 100^2 in a set. After that simply check if (x*x+y*y) is in the set. If it is in the set answer is 1 else answer is 2 .

One edges case you'll have to handle is 0 0

same on bfs(dp) + brute force :)

i got AC on problem A when almost 7k people have passed A. my bad observation skill :(

Only insanity can help you pass F

I think you have used an array of size N * 26 for 26 characters at each vertex of the tree. I did the same mistake and got MLE on test 169. If you notice, then there will be almost $$$O(\sum{|s_i|})$$$ values required out of N * 26 values which easily gets AC.

You are using too much memory. In v and pow vector you are using O(C*n) space in worst case.

Applied the same approach, still my solution got hacked link. Can someone look at it? Thanks in Advance.

Yeah so?

Think about the case where C=10^6 and n=10^5 with each ci=1 i.e. all the units have cost 1. In this case your Code complexity become $$$O(nC) $$$

check it again. It's updated now.

Same

+1

The monster attack one unit.

And when one of our units was killed, we lose

May be because u use the float, u should use the ll