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.

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

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

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)

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

Number of odd divisors * 2

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.

I agree.

will learn something today

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

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

Link to your solution please

Just do as the problem says.

Wait, it was GRAPH!!

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

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

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

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

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

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.

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

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.

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

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

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

This is a nice one

Yeah.E is harder than F.

Why not just swap the order of them

Trust me no one will watch this.

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.

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.