### NemanjaSo2005's blog

By NemanjaSo2005, history, 9 months ago,

Author: NemanjaSo2005

Hint 1
Hint 2
Solution
Bonus

1900B - Laura and Operations

Author: NemanjaSo2005

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Bonus

1900C - Anji's Binary Tree

Author: Riblji_Keksic

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Bonus

1900D - Small GCD

Author:NemanjaSo2005

Hint 1
Hint 2
Solution part 1
Hint 3
The rest of the solution
Bonus

1900E - Transitive Graph

Author:NemanjaSo2005

Hint 1
Hint 2
Hint 3
Solution
Bonus

1900F - Local Deletions

Author: NemanjaSo2005

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Bonus
• +103

 » 9 months ago, # | ← Rev. 2 →   0 Problem B could be solved with XOR's as well. Here's a somewhat related problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=1232
•  » » 9 months ago, # ^ |   0 can you please provide me the solution method you are discussing about!!
•  » » » 9 months ago, # ^ |   0 2xor3=1; 1xor3=2; 1xor2=3; easy simulation
•  » » » 9 months ago, # ^ |   0 ~(b^c)&1, ~(c^a)&1, ~(a^b)&1 
 » 9 months ago, # |   0 I solved B using DP 234444052
•  » » 9 months ago, # ^ |   0 Hats off to you to waste your time hhhh
•  » » » 9 months ago, # ^ |   0 I couldn't find the easier solution and I immediately noticed DP :skull:
 » 9 months ago, # | ← Rev. 3 →   +42 Nice problems, I liked the contest. I had a different solution (which generalises to harder versions easily) for D though. solutionWe will be using the following fact:For any positive integer $n$ we have $\sum \limits_{d \mid n} \varphi(d) = n$First of all note that we can sort the array and work with the sorted version with the same summation. In this case, we need to compute the following expression: $\sum \limits_{1 \leq i < j \leq n} \gcd(a_i, a_j) \cdot (n-j)$Now the main idea is to use the previous summation on the gcd expression.This means we need to evaluate the sum $\sum \limits_{1 \leq i < j \leq n} \sum \limits_{d \mid a_i, d \mid a_j} \varphi(d) \cdot (n-j)$Swapping the summation and seeing everything in terms of $d$, for a fixed $d$ and two $i< j$ such that $d \mid a_i, a_j$ we need to add a contribution of $\varphi(d) \cdot (n-j)$. Here the $n-j$ is irrelevant, and it could have been any function of $j$ or $a_j$ for that matter. (for example if it was $j+a_j$ the described solution still works)Now we are going to use the crucial fact that numbers $\leq 10^5$ have at most $128$ divisors. This allows us to update the answer as we keep adding new $a_i$. For each number $1 \leq d \leq 10^5$ we store how many multiples of it we have seen so far. Then, when processing a new element $a_i$ we look through all its divisors $d$, add a value of $\varphi(d) \cdot (n-i) \cdot \text{count of multiples of } d$and increment the corresponding count for said divisor. It's easy to keep track of all of this data, (we can also precompute $\varphi$ easily) and since $128$ is small enough to fit in the constraints, this gets the AC. EDIT: Note that the bonus can be solved in essentially the same way as above. The multiplier expression with $\gcd(a_i, a_j)$ is denoted by some $j-i-c$ for some $c = 0, 1$ (too lazy to calculate which). If we split up the $i, j$ parts we can solve the problem on the original array and reverse array and simply combine the results to obtain the final answer.
•  » » 9 months ago, # ^ |   +7 Typo: you are writing a solution for problem D.Great solution though :)
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Nice solution (for D though)! Thank you!
•  » » » 9 months ago, # ^ |   +1 Oh yes @boboge, @Megalovania sorry about that, I was only using 2 brain cells last night. lol
•  » » 9 months ago, # ^ |   0 Wow hey your solution was the same as mine, I stored $\varPhi(d) * counts\ of\ multiples\ of\ d$ instead of counts only tho. Nice solution anyways!!!
•  » » » 9 months ago, # ^ |   0 Can you please please explain me what does phi (N) means ?
•  » » » » 9 months ago, # ^ |   0 It is Euler's totient function. $\varphi(N)$ returns the number of positive integers $n\le N$ such that $n$ and $N$ are coprime, ie, have $\gcd(n,\,N)=1$.
•  » » » » » 9 months ago, # ^ |   0 Can you please explain how does that helps here ?
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 Well @NovusStellachan's explaination of the use of Euler's totient function is quite clear, can you explicitly state what you don't get about it?
•  » » » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 I am not able to understand how phi is helping us to calculate the answer
•  » » » » » » » » 9 months ago, # ^ |   +4 If we sort the array then for each i, the answer get increased by an amount of: $(n-i)*\sum\limits_{j •  » » » » » » » » » 9 months ago, # ^ | 0 Thanks for the explaination sir •  » » » » » » » » » 9 months ago, # ^ | 0 How do you type the math symbols so easily? Is it something built-in on CF or can I just do that everywhere with a specific keyboard settings? If so, how? •  » » » » » » » » » 9 months ago, # ^ | 0 CF comments and posts have built-in Latex :D •  » » 9 months ago, # ^ | +3 This is great. With your generalization, i could understand D more. (You should write D's solution laughs) •  » » 5 days ago, # ^ | 0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } Great solution! Replacing the gcd with that summation was really smart. I could have never thought of that :O  » 9 months ago, # | -8 thanks for the tutorial with hints problem E was one of the best problems i have seen live in a contest  » 9 months ago, # | ← Rev. 6 → +9 Great editorial ! It is always appreciated to have hint based editorials.Btw I might have been a bit rash in my feedback. Considering the amount of solves by div2 contestants, E made the job a div2 E should do (also, the bonus task looks super cool!!). Also, after thinking a bit more about it, I think it's not that bad to have a div2 C which isn't adhoc as it gives all contestants the opportunity to solve "algorithmic" problems and not "1-observation" problems. I'm interested in others advice •  » » 9 months ago, # ^ | +1 As a lower rated contestant, I definitely prefer more algorithmic problems. This problem reminds me of https://mirror.codeforces.com/problemset/problem/1843/D.  » 9 months ago, # | 0 really enjoyed the round, THANKS. Looking forward to more from you!!  » 9 months ago, # | 0 I'm facing a problem with solving problems with number theory tags and focused on GCD, can I have a resource to learn from so I can pass this kind of problems faster please? •  » » 9 months ago, # ^ | +5 Not really a resource but all you really need is prime decomposition of a number, the gcd trick used in D, the fact that numbers usually have up to O(m^1/3) divisors, the number of prime divisors is logarithmic, seeve, √N factoring. You can learn those by either looking it up, or solving number theory on codeforces/other platform.  » 9 months ago, # | 0 bruh why is D so tough. Can someone simplify please.. •  » » 9 months ago, # ^ | 0 We assumed that trick with subtracting higher multiples was quite well known. Also, predicted raiting for D is 1900, which is not that much for a D. •  » » » 9 months ago, # ^ | 0 I never encountered it before but it was nice to find :) •  » » » 9 months ago, # ^ | 0 I want to learn more about this. Is there a name for this trick or some resource you can share for it. Thanks for the help in advance •  » » » 9 months ago, # ^ | +1 I think it will be 2000 •  » » » 9 months ago, # ^ | ← Rev. 2 → 0 This looks interesting. Where can I find information about this trick? •  » » » » 8 months ago, # ^ | 0 Check problem D over here — https://mirror.codeforces.com/blog/entry/121618  » 9 months ago, # | ← Rev. 2 → +2 I had a slightly different solution for D. I iterated over i from 1 to maxi in order to compute x[i] (which is defined in the editorial). To compute each individual x[i], I had a list of indices of numbers in the sorted array divisible by i and I started from the third element in this list all the way to the last element. Something interesting is that if you pick some value for C with an index in the interval (x, y] in the sorted array where x and y are the indices of 2 multiples of i with no multiples of i between them with an index in that interval, then the number of possible choices for a and b such that both are divisible by i will always be the same. So you can iterate through the list of indices of multiples of i and get the #of ways to pick A and B and multiply this by the length of the current interval that tells us the #of ways to pick C. A nice implementation trick is to add the index n-1 to the end of every list of indices of multiples in order to catch all possible values of C for all x[i]. Once you've computed that, the rest of my solution is the same.234519989  » 9 months ago, # | +6 Can someone help me understand the solution to Problem D? I have been trying to understand the solution for a bit but I just can't understand it at all. Can someone give a simpler explanation because my brain just can't understand the solution for whatever reason? •  » » 9 months ago, # ^ | +27 Can provide a simple solution.I am not a native English speaker and I use translation software. If you have any translation questions, please feel free to reply to me :)The first step, as in the solution, is to find all divisors of all numbers in the range in$mlogm$time, which can be preprocessed and stored through$10^5$vectors. Note that this step precedes multiple rounds of testing. The second step is to sort the input array and enumerate$a_i$from small to large as$b$, then$c$can be selected arbitrarily after$b$, so the original problem can be converted into$\sum_{i=1 }^n\left((n-i)\sum_{j=1}^{i-1}\gcd(a_j,a_i)\right)$. That is, we now need to quickly find$\sum_{j=1}^{i-1}\gcd(a_j,a_i)$for each$i$.The third step is to find that when$a_i$is fixed, the result of$\gcd(a_j,a_i)$must be a divisor of$a_i$. So enumerate all the factors$d$of$a_i$from large to small, try to check how many$a_j$are multiples of$d$, and$d=\gcd(a_j,a_i)$, multiply this number by$ d$, then add it to the answer.More specifically, we have an array$cnt$in the range.$cnt_d$represents how many numbers in$a_1$to$a_{i-1}$are multiples of$d$. Since it has been sorted, this Arrays can be maintained simply by enumerating factors during previous traversals.The following work will be better understood through an example. Consider the following sequence$2\ 3\ 6\ 7$. At this time,$i=3$, then$cnt_1=2$(including$2$and$3$),$cnt_2=1$(including$2$) have been maintained.$cnt_3=1$(including$3$). We enumerate the factors$d$of$6$from largest to smallest:When$d=6$,$cnt_6=0$, we do nothing.When$d=3$,$cnt_3=1$, which means that among the previous numbers, there is a number that is a multiple of$3$. Although we do not know who it is (in fact, it is$3$), because we Enumerate$d$from large to small. At this time,$d=3$must be the$\gcd$of that number (in fact, it is$3$) and$a_i$(although this is not actually completely correct, we will ensure the correctness of this soon) , we do$ans+=d*cnt_d$. And because the numbers in$cnt_d$must also be in$cnt$of all factors of$d$, and we only want these numbers to be counted in$d$, so we need to traverse all the factors of$dd ^{'}$, do$cnt_{d^{'}}-=cnt_d$, thus ensuring correctness. In this example, we did$ans+=3\times1$, then traversed$1$and$3$, and did$cnt_1-=cnt_3$and$cnt_3-=cnt_3$, thus successfully converting the calculated$3 $is removed from$cnt_1$and$cnt_3$.When$d=2$,$cnt_2=1$, we do$ans+=1\times2$,$cnt_1-=cnt_2$and$cnt_2-=cnt_2$.When$d=1$, we will find that$cnt_1$has been reduced from$2$at the beginning to$0$, so we do nothingFinally, we undo all modifications made during this process, i.e. restore$cnt$to$cnt_1=2$,$cnt_2=1$,$cnt_3=1$. This can be achieved by creating a$\log$sized backup of$cnt$before calculatingNote that the number of divisors of a number in the int range does not exceed$1600$at most, and the amortized number should be$\log$level, so the complexity is not a problem •  » » » 9 months ago, # ^ | 0 Why does cnt[1] also need statistics? From back to front, why do we need to subtract the factor of d? What will be the impact if we don’t subtract it? Do you have any examples? •  » » » » 9 months ago, # ^ | 0 For your first question,$cnt_1$certainly needs to be counted. Because there is a case$\gcd(a_j,a_i)=1$, they need to be added to the answer. I'm confused by this question and I'm not sure I fully understand your first question.For your second question, I can provide further explanation.Still based on the premise that$a$has been sorted.For example, the current situation is$i=9$,$a_9=18$, and its factors are${18,9,6,3,2,1}$.Suppose we had$a_7=12$before, and its factors are${12,6,4,3,2,1}$.Obviously,$\gcd(a_7,a_9)=6$, this$6$should be part of$\sum_{j=1}^{i-1}\gcd(a_j,a_i)$when$i=9$.So now we want$\gcd(a_7,a_9)$to be evaluated, and only once, when enumerating up to a factor$6$of$a_9$.By the way, we need to make it clear that$a_i$is added to$cnt$after calculating$\sum_{j=1}^{i-1}\gcd(a_j,a_i)$. This is very important.According to the definition of$cnt_d$,$cnt_6$definitely includes$a_7$, but does not include$a_9$. When I traverse the factors of$a_9$from large to small,$a_7$will enumerate to$cnt_6$is considered and calculated correctly, but if we do nothing,$a_7$will be calculated again at$cnt_3$,$cnt_2$and$cnt_1$. That is, if we do nothing,$a_j$and$a_i$will be evaluated at all divisors of$\gcd(a_j,a_i)$, which is obviously wrong. •  » » » » 9 months ago, # ^ | 0 Sorry for still using translation software. Translating from Chinese to English is too easy to cause ambiguity. If you have any questions, please continue to ask :) •  » » » » 9 months ago, # ^ | 0 The purpose of enumerating the divisors from large to small is to traverse to the "largest" common divisor. •  » » » » » 9 months ago, # ^ | 0 There seems to be something wrong with the translation of this sentence, if you are confused about it just ignore it :( •  » » » 9 months ago, # ^ | 0 As for the first question I raised, I misread it, and I would like to apologize to you. For the second question: For example, test sample 1 5 2 3 6 12 17When gcd is a multiple of 1: there are 10 situations When gcd is a multiple of 2: there are 4 situations When gcd is a multiple of 3: there are 4 situations When gcd is a multiple of 6: there is 1 situationHere I use the array f[m] to represent the number of cases when gcd is a multiple of mWhen we count from back to front: First calculate gcd which is a multiple of 6, ans+=i*f[i], ans+=6*1 ans=6 Next, it is calculated that gcd is a multiple of 3, but at this time multiples of 3 include 6, so ans += i*f[i] cannot be used directly. Need f[3]-=f[6] in front and then calculate ans+= i*f[i] again.Is my understanding correct? •  » » » » 9 months ago, # ^ | 0 The effect of the translation software is not good. I can't guarantee that I understand what you said, but based on your final description, I think your basic counting idea is correct. Do you have instant software contact information? For example discord? If you still have questions, you can add me on discord "cap1tal_lol". Faster communication may reduce misunderstandings caused by translation software. If adding social software friends in this way is offensive to you, or is not allowed by codeforces, please forgive me and ignore what I said. If you have any questions about passing, you can continue to contact me :) •  » » » » » 9 months ago, # ^ | 0 i got the way you intended to do this problem , really amazing to be honest. for any further query i would like to communicate using discord but problem is we do not have discord servers in common so can you share one server link where i can join so that we can communicate from there ? -Cap1taL- •  » » » » » » 9 months ago, # ^ | 0 •  » » » 9 months ago, # ^ | 0 Thanks, -Cap1taL-! You helped me finally solve this problem.Here is a clarification on the part that I was missing.To calculate$∑^{i−1}_{j=1}gcd(a_j,a_i)$for a specific$i$, we should do the following: // "vector> divisors" stores array of divisors (from large to small) for all 1e5 numbers int gcd_sum = 0; for (int d: divisors[a[i]]) { int gcd_cnt = cnt[d] - already_accounted[d]; // for how many values d is GCD for (int dd: divisors[d]) { already_accounted[dd] += count_gcd_equal_d; } gcd_sum += gcd_cnt * d; } Most definitions in this code are preserved from the original explanation by -Cap1taL-. dd is the same as$d'$. already_accounted[d] indicates the number of values in$a$for which d is a divisor but not the greatest divisor (not GCD).Additionally, let's analyze the time complexity. Let's find out how many operations this cycle will do in the worst case: int ops = 0; for (int d: divisors[a[i]]) { for (int dd: divisors[d]) { ops++; } } The result is$2835$operations if$a[i]=90720$. So, in the worst case, our program will perform$(8 \cdot 10^4) \cdot 2835 = 2 \cdot 10^8$operations, which is feasible as long as you don't allocate memory in the loops. •  » » » 9 months ago, # ^ | 0 I understand the rest of the solution from the tutorial, but I do not understand how to do this "The first step, as in the solution, is to find all divisors of all numbers in the range in mlogm time". I am just a beginner. What I can think of is that we use seive to find all prime factors for each number, but I do not understand how to go from here to finding all factors. •  » » » » 9 months ago, # ^ | 0 int n; cin>>n; vector> d(n+1,vector()); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j+=i){ d[j].push_back(i); } } that cost$n\ln n$ » 9 months ago, # | 0 Problem B, I try to test 1 1 11 in everybody AC code and all code print 1 1 1, that a wrong answer. •  » » 9 months ago, # ^ | ← Rev. 2 → +2 for 1:1 1 110 2 10 // turn 1 and 3 into 22 0 8 // use 2 twos and 2 threes to make 2 ones0 2 6 // use 2 ones and 2 threes to make 2 twos2 0 4 // etc.0 2 22 0 0 // two ones1 is possiblefor 2:1 1 112 0 100 2 82 0 60 2 42 0 21 1 10 2 0 // 2 twos2 is possiblefor 3:1 1 112 0 100 2 82 0 60 2 42 0 21 1 10 0 2 // two threes3 is possibletherefore 1 1 1 is a correct answer •  » » » 9 months ago, # ^ | 0 Yes sirr  » 9 months ago, # | 0 In problem C, I was able to identify the need for DFS. I wrote my code in both Python and C++. Tried both. But got TLE on pretest 2 in Python and TLE on pretest 5 in C++.Any kind of help is greatly appreciated. •  » » 9 months ago, # ^ | ← Rev. 3 → 0 You used reference for the vector but you should also use it for the string. Your solution is quite nice! I think you are unlucky accepted submission •  » » » 9 months ago, # ^ | ← Rev. 2 → 0 Thanks for mentioning,i was not able to understand why i got tle on pretest 5. Spoiler(string should also be passed by reference) ... •  » » » 9 months ago, # ^ | 0 Really!!? I didn't get AC for a singular "&" sign?? •  » » » » 9 months ago, # ^ | 0 Yes, because the string was been copied every time the function was called. It leads to an O(n^2) time complexity. •  » » » » » 5 months ago, # ^ | ← Rev. 3 → 0 Hi, can you please tell why passing a string by value would make the soln O(N^2)? I know a copy of the string has to be made in the called function but shouldn't that make a minimal difference. Also in this soln the function is called only once. •  » » 9 months ago, # ^ | 0 I got TLE on 6th pretest with Python. If someone can see the problem, please tell me: https://mirror.codeforces.com/contest/1900/submission/234478784 •  » » » 9 months ago, # ^ | 0 Same with me, though when I tried solving it after the contest using C++, with similar logic and passing everything by reference/ making everything global. It passed. •  » » » 9 months ago, # ^ | ← Rev. 4 → 0 Hey I just checked your submissions and looks like you solved it using Python! Can you explain it to me what was the issue that you were facing before. I wrote a recursive dfs (without any memoization) and got TLE in pretest 6, maybe writing it some other way might have helped. SpoilerN = 5*10**5+1 t = int(input()) g = [[] for i in range(N)] a = [0]*N b = [0]*N maxm = N st = "" def dfs(v,x): if( v != 1 and a[v] == 0 and b[v] == 0): maxm = min( maxm, x ) for i in g[v] : if( i == 0 ): continue if( st[v - 1] == 'U' ): dfs( i, x + 1 ) elif( st[v - 1] == 'R' ): if( i == b[v] ) : dfs( i, x ) else : dfs( i, x + 1 ) elif( st[v - 1] == 'L' ): if( i == a[v] ): dfs( i, x ) else: dfs( i, x + 1 ) for _ in range(t): x = 0 maxm = float('inf') n = int(input()) st = input() for i in range(1,n): a[i],b[i] = map(int,input().split()) if (a[i]): g[i].append(a[i]) if (b[i]): g[i].append(b[i]) dfs(1,0) print(maxm)  •  » » » » 9 months ago, # ^ | 0 I have examined other's solutions and wrote bfs based on their solutions. I didn't figure out the reason of failure of my own dfs solution :( •  » » » » » 9 months ago, # ^ | 0 Hey, I got the solution to this. There is a workaround to deep recursion functions in Python. It's a method generated by pajenegod. You can find a discussion about bootstrap here https://mirror.codeforces.com/blog/entry/91490 . It is a really useful script. •  » » » » » » 9 months ago, # ^ | 0 Thank you for letting me know. I saved it for the future. Now we know why  » 9 months ago, # | 0 Problem C.Anji's Binary Tree Solution Link : HERE  » 9 months ago, # | +4 Anyone solved D using Mobius inversion? •  » » 9 months ago, # ^ | +6 Yes Submission •  » » » 9 months ago, # ^ | 0 Can you please explain your approach too? •  » » » » 9 months ago, # ^ | +17 Sorting the array gives the same value of the required sumThe required sum$S$is therefore$\displaystyle\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \sum\limits_{k=j+1}^{n} f(a_i, a_j, a_k)\displaystyle =\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \sum\limits_{k=j+1}^{n} \gcd(a_i, a_j) = \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) \gcd(a_i, a_j)$Applying the procedure described in this blog:$\displaystyle S = \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) \gcd(a_i, a_j)\displaystyle= \sum\limits_{k=1}^{M} \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) k [\gcd(a_i, a_j) = k]\displaystyle=\sum\limits_{k=1}^{M} \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j)\, k \, [\gcd(\frac{a_i}{k}, \frac{a_j}{k}) = 1]$Applying mobius inversion:$\displaystyle= \sum\limits_{k=1}^{M} k \sum\limits_{d = 1}^{\lfloor \frac{M} {k} \rfloor} \mu (d) \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) \, [kd \mid a_i] \, [kd \mid a_j]$Let$\displaystyle \text{magic}(x) = \sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} (n - j) \, [x \mid a_i] \, [x \mid a_j]\displaystyle = \sum\limits_{j=2}^{n} (n - j) \, [x \mid a_j] \sum\limits_{i=1}^{j - 1} \, [x \mid a_i]\text{If }\, i_1, i_2, \dots i_m \text{ are the indices of multiples of } x \text{ in the sorted array }\text{magic}(x) = (n - i_1)(1 - 1) + (n - i_2)(2 - 1) + \dots (n - i_m)(m - 1) $Which can be calculated "on the fly", by factorizing each arr[i] and updating magic[f] where f is a factor of arr[i]. Thus the required sum is$\displaystyle= \sum\limits_{k=1}^{M} \sum\limits_{d = 1}^{\lfloor \frac{M} {k} \rfloor} \mu (d) \, k \, \text{magic}(kd) $Calculating magic[x] by factoring in O(n * MAX_FACTORS): SubmissionCalculating magic[x] without factoring in O(M log M): Submission  » 9 months ago, # | 0 infinite water source ftw •  » » 9 months ago, # ^ | +3 Ikr? Minecraft players had an advantage in the problem!  » 9 months ago, # | +9 D could solved in O(MlogM) without factorizing. Just do the normal trick of counting gcd pairs and count in the contribution of c. •  » » 9 months ago, # ^ | 0 could you please explain? •  » » » 9 months ago, # ^ | ← Rev. 5 → +21 I will first explain the normal method to count gcd pairs. Typical problem is, given an array$a$of length$N$with value range$[1,M]$. Count the sum of$gcd$of each pair of elements, formally$\sum_{i=1}^N\sum_{j=i+1}^Ngcd(a_i,a_j)$. Instead of iterating each pair of elements, we calculate the contribution from$1$to$M$as$gcd$of a pair of elements. Define two functions:$g(i) = $the count of pairs that$gcd$is$i$.$h(i) = $the count of pairs that$gcd$could be divided by$i$. Suppose number of elements that could be divided by$i$is$cnt_i$, then$h(i)=cnt_i*(cnt_i-1)/2$. By inclusion-exclusion principle,$g(i)=h(i)-\sum_{j>i\ and\ i|j}g(j)$.Iterate from$M$to$1$, calculate$cnt$and$h(i)$with the harmonic trick. for (int i = M; i >= 1; --i) { int cnt = 0; long long h = 0; for (int j = i; j <= M; j += i) { cnt += c[i]; if (j > i) h += g[j]; } g[i] = 1ll * cnt * (cnt - 1) / 2 - h; } Now come back to the original problem. We need to calculate the contribution of each$i$where$f(a,b,c)=i$. WLOG, suppose$a\le b\le c$. Suppose we are iterating all multiples of$i$and reach$j$. We fix$j$as$b$. All numbers smaller than or equal to$j$and is a multiple of$i$could be a choice of$a$. All numbers greater than or equal to$j$is a choice of$c$. Notice here$c$is not required to be a multiple of$i$. Then we have four cases:$a
•  » » » » 9 months ago, # ^ |   0 Thank you very much. This was really awesome and helpful.
•  » » » » 9 months ago, # ^ |   0 Great explanation! Seems like gcd convolution is just a generalization of this, but even knowing how to do gcd convolution, I was not able to solve the initial problem, so your commentary has really helped a lot :)
 » 9 months ago, # |   +1 ABC was too easy this contest.
•  » » 9 months ago, # ^ |   0 and my rating dropped for not solving more than one question in the contest
 » 9 months ago, # |   0 Problem B. If all numbers are odd or all are even. Then [1,1,1] since you can make any of them after some operations. Else pick the index of the number which has the unique parity. [1,2,1] pick two, [2,1,2] pick one. [1,2,3] pick two.Operatio on [1,2,3][1,2,2,3,3,3] -> [&1&,2,2,&3&,3,3] -> [2,2,3,3,2] -> [2,2,&3&,&3&,2] -> [2,2,2,2].Magic as described by the author. 234542604
»
9 months ago, # |
Rev. 3   0

Hi , can smb tell me whats wrong with dfs that returns the answer in task C , because I have TLE in pretest 5.

# include <bits/stdc++.h>

using namespace std;

# define endl '\n'

int dfs(int x, int kount,string s, vector<pair<int,int>> v){ if(v[x].first==0 && v[x].second==0) return kount; int ans=1000000000; if(v[x].first!=0){ if(s[x-1]=='L') ans=min(ans,dfs(v[x].first,kount,s,v)); else ans=min(ans,dfs(v[x].first,kount+1,s,v));

}
if(v[x].second!=0){
if(s[x-1]=='R')
ans=min(ans,dfs(v[x].second,kount,s,v));
else
ans=min(ans,dfs(v[x].second,kount+1,s,v));

}
return ans;

}

void solve(){ int n; cin>>n; string s; cin>>s; vector<pair<int,int>> v(n+1); for(int i=1; i<=n; i++) cin>>v[i].first>>v[i].second; cout<<dfs(1,0,s,v)<<endl;; }

int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }

P.S it works O(n) and n from the text is <=3*10^5 , I can't understand why it's TL

•  » » 9 months ago, # ^ |   +1 it might be because the vector and string are not passed by reference, causing the program to make a copy of both of them, causing the time complexity to be O(n^2) instead of O(n).
 » 9 months ago, # | ← Rev. 2 →   0 can some one please tell why it is giving TLE on test case 5 and please correct it.https://mirror.codeforces.com/contest/1900/submission/234547330
 » 9 months ago, # |   +6 Problem D can be solved by mobius inversion formula. \begin{align} \sum_{i = 1}^n (n - i) \sum_{j = 1}^{i - 1} \gcd(a_i, a_j) &= \sum_k k \sum_{i = 1}^n (n - i) \sum_{j = 1}^{i - 1} [\gcd(a_i, a_j) = k]\\ &= \sum_k k \sum_{\substack{i = 1\\k | a_i}}^n (n - i) \sum_{\substack{j = 1\\k | a_j}}^{i - 1} [\gcd(\frac{a_i}{k}, \frac{a_j}{k}) = 1]\\ &= \sum_k k \sum_{\substack{i = 1\\k | a_i}}^n (n - i) \sum_{\substack{j = 1\\k | a_j}}^{i - 1} \sum_{d | \gcd(\frac{a_i}{k}, \frac{a_j}{k})} \mu(d)\\ &= \sum_d \mu(d) \sum_k k \sum_{\substack{i = 1\\kd | a_i}}^n (n - i) \sum_{\substack{j = 1\\kd | a_j}}^{i - 1} 1 \end{align}Which can be solved in $O(n\log n + n \sqrt{m} + m\log m)$. Code: 234463754
 » 9 months ago, # | ← Rev. 3 →   +7 Note that we need to solve $\sum\limits_{i=1}^n(n-i)\sum\limits_{j=1}^{i-1}\text{gcd}(a_i,a_j)$Use the equation $n=\sum\limits_{d|n}\varphi(d)$We have \begin{aligned}&\sum\limits_{i=1}^n(n-i)\sum\limits_{j=1}^{i-1}\text{gcd}(a_i,a_j)\\=&\sum\limits_{i=1}^n(n-i)\sum\limits_{j=1}^{i-1}\sum\limits_{d|\text{gcd}(a_i,a_j)}\varphi(d)\\=&\sum\limits_{i=1}^n(n-i)\sum\limits_{d|a_i}\varphi(d)\sum_{j=1}^{i-1}[d|a_j]\end{aligned}Pretreatment Euler function so that we can solve the equation in time complexity $\mathcal{O}(n\sqrt{n})$234478574
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Why do you need sqrt in complexity?
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Assume that $n$ equals to the range of $a_i$, we need to find out all the factors of $a_i$, check my code in the following link and you will get it ;)
•  » » » » 9 months ago, # ^ |   0 Yeah, I just meant you can precalculate divisors for each i (note that it's O(n log n) both time and memory complexity), then you can go through all divisors of a number (which are up to 128 for a numbers <= 10^5).
•  » » » » » 9 months ago, # ^ |   0 ur right :D
 » 9 months ago, # |   0 Thanks for the fast editorial !
 » 9 months ago, # |   0 Are the "Bonus problems" somewhere for us to submit them??
•  » » 9 months ago, # ^ |   0 No, you can only mind solve them.
 » 9 months ago, # | ← Rev. 2 →   0 .
 » 9 months ago, # |   0 Hey! guys, I'm new to competitive programming. I tried to implement anji's tree solution but I got a TLE, but when I passed the string by reference to the dfs function it worked Could someone explain to me how passing an argument by reference influence the run time. This is my code: https://mirror.codeforces.com/contest/1900/submission/234732141
 » 9 months ago, # |   +8 Problems C and E are just... weird... Nothing really to solve, just implement standard algorithms.
 » 8 months ago, # |   0 Can anyone explain why this approach doesnt work for Problem D?So i was iterating over A, and at index i i'm considering that to be middle value of triplet that is b. So as per question i need to find value of a and c now. I initialized currentIndexAns = 0 for this loop. Since a index has to be less than index of middle that is i for current loop. In an inner loop of i, i'm iterating A again. In this case if my inner loop index that is j. (ji and a[j]>=a[i]. Let's call this count as countMaxLeftMiddle. Then i will multiply this, with currentIndexAns * countMaxLeftMiddle. To get contributions of triplets which have i as middle index.Here is my code: #include using namespace std; class Solution { int gcd(int a, int b) { if (!a || !b) return a | b; unsigned shift = __builtin_ctz(a | b); a >>= __builtin_ctz(a); do { b >>= __builtin_ctz(b); if (a > b) swap(a, b); b -= a; } while (b); return a << shift; } public: long solve(int* a, int n) { long ans = 0, subPrblmAns; int greaterEqMidCntOnRight, mid; for (int i=0; i j) { if (mid >= a[j]) { subPrblmAns += gcd(mid, a[j]); } } else if (i < j) { if (mid <= a[j]) { greaterEqMidCntOnRight++; } } } cout << subPrblmAns << " " << greaterEqMidCntOnRight << endl; ans += (subPrblmAns * greaterEqMidCntOnRight); } return ans; } }; int main() { int t, n; int *a = NULL; Solution sol = Solution(); cin >> t; for (; t>0; t--) { cin >> n; a = new int[n]; for (int i=0; i> a[i]; } cout << sol.solve(a, n) << endl; delete(a); a = NULL; } return 0; } 
 » 8 months ago, # |   0 when you dont try E, because of stucking in d :(((Seems easy for me the E one. (I solved it in one go)
 » 8 months ago, # |   0 I cannot understand this part in tutorial for E : The edge will have a weight equal to the size of the SCC that it is going into.Why is that ? Shouldnt all the weights of edges be 0 ? and find the longest path by vertex numbers ?
•  » » 8 months ago, # ^ |   0 You can also keep the number of vertices in SCC in DAG vertex. Doesn't matter.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Puf did that. somehow I cannot get pass test 4. Is there any corner case or something ?
•  » » » » 8 months ago, # ^ |   0 just a stupid mistake nevermind
 » 8 months ago, # |   0 In D how to create that divisor array in NlogN. i am doing it in NrootN.
•  » » 8 months ago, # ^ |   0 You precalculate all divisors for each number using something similar to sieeve.
 » 8 months ago, # |   0 Hi, I have a question related to the time limit in problem C (Anji's Binary Tree).I got many TLE in submissions like 235439131, 235440112, 235441383. The idea was fine, but after reading some of the comments, I realized that removing some things like memset, global variables, and setting reference variables will get me to the AC (235443694).I would like to know what kind of aspects I have to think when I want to use memset or other kinds of stuff. Why do the last submissions differ in seconds to each other? What are the technical aspects related to the stuff that I have used in the first submissions? Thanks!
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Memset is O(array_size) complexity. So using it for each testcase on array of size 300 000 for 50 000 testcases is just too slow. Always reset arrays by iteratting from begin to N as you know elements after it are unaffected. Rarely you might even need to keep elements you changed in a queue.Edit: Also, note that locally declared variables are not guaranteed to have all values set to 0, so they are even worse than forgetting to reset global ones.
•  » » » 8 months ago, # ^ |   0 Got it, thanks for fast reply!
 » 8 months ago, # |   0 Can someone Please explain why I am getting a TLE in this solution for problem C 234510811
 » 8 months ago, # | ← Rev. 3 →   0 even after lot of modifications and changes, I am getting memory limit exceeded on test case 3 where n = 200000, m = 200000.I think it is due to DFS3() call but couldn't think for it's substitute. This function calculates the maximum length simple path and then for that length path minimum value. this is my submission link.There might be some other reason for TLE but I have gone through other submissions and they have also allocated same complexity of memory.( vectors and arrays for graphs )
 » 8 months ago, # |   0 Problem D can be solved without the constant of 128.Firstly notice swapping the indexes doesn't influence the sum. Then swap the indexes to a sorted state. Then, for each $g$, we want to know, $dp[g] =$ how many indexes tuples that $i < j < k$, that $\gcd(a[i], a[j]) = g$. Similar to the question, we first calculate $cnt[g] =$ number of tuples $i < j < k$ that $a[i] = a[j] = 0 \pmod{g}$, then minus $dp[2g] + dp[3g] + ... dp[\text{max multiplier} \times g]$ to $cnt[g]$Because we are in a sorted state, we can work on those $pg$ for each $p = 1 .. \text{max multiplier}$.Notice that, there are two cases. The first case is $a[i] < p g$. In this case, $pg$'s contribution to $cnt[g]$ is #$(i) * S(pg)$. $S(pg)$ is the number of tuples $(j, k)$ that $j < k$ and $a[j] = pg$. #$(i)$ is the number of index $i$s that $a[i] < a[j], a[i] = 1g .. (p-1)g$ (notice $i < j$ is obvious because we sorted it).The second case is $a[i] = a[j] = pg$. In this case, the sum is $T(pg) = \Sigma_{l \in \text{first } pg \text{ index} .. \text{last } pg \text{ index} } (l - \text{first } pg \text{ index}) (N - l)$.Both $S(pg)$ and $T(pg)$ are able to be precomputed by walking through the sorted array. So we can result a time complexity in $O(N \log N)$
»
8 months ago, # |
Rev. 2   0

In question 1 , in 5th test case

10

# ...#..#.

someone pls explain how the output is 2 ?

•  » » 8 months ago, # ^ |   0 Read the editorial...
 » 8 months ago, # |   0 In Problem C, Test case 3: I can just change the string to LRLR by modifying R -> L and U-> R and reach Vertex 2, that takes 2 modification but Why the answer is 3? Can anyone explain that bit to me?
•  » » 8 months ago, # ^ |   0 2nd letter is letter on vertex with index 2. Not on 2nd vertex you reach.
•  » » 8 months ago, # ^ |   0 initial RULR(1 2 3 4) path and replace 1-L 3-R 4-L final LRLR modification done in (1 3 4) in your case, you are modifying node 2 which won't affect and increase in one operation You should draw tree clearly
 » 8 months ago, # |   0 Why the BFS soln is not working?? Isn't it O(n)
 » 8 months ago, # |   0 Can Anyone explain solution with code of F local deletions ??
»
8 months ago, # |
0

# define ln "\n"

const int U = (1 << 30) — 1; // bit operator

int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); ll t; cin>>t; while(t--) { ll n,m; cin>>n; string s; cin>>s; vectorans(n+1,0); ll sol=INT_MAX; vectorleaf; for(ll i=1;i<=n;i++) { ll x,y; cin>>x>>y; if(s[i-1]=='R') { ans[x]+=ans[i]+1; ans[y]=ans[i];

}
else if(s[i-1]=='L')
{
ans[y]+=ans[i]+1;
ans[x]=ans[i];
}
else{
ans[x]+=ans[i]+1;
ans[y]+=ans[i]+1;
}

if(x==0 && y==0) leaf.push_back(i);
}
// for(ll i=0;i<n;i++) cout<<ans[i+1]<<" ";
for(ll i=0;i<leaf.size();i++)
{
sol=min(sol,ans[leaf[i]]);
}
cout<<sol<<endl;

}

}

Why this is wrong answer ,I am just updating distance from root according to given condition?? can any give me test case ?? @C Question

 » 7 months ago, # |   0 In Problem C, I used memorization to calculate the answer. Although being of time complexity of O(n), It is giving Time limit exceeded for n=10^5. Can someone suggest me the problem?https://mirror.codeforces.com/contest/1900/submission/239971869
•  » » 7 months ago, # ^ |   0 You are passing string s in each recursion call and therefore it is actually $O(n^2)$. I recommend using global variables for stuff such as graphs or labels and preferably all arrays/vectors.
 » 5 months ago, # |   -8 Did anyone tried Problem F? I didnt understand the editorial here
 » 5 months ago, # |   -8 Did anyone do Problem F? I do not understand the tutorials provided
 » 2 months ago, # |   0 can anyone explain me that how are we getting 2 in question A's 5th test case
 » 2 months ago, # |   0 haha infinite water glitch go brrr