### chokudai's blog

By chokudai, history, 2 months ago, We will hold AtCoder Beginner Contest 190.

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

We are looking forward to your participation! Comments (119)
 » I'll be discussing the problems right after the contest, at https://twitch.tv/AnandOzaGood luck everyone!
•  » » I've also recorded a screencast, which will be published 5 minutes after the contest: https://youtu.be/WGOnGlU5D-A. There's no commentary, so feel free to mute.
 » ... and I will release the usual screencast with commentary on my YouTube channel at https://www.youtube.com/c/NikitaSkybytskyi so that you can catch it later if you miss the stream or just like the overcomplicated explanations :upside_down_face:
•  » » 2 months ago, # ^ | ← Rev. 2 →   The screencast is here, and the (much shorter) editorial is here.
 » Starting soon!
 » This is my first contest. I have to say ABC is better than Div. 3.
 » It's better to swap E and F
 » How to solve E? I solved F but not E.
•  » » 2 months ago, # ^ | ← Rev. 2 →   dp[mask][pos] is the gem you visited and the last gem you use.We can first do bfs k time to calculate the Cij, the do the normal 2^k * k^2 bitmask dp.
•  » » how to solve F? got TLE at 2nd TC
•  » » » You can use fenwick tree to calculate inversion for k=0, and then as the given sequence is a permutation all you have to do is find the contribution the ith element is making to the ans when the ith element is put in back of the array...Here is the link to my solution
•  » » Build a graph with the edges, for each of the K gems, find the shortest path to other K gems(BFS). Now, you have basically have to chain the K gems in an order(a permutation) s.t. the sum of distances from one gem to the next is minimum (DP+bitmask).
•  » » 2 months ago, # ^ | ← Rev. 3 →   You can observe that if all the $c_i$ are not part of a component then answer is no , otherwise we can always form some ans . Now notice that k <= 17 so we can use dp over subsets . $dp[mask][j] = min(dp[mask][j] , dp[mask\oplus j][i] + dist[i][seq[j]]);$Now we are trying to form $mask$ that ends with $c_j$ and just before $c_j$ , we had visited $c_i$ and $dist[i][seq[j]]$ tells the minimum distance from $seq[i]$ to $seq[j]$
•  » » 2 months ago, # ^ | ← Rev. 6 →   It is about E:How to prove the solution of the first loop of $dp[mask][j]=min(dp[mask][j],dp[mask⊕j][i]+dist[i][seq[j]])$?I think if solve from shorter to longer it is simple.But i saw that all of solution is from [0 , 1<
 » How to solve C? Greedy algorithm doesn't work.
•  » » K is small. Use recursion
•  » » just brute force all the possible solution
•  » » » 2^100 = 10^30. Dude, what are you talking about?
•  » » » » 2^16*100
•  » » » » » I read through the line))))
•  » » 2 months ago, # ^ | ← Rev. 2 →   Use recursion to find out all the possible ways in which person can put balls in the disk it will be 2^k ways that is 2^16, total complexity will be O(2^K * M)
 » I solved $D$ with the help of oeis. Can someone help me on how to approach such problem as I would never be able to find connection between number of odd divisor and what the problem asked?
•  » » Can you please share the link of OEIS you referred to?
•  » » » ClickThe $1^{st}$ one
•  » » » » Thanks! Just found an article about the same.
•  » » How you solved D?
•  » » » $2*$ number of odd divisor of that number.Reference
•  » » 2 months ago, # ^ | ← Rev. 2 →   Formula for sum of first k element of arithmetic series whose first value is $a$ and diffrence between two consecutive element is $d$$S_k = (k / 2) (2 * a + (k - 1) * d)here d = 1 and s_k = n$$n = (k / 2) (2 * a + (k - 1))$$n = (k * a) + (k * (k - 1)) / 2$$n - k * (k - 1) / 2 = k * a$$(n - k * (k - 1) / 2) / k = a$now just check if $a$ is an integer;we will go over all possible value of $k$ for given $n$ and check if $a$ is an integer or not.submission link
•  » » » I think you mean $(n-k*(k-1)/2)/k=a$Thanks, I understood
•  » » » » Thanks for pointing out.
•  » » » why did u do *2 in the ans?
•  » » » » for each arithmetic series starting at $a$ and ending at $b$.$a, a + 1,.., b - 1, b$there is one another series like this$-(a - 1), -(a - 2),...,(a - 2), (a - 1), a, a + 1,.., b - 1, b$so here you can see negative values will cancel out positive values and it will become same as original series.
•  » » » » » thanks
•  » » » btw, why is the condition for the for loop (k * (k + 1)) / 2 <= n but not (k * (k — 1)) / 2 <= n ?
•  » » » » for arithmetic series(not starting from negative values) of length $k$, minimum sum we can get is $k * (k + 1) / 2$. This series goes from $1$ to $k$.we have to make sure this sum doesn't exceed $n$
•  » » » » You can also use : $k*a = n - k(k - 1)/2 >= 1$so that $k(k - 1) <= 2(n-1)$
•  » » » If we go one step further...n/k — (k-1)/2 = aWhich means k should be divisor of n and in order to make LHS = RHS, (k-1)/2 should also be an integer => k is odd...hence final ans would be 2 * No of odd divisors of n
 » 2 months ago, # | ← Rev. 2 →   My thought process on D.Suppose the AP contains $k$ terms, namely, $a, a + 1, \dots a + (k - 1)$. Summing up all these values and using the formula for the sum of first $i$ natural numbers, we can conclude that $a \cdot k + \frac{k \cdot (k - 1)}{2} = N$Multiplying both sides by 2, so that we deal with integers instead of fractions, we get $k(2 \cdot a + (k - 1)) = 2N$Naturally, $k$ which denotes the number of terms, should be divisible by $2N$. In other words, the possible value of $k$ is a divisor of the number $2N$. Finally, $2 \cdot a = 2\frac{N}{k} + 1 - k$This implies that the RHS should be divisible by 2. If we can satisfy both these conditions, we get our desired sequence.We know that there are atmost $O(N^{1/3})$ divisors. Hence, we can bruteforce the 2 conditions over all divisors.Code
 » 2 months ago, # | ← Rev. 3 →   How to solve D ? In problem D I used AP formula and then realized that if for positive value of $a$ , $(2a-1)^2 + 8n$ is perfect square , then we can increment the answer twice . But i didn't knew how to proceed further.Can someone help in how to count all positive values $a$ such that $(2a-1)^2 + 8n$ is perfect square ?
•  » » Number of odd divisors * 2
•  » » » I understood from above explanations that why it should be one of the divisors . Could you please elaborate why it will by always odd divisor and not even ?
•  » » » » Assume N = x * y and x is odd. Now, you have x copies of y summing to N. You can modify it to y-i,..y-2, y-1, y, y+1, y+2,.., y+i and get an AP. Another Ap can be made if you consider negative integers. But the same is not true if x is even.
•  » » » » » Thanks . It makes sense why odd will work always . It's difficult to create even length AP around y (similar to what we did when length was odd) . But it doesn't proves that there won't exist any AP of even length summing to N ?
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   even length (lets say it is l) is possible if 2N/l — (l+1) is even, which is possible only when l has all powers of 2 as in 2*N means 2N/l is odd (and indeed l is a divisor of 2N). Due to this only the answer comes as 2*(number of odd divisor possible)
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   I understood that if x is even then then it should contain all powers of 2 but i didn't get why it cannot be one of the answer ?For N = 53*4 = 212 , take x = 8 , then 'a' turns out to be 23. Indeed 23+24+25+...+30 = 212 . Thus one of the even divisor of 212 that is 8 is working .amurto could you also please check this example.
•  » » » » » » » » 2 months ago, # ^ | ← Rev. 6 →   After doing some observation, I came to know this$a + (a + 1) + (a + 2) + .. d = n$ And the problem can be reduced to find all possible values of $a$ and $d$.We can represent the desired series as $\frac {(a + d) * (d - a + 1)} 2$If you observe the parity of $(a + d)$ and $(d - a + 1)$ it will always be different. So, that gives an idea the sum will be in the form of $\frac {odd * even} 2$.And the solution is suffice to find all possible forms of $odd divisor * even divisor$ when you prime factorize $2n$. And you have to multiply it by $2$ since $(even divisor * odd divisor)$ order matters.The quotient may be even when you divide $2n$ by one of its even divisor But, the quotient is always an even number when you divide $2n$ by its odd divisor. Thus, The answer is $2$ * (total number of odd divisors of $2n)$. AC code#include int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); long long n, ans = 1; std::cin >> n; int cnt = 1; for(long long i = 2; i * i <= n; i++) { cnt = 0; while(n % i == 0) { n /= i; cnt++; } if(i > 2) ans *= ++cnt; } if(n > 1) ans *= 2; std::cout << 2 * ans << '\n'; } 
•  » » » » » » » » 8 satisfies well the condition I wrote above 2*212/8 — 9 is indeed even and then is a valid divisor of 2*212 for which answer is possible.
•  » » » » » » » » For N=212, x=53, y=4, consider 53 copies of 4. Lets create an AP with terms y-x/2,..,y-1,y,y+1,..,y+x/2. It would look like -22,-21,-20,...,0,1,2,3,4,5,,...,23,24,25,26,27,28,29,30 We cannot add more integers to the prefix to make another AP, but rather remove some integers from the prefix. Consider a suffix from the above AP where sum=N. It is the same AP you mentioned. 23,24,..,30. So for every odd divisor, two APs are possible, even length and odd length.
•  » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   I understood it should be only 2* count of odd divisor .From formula $2a=2N/K+1-K$ , RHS shouldn't be odd and thus suppose $2N = x*y$ , both $x$ and $y$ cannot be even or odd simultaneously and cannot be equal. Also for every $x$ corresponding $y$ will be unique and suppose $x •  » » » » » » » » » It could be even divisor if the quotient is an odd when you divide$2n$by an even divisor. •  » » Here is how I solved this problem. Let's say$n$=$\frac{a\cdot (a + 1)}{2}$—$\frac{b\cdot(b + 1)}{2}$Now after solving the equation we get$2\cdot n = (a - b)\cdot(a + b + 1)$after that we can see whenever integer solution exists for$a$and$b$we add$2$to our answer because we can also go into negative side to get one more solution . Time complexity will be$O(sqrt(n))$•  » » u can do it by counting the number of ways of making sum of n by consecutive numbers gfg algo for it by this and then just add 1 that the case the number n itself and multiply by 2 because u can always make the same series by adding negative terms and u are done..my code •  » » You can brute force the value of number of terms in AP, which is at most 1e7 for sum=1e12 and check if you can find any suitable a(First Term) for all number of terms from 1 to 1e7. Then just double the ans.  » Felt like torturing myself while doing E •  » » I agree. •  » » will learn something today  » i solved F using Policy Based Data Structure in C++ how to solve it without Policy Based Data Structure •  » » You can use fenwick tree to count number of inversions in the initial array let say$ans$. After that you can notice that each front element will move to the back of the array and thus you can do$ans = ans - (a[i]-1) + (n-a[i])$. •  » » » not able to observe ans = ans — (a[i] — 1) + (n-a[i]) ... please explain •  » » » » 2 months ago, # ^ | ← Rev. 2 → You can observe that each time you increase$k$, front element of the array will move to the back of the array . Since there are$a[i]-1$elements which were causing inversion because they are after$a[i]$but they will be at front of$a[i]$as soon as we move$a[i]$to the back of array . Thus we need to subtract$a[i]-1$.For example :array$3,2,1$, Now suppose i move$3$to back of the array , then array will be$2,1,3$. We can see that$1$and$2$were causing inversion with$3$but after we moved$3$to back of the array they won't cause inversion any more .$n-a[i]$part can be explained analogously . •  » » You can use merge sort to find th no. of inversion , The link could be found on Geeks for geeks •  » » » link to article please •  » » » » Code#include long long cnt = 0; void merge(int* arr, int* M, int l, int mid, int r) { int i = l, j = mid + 1, k = l; while(i <= mid && j <= r) { if(arr[i] > arr[j]) M[k++] = arr[j++], cnt += mid - i + 1; else M[k++] = arr[i++]; } while(i <= mid) M[k++] = arr[i++]; while(j <= r) M[k++] = arr[j++]; for(int i = l; i <= r; i++) arr[i] = M[i]; } void mergeSort(int* arr, int* M, int l, int r) { int mid = l + (r - l) / 2; if(l < r) { mergeSort(arr, M, l, mid); mergeSort(arr, M, mid + 1, r); merge(arr, M, l, mid, r); } } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); int n; std::cin >> n; int arr[n], M[n]; for(int i = 0; i < n; i++) std::cin >> arr[i]; mergeSort(arr, M, 0, n - 1); std::cout << cnt; } Or You can see other submissions on EURON •  » » » » •  » » Link to your solution please •  » » »  » wait! So, B isn't dp? •  » » Just do as the problem says. •  » » » How to solve it if you can use multiple spells? I thought about some knapsack. •  » » » » You just need to find out whether there is at least one strong spell or not. •  » » » » » Yeah But I'm asking how to solve the variant of the problem. •  » » » » » » If you can choose any number of spells, you just have to check the sum of the powers' of strong spells. But if there is a limit on the maximum number of chosen spells, yeah, it would be a knapsack problem. •  » » Wait, it was GRAPH!! •  » » » No way$!$I solved using$FFT$•  » » » » orz  » why you set question statement confusing instead of making good question. In todays contest question B statement was very confusing. In 2nd last contest you did in question C.  » 2 months ago, # | ← Rev. 2 → My submission for F passes the sample test on my system but they are generating a different output on Atcoder's system. Anyone please help me finding out where it's all going wrong.UPD: Got the error, there was a segmentation fault in my Fenwick Tree. •  » » Hey, running your code on my system gives this error: f.cpp:122:15: runtime error: index 300016 out of bounds for type 'int ' •  » » » Yeah, I saw that just now. Thanks !!  » D much harder than E and F. Still do not get it. •  » » 2 months ago, # ^ | ← Rev. 2 → Even i couldn't get the idea for D. But OEIS helped. oeis sequenceDid a brute force to find the answer for the first 20 natural numbers and then used oeis to get the general formula.The formula is : 2*cnt_of_odd_divisors_of_n •  » » Hint: l + (l + 1) + ... + r = (l + r) * (r - l + 1) / 2 •  » » » I've also tried this to find r for each l iterating from -n to n. But it was a brute force approach. •  » » » » Sometimes coming up with brute force helps in problems like these where the input is a single integer. Most of the times the general formula can be obtained from sites like Oeis. This is not the best approach to solve problems but certainly helps if you are not able to come up with any better solution. •  » » » » » These kinda problems are those I'd spend a day to solve. I know OEIS but It's only fun if I solve the problem myself. And Yeah, I think ABC really helps improving the observation skill. •  » » 2 months ago, # ^ | ← Rev. 3 → clicksum = n / 2 * (2 * a1 + (n - 1) * d) d = diffrence between 2 terms n = total terms a1 = first term sum = sum of all elements sum = (n / 2) * (2 * a1 + (n - 1) * d) (d = 1 given) 2 * sum = n * (2 * a1 + (n - 1)) we can factorize 2 * sum as x * y such that (1) x = n y = 2 * a1 + (n - 1) so y = 2 * a1 + (x - 1) a1 = (y - x + 1) / 2 if (y - x + 1) divisible by 2 ans++ (2) x = 2 * a1 + (n - 1) y = n so x = 2 * a1 + (y - 1) a1 = (x - y + 1) / 2 if (x - y + 1) divisible by 2 ans++  codevoid solve(int &tc) { ll n; cin >> n; n *= 2; ll ans = 0; for(ll i = 1; i * i <= n; i++) { if(n % i == 0) { ll x = i; ll y = (n / i); if((y + 1 - x) % 2 == 0) { ans++; } if(x != y) { if((x + 1 - y) % 2 == 0) { ans++; } } } } cout << ans << endl; }  •  » » » What is the meaning of "we can factorize ... as ... such that..." ? •  » » » » i mean divisors : 12 => (1, 12), (2, 6), (3, 4) •  » » We can look at problem D in this way:Sum of 'n' elements of an AP with first term being 'a' and common difference being 'd' = n*a + (n*(n-1))/2.we want it to be equal to 'S'. On rearranging terms we geta = (S-(n*(n-1))/2)/nWe can fix that a>0 as we can always form an AP starting with negative -a+1. So for every possible a>0 we can have another AP whose 1st term is non-positive.for a to remain positive S-(n*(n-1))/2 should remain positive. So we need to iterate over all values of 'n'. S can go up to 1e12 and it's subtracted with n^2 so we need to travel around 10^6 only.Hope that helps. Feel free to ask if anything is not clear. •  » » » I would be happy to get some explanation starting with the idea, not some formular.As far as I understood the formulars follow the idea that 2*N is diviseable by the length of the seq with sum N. Is that correct?How do we know that there is only one such sequence with than length? What is 'a' in your formulars, how/why can we "fix it"? •  » » » » Regarding idea, I started by writing down the formula itself because I remembered that there is square term in the formula and the time complexity also seemed to be O(sqrt(n)).There are a lot of formulas to calculate the sum of AP but I chose this because of the square term.'a' is the first term of AP.With common difference 'd' being fixed and equal to 1, sum of AP becomes sum of consecutive numbers starting from 'a'. So for a particular length and fixed sum, we can have only 1 'a', so it's unique. We cannot have sum of, let's say 3 consecutive numbers same unless they have the same first number. •  » » » » Maybe this helps to get the intuition. •  » » 2 months ago, # ^ | ← Rev. 2 → Let$n$be the given number$a$the first number in the sequence and$k$size of the sequence:$n = \frac{k * (k-1)}{2} + a * k$. We want to get how much$a$is equal, because it has to be the real number. With enough transforming, you get the following formula:$a = \frac{n}{k} - \frac{k-1}{2}$. We have two cases: 1) Both$\frac{n}{k} - \frac{k-1}{2}$are real. For that case, the answer is the number of odd divisors of$n$. 2) Both$\frac{n}{k} - \frac{k-1}{2}$are of the form$0.5+$some real number. As you can see,$k$must be even so that$\frac{k-1}{2}$be of that form. Now$\frac{n}{k}$to be of that form,$gcd(n, k)$must be equal to$\frac{k}{2}$. The answer for this case is also the number of odd divisors of$n$. •  » » Try out a few numbers and try to find the pattern. I didn't think in terms of formulae either, but was lucky enough to catch this from the examples. N = 12N = 12 We can write AP with sum 12 as, 12 => 12 6,6 => 5.5, 6.5, but we only want integers 4,4,4 => 3,4,5 3,3,3,3 => same issue as 6,6 2,2,2,2,2,2 => -2,-1,0,1,2,3,4,5 (same as 3,4,5 but a 0 sum AP before it) 1,1,1,1,1,...,1 => -11,-10,-9,...10,11,12 (same as 12 but a 0 sum AP before it)  N = 5N = 5 We can write AP with sum 5 as, 5 => 5 5 => -4,-3,-2,-1,0,1,2,3,4,5 (same as above but with a 0 sum AP before it) 1,1,1,1,1 => -1,0,1,2,3 2,3 => 2,3 (same as above but without the 0 sum AP before it)  Observationif we write N as sum of its divisors, using even number of summands leads us nowhere but with odd number of summands, we can do 2 things 1. increase/decrease the numbers to form an AP (4,4,4 => 3,4,5) 2. then, add/remove a 0 sum AP before it (3,4,5 => -2,-1,0,1,2,3,4,5) or (-1,0,1,2,3 => 2,3) so the answer turns out to be 2 * number of odd divisors of N.  •  » » I did a binary search approach on D. I tried to express the number as a sum of i consecutive numbers. You can check my submission for a better understanding •  » » » Actually I am not sure for which value do you do the binary search. On the other hand, I was now able to implement a binary search.The formular for the sum of some seq, let$l$be first,$r$be last element of the seq:$(l+r)/2 * (r-l-1)$So we know that$2*N$is divisable by the len of the seq. Finding all divisors of$2*N$foreach: Binary search for the first element of that seq.Then, if the seq of that len, with that first element has sum N, then we found one and increment ans by 2.I had some difficulties to overcome overflow errors, in the end I used 128 bit type. However, it seems to work with 64 bit, too, but I still do not see how. Debug output shows me that calculating the sum in the binary search overflows the 64 bit type.submission •  » » » » 2 months ago, # ^ | ← Rev. 4 → Let l be the first term and total number of terms be i.. so it can be written as l,l+1,l+2,...,l+i-1 i.e (l*i)+((i-1)(i-1+1)/2) so it will never overflow because l <=1e12 and i<=2e5 in my submission. And l was the value on which i did binary search for every i terms  » Can somebody please help as why my recursive solution is giving TLE in problem C? I don't understand. •  » » Interesting! Looks like you're iterating through$k!$instead of$2^k$combinations. remove the for loop. •  » » » Yes, I iterated through k!, the unnecessary loop didn't strike me ;(, Thanks :) •  » » » » You can either use some bitmask trick. for(int i = 0; i < 1 << k; i++) { for(int j = 0; j < k; j++) { if(i >> j & 1) //include } }   » My solutions, along with detailed explanations, can be found here :) •  » » Can we see testcases in atcoder. i am new to atcoder. •  » » » Testcases can be found here https://atcoder.jp/posts/21  » Words hiding behind each problem AJust Implement what I'm saying BWasn't it clear what A just said? "Just Implement what the statement says!!!" CK is small just do brute force! DGoogle me google me, please! Type in "number of ways to write a number as a sum of consecutive integers" EI don't know, it's a hard problem for me the easy problem: if nodes in$C\$ are not in the same connected component print -1 the other one: find the minimum length of a path that contains a certain set of nodes in an undirected graph (uhh?) FYou might have solved me on another site try to remember
•  » » This is a nice one
 » Can we make problem F harder and E easier?
•  » » Yeah.E is harder than F.
•  » » Why not just swap the order of them
 » This is my code for question C.I cant figure out why it failed for 12 cases.I worte a recusive fintion for 2^k enumeration and check each condition.Can Anyone help? ll n,m; ll k; ll ans; vectorS; void rec(ll i, vector&pep, vector&test) { if(i==k) { ll x=0; for(int j=0;j 0) && (S[test[j].second] > 0)) { x++; } } ans=max(x,ans); return; } else{ S[pep[i].first]++; rec(i+1, pep, test); S[pep[i].first]--; S[pep[i].second]++; rec(i+1, pep, test); } } void solve() { cin>>n>>m; S = vector(n+1,0); vectortest(m,{0,0}); for(int i=0;i>test[i].first>>test[i].second; } cin>>k; vectorpep(k,{0,0}); for(int i=0;i>pep[i].first>>pep[i].second; } ans=0; rec(0, pep,test); cout<
•  » » You forgot to undo S[pep[i].second]--.
 » What are some similar problems that you factor the N like in D? Any recommendations?
 » 2 months ago, # | ← Rev. 2 →   Video tutorial for Problem A, B
•  » » Trust me no one will watch this.
 » Hey, Can anyone please explain me the question C https://atcoder.jp/contests/abc190/tasks/abc190_cI couldn't figure out what's going on the question. The structure is v peculiar to me since this was my first time participating in this one.I have put more than an hour to understand the question but still couldn't figure it out.
•  » » 2 months ago, # ^ | ← Rev. 2 →   There are K persons and the i-th the persons can increase either value of Ci or Di by 1(which simply means that the two dishes that are given to him, he can increase the value of any one of them by 1).above are the m conditions and the condition i is true if both the i-th dish have value >= 1. so the question is each person should increase the value of the dish in such a way that most conditions are satisfied.
 » Anyone solved E with DSU/Kruskal's algo ?? If yes, please share link to your solution. I am unable to find where mine is going wrong... My solution
•  » » Building a graph is one step of the solution. But then we have to find a path in the graph including all of a given set of vertex. That set has nothing to do with a MST, so it is unclear how Kruskal could help in that problem.
•  » » » Let x and y are two vertices and distance between them is d (from the normal unweighted graph). We will make a new graph with an edge between x and y , weight of that edge will be (d-1). i.e. number of extra gems required for that path. And this new graph will contain only k vertices. This becomes a MST problem then.(Some more manipulation is required of course). Feels like unnecessary calculation, but somehow this was the first approach that struck me after reading the problem. Not sure if its right.