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.

That's why I copy-paste the magical strings from the problem statements. Too easy to make a mistake

Could you explain what does the "lo" and "lh" means in the code of problem F?

Wow. It was helpful. I bookmarked that site.

I have added some comments to the code of Problem F, hope they will help.

Can you explain how to make the second update and find minimum then?

Elements can repeat.

Try the case with all elements as 1.

Try the case with all elements as 1.

logic is correct but implimentation is wrong.

For input

3
1 1 1

your program outputs "setwise coprime", while it should be "pairwise coprime".

In the end of your solution you are dividing the answer by 2, but you can't do it by simply using operator "/" in modular arithmetic, you can read an article about it here. Also, I would say that your solution is too complicated, to get the answer you just need to calculate how many times will every number in the array be added, you can do that using prefix sums, see this solution.

Your formula is fine, but remember that you work with MOD, so you can't just divide your answer by 2. If you'll take modular multiplicative inverse, you'll get AC. Your modified solution: link.

For example: you should print answer $$$\frac{200}{2} \mod 109$$$. You're taking $$$\frac{200 \mod 109}{2} = 45$$$, that's wrong. Correct solution is: $$$200 * 2^{-1} \mod 109 \equiv 200 * 55 \mod 109 = 100$$$.

lcm grows very quickly so you can't store it in even long long.

Consider 2 primes very close to 10^6 their lcm can be as large as 10^12. So if we have n distinct primes lcm can be 10^(6*n) although that's a very light upper bound value of distinct prime also decrease but still you get the idea you can't store lcm.

Your LCM will overflow, and I think your solution might not be logically correct. Let's say the lcm of the array comes out to be x and the product the array comes out to be Mod + x then in this case your solution will output pairwise coprime whereas the correct output could be any of the 3 outputs. For example let the elements of the array be [Mod, Mod, Mod, Mod] then the lcm = Mod & product = Mod ^ 4, this will lead to the answer not coprime but your solution will give pairwise coprime. This example does not fit into the constraints but there will surely be one such testcase that will fit.

The main idea : use a set to store the nearest place in the row i which can be reached from column "j".Suppose it's d[j] for the j-th column,and use another set to store "d[j]-j" for finding the smallest "d[j]-j".

For all $$$(i, j)$$$ such that $$$1 \leq i \leq H$$$ and $$$A_i \leq j \leq B_i$$$, it is prohibited to make moves of $$$(i, j) \to (i+1, j)$$$.

You used 2 nested for loops, so you exceeded the time limit. Find a better approach with a better time complexity.

It's a basic thing to notice you can't run 2 nested for loops like that. Do you know how to estimate time complexity?

x, y = par[x], par[y] in 2nd line of union

Add 2 characters to WA code and it passes: https://atcoder.jp/contests/abc177/submissions/34640706

The issue is $$$x = m[n-1]-m[i]$$$ might be a negative value if you apply $$$m[i]$$$ mod $$$d$$$(which isn't necessary to do so in this case). In some languages like C++, modding negative values is a bit weird, so you make it non-negative by adding $$$d$$$ to $$$x$$$ (as $$$|m[n-1]-m[i]|<d$$$ in the WA code) before modding by $$$d$$$.

Corrected here.

I debug your code in order to improve my debugging ability. You miss a case where there is no prime at all, i.e., all $$$a[i]=1$$$. So if(mx == 1) should be if(mx <= 1).

Besides, potential integer multiplication overflow exists in your code.