We will hold AtCoder Beginner Contest 190.

- Contest URL: https://atcoder.jp/contests/abc190
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210130T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: beet, gazelle, kyopro_friends, tatyam, YoshikaMiyafuji
- Rated range: ~ 1999

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

We are looking forward to your participation!

I'll be discussing the problems right after the contest, at https://twitch.tv/AnandOza

Good 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:

The screencast is here, and the (much shorter) editorial is here.

Starting soon!

It's better to swap E and F

How to solve E? I solved F but not E.

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

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).

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]$$$

It is about E:

How to prove the solution of the

first loopof $$$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<<k) or (0 , 1<<k).

Update: I known that because if i have a subset j the i^(1<<j) is solved before cacluate i.

How to solve C? Greedy algorithm doesn't work.

K is small. Use recursion

just brute force all the possible solution

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?

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$$$

If we go one step further...

n/k — (k-1)/2 = aWhich means

kshould be divisor ofnand in order to make LHS = RHS,(k-1)/2should also be an integer =>kis odd...hence final ans would be 2 * No of odd divisors of

nHow 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 ?

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)

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.

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 code8 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

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.

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<y$$$ then it's going to work for only $$$x$$$ and not for $$$y$$$ else RHS won't be positive. odd element in pair $$$(x,y)$$$ will also be factor of $$$N$$$ and thus answer will be 2* count of odd divisor .

thanks amurto,rkguptagkp462,EnterYourName .

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))$$$

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

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

https://www.google.com/amp/s/www.geeksforgeeks.org/counting-inversions/amp/

Link to your solution please

https://atcoder.jp/contests/abc190/submissions/19815910

wait! So, B isn't dp?

Just do as the problem says.

Wait, it was GRAPH!!

No way $$$!$$$ I solved using $$$FFT$$$

orz

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 [300015]'

Yeah, I saw that just now. Thanks !!

D much harder than E and F. Still do not get it.

Even i couldn't get the idea for D. But OEIS helped.

oeis sequence

Did 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.

https://en.wikipedia.org/wiki/Arithmetic_progression

clickcodeWhat 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 get

a = (S-(n*(n-1))/2)/n

We 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.

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 = 5ObservationI 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

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.

My solutions, along with detailed explanations, can be found here :)

Can we see testcases in atcoder. i am new to atcoder.

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

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?

Video tutorial for Problem A, BProblem A

Problem B

Trust me no one will watch this.

Hey, Can anyone please explain me the question C https://atcoder.jp/contests/abc190/tasks/abc190_c

I 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.

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.