Atcoder ABC 177
Codechef August Lunchtime
Binary search io Weekly Contest 22

Leetcode Weekly Contest 204
Codeforces Round #666
Topcoder SRM 789

:)

Also worst weekend for getting brutally killed when problems are tough ..

ABC-175 was really good especially problems D and E but ABC-174 was really bad.

Store an array $$$a$$$ where $$$a[i]$$$ denotes the minimum number of rightwards moves to get to a column $$$i$$$ at row $$$r$$$. We can simply add the fixed number of downward moves at the end. We update this at each row when we go from row $$$r$$$ to $$$r+1$$$. So in the beginning it is $$$a = {0, 0, \dots, 0}$$$. Note that when we try to move to the next row, and are forbidden from going downwards from columns $$$[L, R]$$$, we have that for $$$i\in [L, R]$$$, $$$a[i] = a[L-1] + i - (L - 1)$$$. The rest of the values in $$$a$$$ stay the same. If $$$L = 0$$$, then $$$a[i] = INF$$$ for $$$i\in [L, R]$$$, where $$$INF$$$ denotes impossibility to get to that location, formally stored as a large number. We can store the array as blocks of consecutive numbers. For example, the array $$${1, 2, 3, 2, 3, 6}$$$ could be compressed into $$${ ((0, 2), 1), ((3, 4), 2), ((5, 5), 6)}$$$, where these denote an interval and the starting number of the block of consecutive numbers. Then updates can be done in $$$\mathcal O(\log W)$$$ using a set. We then simply query for the minimum value of any block of consecutive numbers, and add the current row number for the vertical moves. If this is $$$INF$$$, then we know we can't get to this row. Overall, this runs in $$$\mathcal O(H\log W + W\log W)$$$.

Submission

It is segment tree with a clever range update. I was not able to make a working implementation, but others did.

Exactly

const int N = 1e3+1;

I think N shall be 1e6 but you chose 1e3.

size of the largest connected component

create a graph and find the size of largest connected component

We can use DSU to find size of biggest component, which is ans.

Size-based merging of dsu. https://atcoder.jp/contests/abc177/submissions/16334890

This approach is $$$O(n \alpha (n))$$$.

Main observation is that if in a group, all of them are friends with each other then it is must to distribute all of them in different teams. So You have to find such group of the maximum size.

I learnt DFS a few days ago. So today I solved this problem with a simple DFS application.

Suffix sum would be a better option.

Have you put the mod(10^9+7) correctly everywhere?

can u elaborate more about your approach??

Maybe .. a common mistake in such in incorrect implementatation of modulos ? Link you code maybe ?

(a + b + c)^2 = (a^2 + b^2 + c^2) + 2 * (ab + bc + ca) You have to find (ab + bc + ca).

You can find it here.

Compute the times all integers within the given range occurred as a prime factor, then

• If every one of them occur no more than once, then pairwise coprime,
• Or, if at least one of them occour $$$n$$$ times, then setwise coprime,
• Or, not coprime

https://atcoder.jp/contests/abc177/submissions/16343274

It is enough to create the set of primefactors foreach a[i] and check if any primefactor is in any others a[j] set.

Additionally calculate the gcd of all a[i].

submission

approach for E :

for setwise coprime : i used the recursive property of gcd

for pairwise coprime : is it possible to make a set(size > 1) from given numbers s.t if we take any two element from the set whose gcd is atleast x.

if it is not possible for x>1 then paiwise coprime

submision

I guess interger overflow for large testcases in ans*=x line!

can you please provide link to your submission.

(vec[i]*pre[i-1]%MOD will lead to overflow. Replace it with ((vec[i]%MOD)*(pre[i-1]%MOD))%MOD.

try when store pre array also use mod

size of visited and adj it should be 2*10^5+1

I used Segment tree + BS, so complexity is nlog^2n.

Link to solution

Ya there shall be more ARCs!

They just could have used some tougher E. I took some time at B, then got a WA in E and that costed me.

for pairwise prime , you can store the smallest prime factor of a number using sieve. which helps to compute prime factors of the number in log(n) time. Then use a hashmap to check if any two number share any prime factors, if they do the set can't be pairwise coprime. For setwise co prime we just take the gcd while iterating the whole array. Here's my code ~~~~~ https://atcoder.jp/contests/abc177/submissions/163592881. — ~~~~~

https://atcoder.jp/contests/abc177/submissions/16359288

After each of the H rows we have foreach starting position a "shift" to right if we start at that position. The starting position with the min shift is optimal to start (because it produces the shortest path).

So we need to calculate/maintain these shifts efficiently. This is possible with a segment tree and lazy range updates, but the implementation is tricky. Because every position is not simply updated. The Update-Function is something like: newVal=max(oldVal, position-b[i])

You have done a mistake. Consider sum1 is 1e9+8 we are at an array element 2 . Now you take addition of 2%(1e9+7) and sum1 becomes 1e9+10. Same way you have done mistakes with sum and total.

In first row you cannot go down at positions in interval (a[1],b[1]), in second row you cannot go down at positions (a[2],b[2]) etc.

Floating point operations may cause precision errors.

you can't use lcm bcz if all numbers are prime, you will end up the lcm to be greater than the range of int as well as long long.