+2 nice

Hey man, good luck and stay safe!

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

It wasn't my best contest, unfortunately :( Thanks for your comments <3.

Hope you and your family is safe!! Love from India!

You're true. I like this div3 even in case i would get negative delta. i wonder why only have 10k participants

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

expectantly ^^

i guess thay can

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).

Don't know if you remember me but I am still rooting for you!

No

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

https://codeforces.com/blog/entry/103654

Probably because someone who consistently solves ABCDE in Div 3. will be an expert. I am guessing a candidate who performs at a performance that lets them stay in the upper end of Div 3. will only solve ABCD (fairly quickly), and solve E occasionally, so that leaves the hardest 3 problems not testable by people who are below experts.

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,

it's okey , we will make it sooner or later Bro

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$$$

I only checked for 5 steps thats it.

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 got the basic idea right, but you failed to account for the fact that the increase operation might be cyclic. Try doing the 2*2 case by hand to get the idea.

I had similar solution and for elif case you may change traversed elements, so try to repeat the cycle and it worked out for me

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 >_<

I usually solve problems in order, but I couldn't solve A at first too, solved B and C first, then in the last 10 minutes, I made some changes and was able to submit A. It completely fucked up my penalty time though. More than triple of what it usually is.

ratings update is tmrw

It doesn't change instantly, you should wait for the testing phase firstly, and hacking phase secondly, then you should wait for some while maybe for 0 to 72 hours to get the rank updated.

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)

3 DFS traversal will work, just find the two farthest colored nodes, and the max distance for a particular node will be either from NodeA or NodeB. Similar intuition task https://cses.fi/problemset/task/1132, You can check my solution https://codeforces.com/contest/1881/submission/227909151

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

no

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} > 10^6$$$), so a total of ~200,000 prime factors to add to the map.

if I have unsuccessful attempts of hacking

if you hack your solution

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.

Actually, you're missing out on one index in this for loop,

for(int i=0;i<x.size()-s.size();i++){

The variable i should go upto x.size()-s.size(), so the for loop condition should be i<=x.size()-s.size()

Corrected: https://codeforces.com/contest/1881/submission/227970028

It's doing the same thing as other's have mentioned above. If the answer is yes, m will be an integer the way it is being calculated

cout<<10000<<"\n";
  for(int i=1;i<=10000;i++)
  { cout<<"5 5\n";
    cout<<"abcde\nabcdr\n";

  }

^ This could TLE the ones with already high execution times because they concatenate "abcde" with itself a large number of times along with using a string.find() for a substring with lots of partial matches.

Yeah. Found B to be much easier.