Good luck! Actually, there will be many little guys of my school participate this round tomorrow. Hope everyone can learn and enjoy from this round! :)

hope you achieve your goal, bro.

The feeling is mutual.

So a participant new to codeforces is not a trusted participant right!

Positive delta in terms of rating, not the covid variation xD

Happy Birthday!!

Yeah,wish you and me good luck. I hope to be expert for the first time in my life too!

Dream come true for me too!!

While best coders are grinding to get one black letter, Mike is casually sitting with full black nickname

Mike is most likely occasionally participating in some contests hosted on the other platforms. At least that's how I interpreted his blog post posted two months ago.

Coaches don't play!

while color != satisfactory_color:
    practise()
    give_contests()

FamilyForces

This blog should answer your questions.

Nice joke

Come on, you hesitate between codeforces and leetcode?

-_-

How can using long long instead of int cause WA?

It's obvious, isn't it?

after contest : i hope not to become newbie

you didnt need bit operations for D

voted mistakenly

i dont know what youre talking about so i think it is. You can just do dfs and not pass through a vertex twice if it has infinite paths

Yeah I also modified some scc compression code to solve this problem but it does feel overkill for a Div3.

Can you comment what is wrong in this solution?

I was trying to make topological order of this graph, the nodes that do not appear in this are in some cycle. Then I found the number of paths of nodes in topological order and the nodes that are in cycle and get -1 ,if they are connected to 1, else 0. WA submission

I also used SCC compression to get the dag. Then using bfs to count 2 visits at max. Then using if any node in a single SCC containing multiple nodes is reachable then all nodes present in that SCC are -1. Then every node which are reachable from those -1 nodes are also -1. This can be found using multisource bfs with the -1 nodes. Don't know if it is overkill.

You can see that after each move each array in A will contain one more element of it in the initial array. SO after n move => every element in A will contain the gcd of n + 1 element in the initial array (that's the worst case). If after k moves and we have an array which all of its elements are equals then that will also true for k + 1 and so on. So the main ideal here is to do a binary search on k and use sparse table to calculate the gcd from l to r in O(1) to make sure the complexity is O(nlogn). (sorry for my bad en)

Can use multisource shortest path kinda thing for E..

Actually, after a lot of thinking, I realized that the solution of E is pretty straightforward.

We need to scroll from left to right, maintain the answer, and scroll from right to left and maintain the answer. It doesn't matter which way we scroll first.

My solution LINK

I thought the same but was really solving slow this contest!

You can use a sparse table since the array is static. Mine passed in 155 ms. 121971699

I used Sparse table + Binary search but I think segment tree should be sufficient. Because the time complexity of your algorithm should be O(nlog^3(n)) and n = 2e5, so you need 1.16*10^9 *C operations in total which should fit in the time constraints (4s).

Upd:Forgot to include the gcd

Segment tree without Binary Search https://codeforces.net/contest/1547/submission/121982647

i solved using segment tree + two pointer.

I think I might be the only one with a non-binary search and non-segtree approach for F. Could not get AC so I'm not even sure if it's the right approach.

1. Divide a[i]/ gcd(a[0],a[1],...a[n-1]);
2. Concat array A with A to make A[1..N],A[1..n] of length 2n.
3. Now we know that the final gcd will be 1. All we need to find now is for a particular prime P, what is the longest continuous segment in the array where all numbers are divisible by P.
4. Final answer is, over all the primes, what is the length of maximum continuous segment as defined above.
5. Start from the index 2n-1 and move left to index 0. We can store the maxContinuous length of each prime in a separate array and update it (+1 if divisible, 0 if not) as we move left.

I couldn't get AC in time, but does the approach sound correct?

that is how I solved it, yes

There is a solution with Sparse Table.

Simulate the process, but take adjacent equal values together as a pair of $$$(value, count)$$$

you need to check suffix too , I guess only prefix is checked by your solution!

See this same idea

Since we need to merge the actions of both programmers, we need to take actions (numbers) from already given sets i.e. 'a' and 'b' and merge them. So, every element from 'a' and 'b' must be present in your output, not more not less. Your output may have one or more of the following problems: - There maybe an extra element in your output or - Maybe some element is missing or - Maybe relative order of elements in 'a' or 'b' or both is being changed.

After k processes, the element x_i will be: gcd(x_i ~ x_{i+k}). To calculate this, You can use sparse table.

How did you solve F with the help of seg-tree? Can you explain, please?

Even if the problems were all of the same difficulty you could see a similar pattern.

Let's assume that everyone approaches the problems in alphabetical order, and that different coders solve problems at different speeds. The first problems will be solved by a lot of people, and the last ones only by a few very fast participants.

The distribution of the number of accepted solutions is not a proof that the problem difficulty was increasing in a uniform way.

Observe that After performing a minimum number of steps each element of array will be equal to the gcd of the array.

I used a segment tree with binary search. Note that gcd never increases, So suppose if I am finding the minimum number of operations that are required to make this element equal to gcd, then I can do a binary search on range $$$[i,n]$$$. If we are unable to make the element equal to gcd then do a binary search in the range $$$[1,i-1]$$$

Our answer is equal to the maximum operations that any element needs.

You gotta at least wait for the hacking phase to end (for educational rounds and Div 3 rounds) and then it will take another few hours for the final system test to come, so basically you have to wait 12~24 hours. But for other rounds, it takes about 2 hours for the rating to be updated.

imagine i=n, and it's possible to complete with b, your j will grow to m with the while and then make a runtime error in your else (in b[j]<=k) and the condition j<m, I think so it would work

Or simply go once in the array from left to right, ans[i]=min(ans[i], ans[i-1]+1)

Then do the same from right to left.

Which cf predictor are you using. Please share link.

I think you might reach pupil :).

CF predictors tend to show lower sometimes

What I have observed is that there are many factors behind their incredible speed.

First of all, they are quick at thinking and realizing what needs to be done to solve the problem. That usually comes with practice and experience.

Second thing is that apart from clear thought process, they have a much simpler and smaller implementation than most others.

I am not sure about this one but I think that high speed also comes from reading and understanding problems fast, leaving out the irrelevant details and focusing on what is important to solve the problem, hence reducing the effective problem reading time.

sometimes cheater are found afterwards and their standing is decrease, sometimes the contrary happens, someone proves he's not guilty. and so it's necessary to recompute the ratings (I earned 1 point more) somebody obfuscated his code maybe he was considered a cheater

del

It is more greedy like.

You simulate the process, that is, whenever one of both people want to add a line, we add a line. Else the one with the smaller index changes that line.

If there are not enough lines to change the current line then there is no solution.

think greedily what is the smallest value you can append to y. you start with 0. to know what the smallest think about each bit if it's needed

Choose y[0]=0.

Then choose for all subsequent y[i] the smallest possible value to set all bits of x[i-1]^y[i-1]

Is it really necessary to use a profile picture with a swastika?

I did get confused when I first read C, especially when my perf was so high. I went straight to the example first, then went back and read the rest to check if I missed anything. The parts that that describe Monocarp and Polycarp's sequences are identical, so you can also skip those after a quick glance.

The round is Rated. Just Wait.

I don't think anyone has got their ratings for this round yet because it states that whether you're trusted or not this round is rated for everyone <1600

Ratings are finally updated!