### chokudai's blog

By chokudai, history, 16 months ago,

We will hold AtCoder Beginner Contest 206（Sponsored by Panasonic）.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +74

 » 16 months ago, # |   0 How to do F ?
•  » » 16 months ago, # ^ | ← Rev. 2 →   +9 We can assign Grundy values to each game. Let's denote $g(x, y)$ as the Grundy value corresponding to the game where all intervals lying entirely in $[x, y)$ are considered. We find: $g(x, y) = \text{mex over all values }g(x, l_i) \oplus g(r_i, y) \text{ where }r_i \leq y\text{ and }l_i \geq x.$Alice wins if $g(1, 100) > 0$ otherwise Bob wins.Code
•  » » » 16 months ago, # ^ |   0 Hey, just a small request...I tried to solve F (https://atcoder.jp/contests/abc206/tasks/abc206_f) by DP. This is what I tried. My understanding for intersecting is, Two intervals A, B are said to intersect if there is atleast one real number x such that x belongs to both A and B. (i.e. intervals which lie completely within each other do intersect).With this definition, I tried the following logic. First for each position from 1 to 100 note the end positions of the interval starting from that position. Similarly find the minimum end position of all the intervals starting at or after the current position. Then do a reverse dp (states 0, 1 : 0 -> considering all the intervals starting from >= current position, whether the 1st player can win. 1 -> considering all the intervals starting from current position (only this current position), whether the 1st player can win).The transition is for all the intervals starting from current position, dp[i][1] = dp[i][1] | !dp[end_position][0]. Then For j from i until the minimum end position -1, dp[i][0] = dp[i][0] | dp[j][1]https://atcoder.jp/contests/abc206/submissions/23636854I could not think of a case where it fails. Could you please suggest a case where it does not work ?
 » 16 months ago, # |   +8 How to use Mobius inversion to find the number of coprime pairs in [L,R] ?
•  » » 16 months ago, # ^ |   0 The idea is from this problem, instead of taking input make a array with element [L,R]
•  » » 16 months ago, # ^ |   0 You can also use the idea stated here : https://math.stackexchange.com/questions/218890/how-many-numbers-in-a-given-range-are-coprime-to-nI implemented this and it works well within time-limits
•  » » » 16 months ago, # ^ |   0 Btw, what is the upper bound on the number of distinct prime factors of any integer N (something that we can generally assume while solving problems)?
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 for finding coprime pairs between [L,R] you can iterate over i=[L,R] range and get all factors of i use principle of inclusion and exclusion to get number of coprime with i which lies in range [1,R] and subtract coprime which lies in range [1,L].Finding coprime in range using inclusion and exclusion principle linkAtcoder Solution Link
•  » » » 16 months ago, # ^ |   0 But how would $(R - L + 1) * 7 * 2^7$ fit in the constraints. As integer $i$ at worst case could be a product of at max $7$ primes.??
•  » » » » 16 months ago, # ^ |   0 it is 10^6*max(2^7,sqrt(10^6)/2) = 5*10^8 which passes in 1.5 sec for me. Definitely it is tight solution.
•  » » » » 16 months ago, # ^ |   +2 I guess on average, there are not that many numbers with 7 distinct primes, for instance, the smallest number that is a product of 7 distinct primes is 2*3*5*7*11*13*17 = 510510, so the amortized analysis of the time complexity would be less than that.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 i saw submissions from the leaderboard do this after computing the number of coprimes [L, R]  for (int i = max(2, l); i <= r; i++) { ans -= 2 * n_coprime(i); ans++; } I know it has something to do with removing g, where g = gcd(x,y) and either x/g = 1 or y/g = 1 but can't wrap my head around it.example submissions: AnandOza SSRS
•  » » » » 15 months ago, # ^ | ← Rev. 3 →   0 I walked through the example test case, which might be helpful to whoever is still confused  gcd(x,y) = g and one of x/g != 1 or y/g != 1 is not satisfied is equivalent to gcd(x,y) = g and x = g or y = g ex: 3 7 step 1: compute n_coprime pairs, here mu[i] denotes the mobius function of i i = 2, mu[2] = 1 (4, 4) (4, 6) (6, 4) (6, 6) 3, mu = 1 (3, 3) (3, 6) (6, 3) (6, 6) 4, mu = 0 (4, 4) 5, mu = 1 (5, 5) 6, mu = -1 (6, 6) 7, mu = 1 (7, 7) ans = (4, 4) (4, 6) (6, 4) (6, 6) (3, 3) (3, 6) (6, 3) (5, 5) (7, 7) step 2: remove every g, where g = gcd(x,y) and either x/g = 1 or y/g = 1 [i: 3] [n_coprime(i): 2] (3, 6) -> 2 * 2 - 1 = 3 ans = (4, 4) (4, 6) (6, 4) (6, 6) ~(3, 3) ~(3, 6) ~(6, 3) (5, 5) (7, 7) [i: 4] [n_coprime(i): 1] 4 -> 1 * 2 - 1 = 1 ans = ~(4, 4) (4, 6) (6, 4) (6, 6) ~(3, 3) ~(3, 6) ~(6, 3) (5, 5) (7, 7) [i: 5] [n_coprime(i): 1] 5 -> 1 * 2 - 1 = 1 ans = ~(4, 4) (4, 6) (6, 4) (6, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) (7, 7) [i: 6] [n_coprime(i): 1] 6 -> 1 * 2 - 1 = 1 ans = ~(4, 4) (4, 6) (6, 4) ~(6, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) (7, 7) [i: 7] [n_coprime(i): 1] 7 -> 1 * 2 - 1 = 1 ans = ~(4, 4) (4, 6) (6, 4) ~(6, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) ~(7, 7) tot = 7 9 - 7 = 2 final ans = (4, 6) (6, 4) 
•  » » » » 15 months ago, # ^ | ← Rev. 5 →   0 Okay so I finally understood the method. Basically after computing the co-rime pairs, we loop for i in range [max(2, l), r], and for every i, we substract 2 * n_coprime - 1 from answer.Why 2 * n_coprime - 1? Let's look at some example. ex: [3, 7] i = 2. n_coprime(2) = 2, which is 4 and 6. I'll put these in a set, S = (4, 6). To get the number of coprime pairs, we do S x S, the self product of this set which produces (4, 4) (4, 6) (6, 4) (6, 6) let's represent this better in a n_coprime(2) by n_coprime(2) matrix, 2 x 2 matrix (4,4) (6,4) (4,6) (6,6) we have a convincing pattern, the top and left borders are the g, where g = gcd(x,y) and either x/g = 1 or y/g = 1 that we need to remove.let's see another example ex: [3, 8] i = 2 n_coprime = 3, S = (4, 6, 8) co-prime pair 3x3 matrix: (4,4) (6,4) (8,4) < (4,6) (6,6) (8,6) (4,8) (6,8) (8,8) ^ it looks like the pattern persists, and this is the reason of doing ans -= 2 * n_coprime(i) - 1, as 2 * n - 1 computes the number of elements in the top and left border of a matrix. detailed explanation of example test case [3, 8] gcd(x,y) = g and one of x/g != 1 or y/g != 1 is not satisfied is equivalent to gcd(x,y) = g and x = g or y = g ex: 3 8 step 1: compute n_coprime pairs i = 2, mu[2] = 1 (6, 4), (4, 6), (6, 6), (4, 4), (4, 8), (8, 8), (8, 6), (8, 4), (6, 8) 3, mu = 1 (3, 3) (3, 6) (6, 3) (6, 6) 4, mu = 0 (4, 4) 5, mu = 1 (5, 5) 6, mu = -1 -> already computed twice (6, 6) 7, mu = 1 (7, 7) 8, mu = 0 (8, 8) -> already computed once ans = (4, 4) (4, 6) (4, 8) (6, 4) (6, 6) (6, 8) (8, 4) (8, 6) (3, 3) (3, 6) (6, 3) (5, 5) (7, 7) (8, 8) step 2: remove every g, where g = gcd(x,y) and either x/g = 1 or y/g = 1 [i: 3] [n_coprime(i): 2] (3, 6) -> 2 * 2 - 1 = 3 (4, 4) (4, 6) (4, 8) (6, 4) (6, 6) (6, 8) (8, 4) (8, 6) ~(3, 3) ~(3, 6) ~(6, 3) (5, 5) (7, 7) (8, 8) [i: 4] [n_coprime(i): 2] (4, 8) -> 2 * 2 - 1 = 3 ~(4, 4) (4, 6) ~(4, 8) (6, 4) (6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6) ~(6, 3) (5, 5) (7, 7) (8, 8) [i: 5] [n_coprime(i): 1] 5 -> 1 * 2 - 1 = 1 ~(4, 4) (4, 6) ~(4, 8) (6, 4) (6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) (7, 7) (8, 8) [i: 6] [n_coprime(i): 1] 6 -> 1 * 2 - 1 = 1 ~(4, 4) (4, 6) ~(4, 8) (6, 4) ~(6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) (7, 7) (8, 8) [i: 7] [n_coprime(i): 1] 7 -> 1 * 2 - 1 = 1 ~(4, 4) (4, 6) ~(4, 8) (6, 4) ~(6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) ~(7, 7) (8, 8) [i: 8] [n_coprime(i): 1] 8 -> 1 * 2 - 1 = 1 ~(4, 4) (4, 6) ~(4, 8) (6, 4) ~(6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) ~(7, 7) ~(8, 8) tot = 10 14 - 10 = 4 final ans = (4, 6) (6, 4) (6, 8) (8, 6) Hope this helps, highly suggesting reading this as well if you want to understand what mobius functions does!
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 It was available on gfg : https://www.geeksforgeeks.org/find-the-number-of-pairs-such-that-their-gcd-is-equals-to-1/ Just make an array with every element from L to R.Also check out my comment :https://codeforces.com/blog/entry/91945?#comment-806252
 » 16 months ago, # | ← Rev. 2 →   0 [PROBLEM -D] can anyone help me to find out where am i doing wrong. or can you give some test cases where my solution is failing. MY SUBMISSION
 » 16 months ago, # |   0 What's the Idea behind D ?
•  » » 16 months ago, # ^ |   +3 The idea was to find the sum of depths of all connected components.
•  » » 16 months ago, # ^ |   +6 Create edges between all $s_{i}$ not equal to $s_{n - i - 1}$. The answer is the sum of $size - 1$ for each connected component.
•  » » » 16 months ago, # ^ |   0 why this is working, any proof?? can you check my approach, and give some testcases where my solution will fail.
•  » » 16 months ago, # ^ |   0
•  » » 16 months ago, # ^ |   0 Yes , I understand after reading the code what's done to arrive at the answe , I want to know the why ?
•  » » 16 months ago, # ^ |   0 you can also use disjoint set union to find the answer my submission: https://atcoder.jp/contests/abc206/submissions/23594043
 » 16 months ago, # | ← Rev. 3 →   +6 D : Observation + GraphMake all a graph on all pairs of numbers which are not equal in a string palindromically. i.e. all pairs s.t. : s[i]!=s[n-1-i]Now find size of connected component and add sz — 1 to answer because we pick a number, and make atleast sz — 1 operations to make all other numbers in that component equal to that number. Code//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define F first #define S second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> g(200010); vector vis(200010,false); set h; void dfs(int v){ vis[v]=true; h.insert(v); for(int to : g[v]){ if(!vis[to]) dfs(to); } } void run_case(){ int n,i; cin >> n; vector a(n); for(i=0;i> a[i]; for(i=0;i using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define F first #define S second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i mu(mx+10); #define N 1000010 ll lpf[N], mobius[N]; // Function to calculate least // prime factor of each number void least_prime_factor() { for (ll i = 2; i < N; i++) // If it is a prime number if (!lpf[i]) for (ll j = i; j < N; j += i) // For all multiples which are not // visited yet. if (!lpf[j]) lpf[j] = i; } // Function to find the value of Mobius function // for all the numbers from 1 to n void Mobius() { for (ll i = 1; i < N; i++) { // If number is one if (i == 1) mobius[i] = 1; else { // If number has a squared prime factor if (lpf[i / lpf[i]] == lpf[i]) mobius[i] = 0; // Multiply -1 with the previous number else mobius[i] = -1 * mobius[i / lpf[i]]; } } } // Function to find the number of pairs // such that gcd equals to 1 ll gcd_pairs(ll a[], ll n) { // To store maximum number ll maxi = 0; // To store frequency of each number ll fre[N] = { 0 }; // Find frequency and maximum number for (ll i = 0; i < n; i++) { fre[a[i]]++; maxi = max(a[i], maxi); } least_prime_factor(); Mobius(); // To store number of pairs with gcd equals to 1 ll ans = 0; // Traverse through the all possible elements for (ll i = 1; i <= maxi; i++) { if (!mobius[i]) continue; ll temp = 0; for (ll j = i; j <= maxi; j += i) temp += fre[j]; ans += temp * (temp - 1) / 2 * mobius[i]; } // Return the number of pairs return ans; } void mu_calc(){ for (int i = 1; i <= mx; i++) mu[i] = 1; for (int i = 2; i*i <= mx; i++) { if (mu[i] == 1) { for (int j = i; j <= mx; j += i) mu[j] *= -i; for (int j = i * i; j <= mx; j += i * i) mu[j] = 0; } } for (int i = 2; i <= mx; i++) { if (mu[i] == i) mu[i] = 1; else if (mu[i] == -i) mu[i] = -1; else if (mu[i] < 0) mu[i] = 1; else if (mu[i] > 0) mu[i] = -1; } } void run_case(){ ll l,r,d,j,i; cin >> l >> r; ll c1 = 0,c2 = 0,c3 = 0,a1=0; ll a[r-l+1]; for(d=1;d<=r;++d){ a1+=mu[d]*(r/d)*(r/d); } for(i=l;i<=r;i++) a[i-l] = i; c1 = 2LL*gcd_pairs(a,r-l+1); // cout<
 » 16 months ago, # | ← Rev. 3 →   +6 For E what I did Ans=Total Pairs- pairsHavingGcd1- 2*(pairs(x,y)having gcd=x) n=r-l+1 Total Pairs = n*(n-1) pairs(x,y)having gcd=x, iterate for every number(i) from max(2,l) to r-1 keep on adding r/i — 1 1 is subtracted for the pairs having same no. like (2,2) max(2,l) because if we use 1 then it will be subtracted twice as we have already counted it while calculating gcd==1 since (x,y) and (y,x) needs to be counted therefore multiply by 2
 » 16 months ago, # |   +18 In the last 3 ABCs, the problem F are very educational which is great.
 » 16 months ago, # |   +13 Educational screencast. Slow, detailed explanations. Three different solutions for B, two different solutions for D. AC on F during the last minute. HD soon
 » 16 months ago, # |   -13 physics0523 when you write a contest, do you try to include physics problems whenever possible? Just curious because I'd love to solve some physics (kinematics based geometry) problems.
 » 16 months ago, # | ← Rev. 2 →   0 https://atcoder.jp/contests/abc206/submissions/23628260pls tell what is wrong in this D sol?
•  » » 16 months ago, # ^ |   +3 if(find(arr[i] != find(arr[n-i+1])))Is this intentional?
•  » » » 16 months ago, # ^ |   0 Just to check whether they have same parent or not? Is there something wrong in it? Can u provide any test case?
•  » » » » 16 months ago, # ^ |   +3 Seems like a syntax error. Read carefully. Maybe you wanted if( find(arr[i]) != find(arr[n-i+1]) ) instead of if(find(arr[i] != find(arr[n-i+1])))
•  » » » » » 16 months ago, # ^ |   +3 Sums up my rating graph... Thank u so much tho...
 » 16 months ago, # |   0 Hey Could someone help me on why i am getting wrong answer on F ? I tried thinking for case on where it would fail but cannot seem to fine.My understanding for intersecting is, Two intervals A, B are said to intersect if there is atleast one real number x such that x belongs to A and B. With this definition, I tried the following logic. First for each position from 1 to 100 note the end position of the interval starting from that position. Similarly find the minimum end position of all the intervals starting at or after the current position. Then do a reverse dp (states 0, 1 : 0 -> considering all the intervals starting from >= current position, whether the 1st player can win. 1 -> considering all the intervals starting from current position (only this current position), whether the 1st player can win).The transition is for all the intervals starting from current position, dp[i][1] = dp[i][1] | !dp[end_position][0]. Then For j from i until the minimum end position -1, dp[i][0] = dp[i][0] | dp[j][1]https://atcoder.jp/contests/abc206/submissions/23636854Could you please suggest a case where it does not work ?
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 1 4 1 5 6 16 7 10 11 15 Correct Answer: AliceYour Code: Bob
•  » » » 15 months ago, # ^ |   0 So thank you for giving a testcase where it gives wrong answer.