yessir

The idea is that it will only be optimal to use Kakomon Gym (multiply by A) a few times, after which it will always be better to add instead of multiply. You can simulate the first part while x*a <= x+b, then use division to find out the number of operations of the second type to do.

Sum up the squares of elements in a long long, then cast to long double and take square root.

The easier thing would be to use Python for questions like D, or Java's BigInteger.

Let DP[n][m][b] be the number of ways to build a graph with n labeled nodes and m unlabeled edges with b being a flag for restricting the size of the maximal connected component.

From there at each iteration and to avoid double counting you only look at the components covering the first node.

For example if I want a component of size 5 and n = 10 first I find the number of ways I can choose nodes to form this component which is 9 choose 4 (node #1 is already included). Then I find the number of way to build a path (5! / 2) or a cycle (4! / 2) and call the appropriate state.

Travelling Salesman Problem using dynamic programming

Well, I just honestly implemented dp for traveling salesman problem... I guess it was the intended solution

I guess the main difference in the problem was to visit at least once, while in standard TSP it is exactly once.

So consider if the problem was a general directed graph, then the standard DP solution would not have worked, but since the shortest path between two vertices, in this case, is the same as their direct edge between them, the problem had the exact same solution.

if n<=20 its 95% of the time bitmask dp

Can you share the link? I searched for such one, but did not found any, and was not able to implement a bugfree version.

I don't think you need floyd warshall. Since the distance metric used always gives shortest path between two vertices.

I solved it using dp

my code :

#include <bits/stdc++.h>

using namespace std;

const int N = 17, M = 272144;
int x[N], y[N], z[N];
int dp[M][N];

int dis(int f, int s) {
    return abs(x[f] - x[s]) + abs(y[f] - y[s]) + max(0, z[s] - z[f]);
}

int solve(int lst, vector <bool> v, bool is_back = false) {
    if (is_back) {
        if (lst == 0)
            return 0;
    }
    int h = 0;
    for (int i = 0; i < v.size(); i++) {
        h *= 2;
        h += (int)v[i];
    }
    h *= 2;
    h += (int)is_back;
    if (dp[h][lst] != -1)
        return dp[h][lst];
    bool f = true;
    for (auto x : v)
        if (!x)
            f = false;
    if (lst == 0 && f) {
        return 0;
    }
    if (f) {
        for (int i = 0; i < v.size(); i++) {
            v[i] = false;
        }
        v[lst] = true;
        return solve(lst, v, true);
    }
    int ans = INT_MAX;
    for (int i = 0; i < v.size(); i++) {
        if (v[i])
            continue;
        v[i] = true;
        int t = solve(i, v, is_back) + dis(lst, i);
        ans = min(ans, t);
        v[i] = false;
    }
    return dp[h][lst] = ans;
}

int32_t main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> z[i];
    }
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            dp[i][j] = -1;
    vector <bool> v;
    for (int i = 0; i < n; i++)
        v.push_back(false);
    v[0] = true;
    cout << solve(0, v);
}

Try long double instead of double, and sqrt instead of pow.

Yes

Because a * x will overflow for big cases, leading to a negative number and an endless condition

Solution Just think about a short case and try to work on it. Keep a check on overflows.

For bigger values of n, i * i will overflow and will result in i * i <= n being true.

consider x as 1e18 and a as 1e9. It will overflow range of unsigned long long

Use dynamic programming with bitmask, dp[i][j] is the min cost of visting all cities specified by state i with the last visiting city as j. For a given dp[i][j], if we already know its result, we use it to make the next hop. For all valid hops from a city that has been included in i, to a city j from 0 to n — 1, update dp[next][j] where next is i | (1 << j).

The final answer is dp[(1 << n) — 1][0].

There are a few problems:

The error with abs function is due to ll being defined as unsigned.

Then after this, you will be getting a WA because you have your cd as cd=max(cd,x) instead of cd=max(cd,abs(x))

After that, you still are getting a WA because you are submitting problem B's solution for problem A :)

For C problem,You are running a loop N times which is too slow as N can be upto 10^12.Here you need to run a loop till sqrt(N) and then it will work. Here is my submission:-

https://atcoder.jp/contests/abc180/submissions/17445269

To understand why this works you can see this tutorial:-

https://www.youtube.com/watch?v=ga9N_ey4La4&list=PL2q4fbVm1Ik4liHX78IRslXzUr8z5QxsG&index=2