AtCoder Beginner Contest 190 Announcement

4 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

→ Reply

Ozymandias_Orz

4 years ago, # ^ |

I think you mean $$$(n-k*(k-1)/2)/k=a$$$

Thanks, I understood

→ Reply

4 years ago, # ^ |

Thanks for pointing out.

→ Reply

wargang

4 years ago, # ^ |

why did u do *2 in the ans?

→ Reply

4 years ago, # ^ |

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.

→ Reply

wargang

4 years ago, # ^ |

thanks

→ Reply

gnudgnaoh

4 years ago, # ^ |

btw, why is the condition for the for loop (k * (k + 1)) / 2 <= n but not (k * (k — 1)) / 2 <= n ?

→ Reply

4 years ago, # ^ |

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

→ Reply

Kartik_Bhanderi

4 years ago, # ^ |

If we go one step further...

n/k — (k-1)/2 = a

Which 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

→ Reply

4 years 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 ?

→ Reply

amurto

4 years ago, # ^ |

Number of odd divisors * 2

→ Reply

4 years ago, # ^ |

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 ?

→ Reply

amurto

4 years ago, # ^ |

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.

→ Reply

4 years ago, # ^ |

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 ?

→ Reply

rkguptagkp462

4 years 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)

→ Reply

4 years 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.

→ Reply

4 years 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 <iostream>
 
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';
}

→ Reply

rkguptagkp462

4 years ago, # ^ |

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.

→ Reply

amurto

4 years ago, # ^ |

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.

→ Reply

4 years 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<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 .

→ Reply

TiredOfLife

4 years ago, # ^ |

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

→ Reply

tiasmondal

4 years ago, # ^ |

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.

→ Reply

The_blue_penguin

4 years ago, # |

Felt like torturing myself while doing E

→ Reply

Lcyanstars

4 years ago, # ^ |

I agree.

→ Reply

lemongrab

4 years ago, # ^ |

will learn something today

→ Reply

Stream_Cipher

4 years ago, # |

i solved F using Policy Based Data Structure in C++ how to solve it without Policy Based Data Structure

→ Reply

4 years ago, # ^ |

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

→ Reply

chandanagrawal23

4 years ago, # ^ |

not able to observe ans = ans — (a[i] — 1) + (n-a[i]) ... please explain

→ Reply

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

4 years 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 .

→ Reply

dhruv7888

4 years ago, # ^ |

You can use merge sort to find th no. of inversion , The link could be found on Geeks for geeks

→ Reply

chandanagrawal23

4 years ago, # ^ |

link to article please

→ Reply

dhruv7888

4 years ago, # ^ |

→ Reply

chandanagrawal23

4 years ago, # ^ |

Link to your solution please

→ Reply

Stream_Cipher

4 years ago, # ^ |

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

→ Reply

4 years ago, # |

wait! So, B isn't dp?

→ Reply

Lcyanstars

4 years ago, # ^ |

Just do as the problem says.

→ Reply

soumyadeep_pal_21

4 years ago, # ^ |

Wait, it was GRAPH!!

→ Reply

Ozymandias_Orz

4 years ago, # ^ |

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

→ Reply

PRESS_F_2_PAY_RESPECT

4 years ago, # ^ |

orz

→ Reply

4 years 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.

→ Reply

bitset

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

Yeah, I saw that just now. Thanks !!

→ Reply

4 years ago, # |

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

→ Reply

Inferno03

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

DilshodbekX

4 years ago, # ^ |

Hint: l + (l + 1) + ... + r = (l + r) * (r - l + 1) / 2

→ Reply

4 years ago, # ^ |

I've also tried this to find r for each l iterating from -n to n. But it was a brute force approach.

→ Reply

Inferno03

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

→ Reply

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

4 years ago, # ^ |

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.

→ Reply

dhiraj-01

4 years ago, # ^ |

← Rev. 3 →

click

sum = 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++

code

void 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;
}

→ Reply

4 years ago, # ^ |

What is the meaning of "we can factorize ... as ... such that..." ?

→ Reply

dhiraj-01

4 years ago, # ^ |

i mean divisors : 12 => (1, 12), (2, 6), (3, 4)

→ Reply

4 years ago, # ^ |

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.

→ Reply

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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.

→ Reply

ljuba

4 years 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$$$.

→ Reply

pranavsindura

4 years ago, # ^ |

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 = 12

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

N = 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)

Observation

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

→ Reply

johnwick690

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

→ Reply

johnwick690

4 years 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

→ Reply

Matuagkeetarp

4 years ago, # |

Can somebody please help as why my recursive solution is giving TLE in problem C? I don't understand.

→ Reply

4 years ago, # ^ |

Interesting! Looks like you're iterating through $$$k!$$$ instead of $$$2^k$$$ combinations. remove the for loop.

→ Reply

Matuagkeetarp

4 years ago, # ^ |

Yes, I iterated through k!, the unnecessary loop didn't strike me ;(, Thanks :)

→ Reply

4 years ago, # ^ |

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

→ Reply

ScarletS

4 years ago, # |

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

→ Reply

_manvirag

4 years ago, # ^ |

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

→ Reply

BERNARD

4 years ago, # |

Words hiding behind each problem

→ Reply

dhruv7888

4 years ago, # ^ |

This is a nice one

→ Reply

LFCWDDZXUE

4 years ago, # |

Can we make problem F harder and E easier?

→ Reply

Achraf

4 years ago, # ^ |

Yeah.E is harder than F.

→ Reply

cjj490168650

4 years ago, # ^ |

Why not just swap the order of them

→ Reply

ksb_451

4 years ago, # |

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;
vector<ll>S;

void rec(ll i, vector<pll>&pep, vector<pll>&test)
{
	if(i==k)
	{
		ll x=0;
		for(int j=0;j<m;j++)
		{
			if((S[test[j].first] > 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<ll>(n+1,0);
    vector<pll>test(m,{0,0});
    for(int i=0;i<m;i++)
    {
    	cin>>test[i].first>>test[i].second;
    }
    cin>>k;
    vector<pll>pep(k,{0,0});
   	for(int i=0;i<k;i++)
    {
    	cin>>pep[i].first>>pep[i].second;
    }
    ans=0;
    rec(0, pep,test);
    cout<<ans<<endl;
    return;
}

int main()
{
    fast;
    ll tc = 1;
    //IN tc;
    while (tc--)
    {
        solve();
    }
    return 0;
}

→ Reply

My_Programming_Assistant

4 years ago, # |

← Rev. 2 →

Video tutorial for Problem A, B

→ Reply

HELLO_MF

4 years ago, # ^ |

Trust me no one will watch this.

→ Reply

rahulbhatt18

4 years ago, # |

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.

→ Reply

HELLO_MF

4 years 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.

→ Reply

code_OR

4 years ago, # |

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

→ Reply