### chokudai's blog

By chokudai, history, 3 years 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!

• +82

| Write comment?
 » 3 years ago, # |   +42 I'll be discussing the problems right after the contest, at https://twitch.tv/AnandOzaGood luck everyone!
•  » » 3 years ago, # ^ |   +9 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.
 » 3 years ago, # |   +18 ... 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:
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 The screencast is here, and the (much shorter) editorial is here.
 » 3 years ago, # |   0 Starting soon!
 » 3 years ago, # |   +38 It's better to swap E and F
 » 3 years ago, # |   +7 How to solve E? I solved F but not E.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » 3 years ago, # ^ |   0 how to solve F? got TLE at 2nd TC
•  » » 3 years ago, # ^ |   0 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).
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 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]$
•  » » 3 years ago, # ^ | ← Rev. 6 →   0 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<
 » 3 years ago, # |   +1 How to solve C? Greedy algorithm doesn't work.
•  » » 3 years ago, # ^ |   +1 K is small. Use recursion
•  » » 3 years ago, # ^ |   0 just brute force all the possible solution
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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)
 » 3 years ago, # |   0 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?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +16 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
•  » » » 3 years ago, # ^ |   +3 I think you mean $(n-k*(k-1)/2)/k=a$Thanks, I understood
•  » » » » 3 years ago, # ^ |   0 Thanks for pointing out.
•  » » » 3 years ago, # ^ |   0 why did u do *2 in the ans?
•  » » » » 3 years ago, # ^ |   +3 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.
•  » » » » » 3 years ago, # ^ |   +3 thanks
•  » » » 3 years ago, # ^ |   0 btw, why is the condition for the for loop (k * (k + 1)) / 2 <= n but not (k * (k — 1)) / 2 <= n ?
•  » » » » 3 years ago, # ^ |   +3 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$
•  » » » 3 years ago, # ^ |   +6 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
 » 3 years ago, # | ← Rev. 3 →   0 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 ?
•  » » 3 years ago, # ^ |   +4 Number of odd divisors * 2
•  » » » 3 years ago, # ^ |   0 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 ?
•  » » » » 3 years ago, # ^ |   +8 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.
•  » » » » » 3 years ago, # ^ |   0 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 ?
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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)
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 6 →   +3 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'; } 
•  » » » » » » » » 3 years ago, # ^ |   +3 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.
•  » » » » » » » » 3 years ago, # ^ |   +3 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.
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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 •  » » 3 years ago, # ^ | +1 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))$•  » » 3 years ago, # ^ | +3 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.  » 3 years ago, # | +5 Felt like torturing myself while doing E •  » » 3 years ago, # ^ | 0 I agree. •  » » 3 years ago, # ^ | 0 will learn something today  » 3 years ago, # | +1 i solved F using Policy Based Data Structure in C++ how to solve it without Policy Based Data Structure •  » » 3 years ago, # ^ | +2 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])$. •  » » » 3 years ago, # ^ | 0 not able to observe ans = ans — (a[i] — 1) + (n-a[i]) ... please explain •  » » » » 3 years ago, # ^ | ← Rev. 2 → 0 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 . •  » » 3 years ago, # ^ | 0 You can use merge sort to find th no. of inversion , The link could be found on Geeks for geeks •  » » » 3 years ago, # ^ | 0 link to article please •  » » » » 3 years ago, # ^ | 0 •  » » 3 years ago, # ^ | 0 Link to your solution please •  » » » 3 years ago, # ^ | 0  » 3 years ago, # | 0 wait! So, B isn't dp? •  » » 3 years ago, # ^ | 0 Just do as the problem says. •  » » 3 years ago, # ^ | 0 Wait, it was GRAPH!! •  » » » 3 years ago, # ^ | +4 No way$!$I solved using$FFT$•  » » » » 3 years ago, # ^ | +2 orz  » 3 years ago, # | ← Rev. 2 → 0 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. •  » » 3 years ago, # ^ | 0 Hey, running your code on my system gives this error: f.cpp:122:15: runtime error: index 300016 out of bounds for type 'int [300015]' •  » » » 3 years ago, # ^ | 0 Yeah, I saw that just now. Thanks !!  » 3 years ago, # | +1 D much harder than E and F. Still do not get it. •  » » 3 years ago, # ^ | ← Rev. 2 → 0 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 •  » » 3 years ago, # ^ | 0 Hint: l + (l + 1) + ... + r = (l + r) * (r - l + 1) / 2 •  » » » 3 years ago, # ^ | +1 I've also tried this to find r for each l iterating from -n to n. But it was a brute force approach. •  » » » » 3 years ago, # ^ | -8 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. •  » » » » » 3 years ago, # ^ | +1 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. •  » » 3 years ago, # ^ | ← Rev. 3 → +1 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; }  •  » » » 3 years ago, # ^ | 0 What is the meaning of "we can factorize ... as ... such that..." ? •  » » » » 3 years ago, # ^ | 0 i mean divisors : 12 => (1, 12), (2, 6), (3, 4) •  » » 3 years ago, # ^ | +1 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. •  » » » 3 years ago, # ^ | 0 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"? •  » » » » 3 years ago, # ^ | 0 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. •  » » 3 years ago, # ^ | ← Rev. 2 → +1 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$. •  » » 3 years ago, # ^ | 0 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.  •  » » 3 years ago, # ^ | +3 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 •  » » » 3 years ago, # ^ | 0 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 •  » » » » 3 years ago, # ^ | ← Rev. 4 → 0 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  » 3 years ago, # | 0 Can somebody please help as why my recursive solution is giving TLE in problem C? I don't understand. •  » » 3 years ago, # ^ | 0 Interesting! Looks like you're iterating through$k!$instead of$2^k$combinations. remove the for loop. •  » » » 3 years ago, # ^ | 0 Yes, I iterated through k!, the unnecessary loop didn't strike me ;(, Thanks :) •  » » » » 3 years ago, # ^ | +1 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 } }   » 3 years ago, # | +7 My solutions, along with detailed explanations, can be found here :) •  » » 3 years ago, # ^ | 0 Can we see testcases in atcoder. i am new to atcoder.  » 3 years ago, # | +7 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
•  » » 3 years ago, # ^ |   0 This is a nice one
 » 3 years ago, # |   +2 Can we make problem F harder and E easier?
•  » » 3 years ago, # ^ |   +3 Yeah.E is harder than F.
•  » » 3 years ago, # ^ |   +5 Why not just swap the order of them
 » 3 years ago, # |   0 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<
 » 3 years ago, # | ← Rev. 2 →   0 Video tutorial for Problem A, B
•  » » 3 years ago, # ^ |   +9 Trust me no one will watch this.
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 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.
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 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.