Good luck!

E is worth 525 points!

haha！

I hope I can make ABCDE

Good luck for everyone!

gl & hf! (though unrated)

hope you guys get uogrades and good luck ! :)

glhf!

Can indians participate in Atcoder contests?

Good luck for all of you!

Good luck and have fun!

E is worth 525 points and F is worth 550 points,emmm.....

good luck bro

Good luck!

Was it intended, that the main difficulty in problem $$$E$$$ is not to lose precision?

Why do i think problems after C is way harder than before?

can anybody tell why this backtracking logic for d is not working,

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sor(vec) sort(vec.begin(),vec.end())
#define rev(vec) reverse(vec.begin(),vec.end())
#define pb push_back
#define fri(l,r) for(int i=l;i<=r;i++)
#define frj(l,r) for(int j=l;j<=r;j++)
#define rfi(l,r) for(int i=l;i>=r;i--)
#define rfj(l,r) for(int j=l;j>=r;j--)
#define sz(ds) (int)ds.size()
const int mod = 998244353;

#ifdef LOCAL
#include "debug.cpp"
#else
#define deb(...)
#endif


void fn(int ckt, vector<vector<int>>&gridA, map<vector<vector<int>>, int>&vis, vector<vector<int>>&gridB, int&ans) {

    int n = gridA.size(), m = gridA[0].size();
    
    if (gridA == gridB) {
        ans = min(ans, ckt);
        return;
    }

    if(vis[gridA]) return;
    
    vis[gridA]=1;

    // swap two columns
    
    for (int j = 0; j < m - 1; j++) {

        vector<vector<int>> temp = gridA;

        for (int i = 0; i < n; i++) swap(gridA[i][j], gridA[i][j + 1]);

        fn(ckt + 1, gridA, vis, gridB, ans);

        gridA = temp;
    }

    // swap two rows
    for (int i = 0; i < n - 1; i++) {
        vector<vector<int>> temp = gridA;

        swap(gridA[i], gridA[i + 1]);

        fn(ckt + 1, gridA, vis, gridB, ans);

        gridA = temp;
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("error.txt", "w", stderr);
#endif

    int TC = 1;
    while (TC--) {
        int n, m; cin >> n >> m;

        vector<vector<int>> gridA(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) cin >> gridA[i][j];
        }

        vector<vector<int>> gridB(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) cin >> gridB[i][j];
        }

        int ans = LLONG_MAX;
        map<vector<vector<int>>, int> vis;
        fn(0, gridA, vis, gridB, ans);

        if (ans == LLONG_MAX) cout << -1 << endl;
        else cout << ans << endl;
    }
}

Looks like yet another segtree problem F.

imho best ABC contest in a long time, the idea for EF more educational than the usual easy problems, thanks a lot :)

What's wrong in my solution of $$$D$$$?

Can anyone tell why this submission is getting WA? The logic should be correct after all.

Submission link

How to avoid precision problem in E, I spent all my time to implement it but still get WA. :(

On problem E, what makes

cout << (dp.back() * m - sum.back() * sum.back()) / m / m << "\n";

correct while

cout << dp.back() / m - sum.back() * sum.back() / m / m << "\n";

is wrong?

Submission link: AC, WA

can anyone help me understand the problem D , i didn't got any clue regarding how to solve that , during the contest

Can anybody pls tell me .. in which test case my D fails- Submission — https://atcoder.jp/contests/abc332/submissions/48405276

Again :(

Wrong on three cases on problem F. Can someone find an error?

Submission

In problem E, I believe my implementation has issues.I would like to understand where I made a mistake.

/**
   created:   18.11.2023 19:35:36
**/
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double long double
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pp pair<int, int>

#ifdef LOCAL
#include "../debug.hpp"
#else
#define dbg(...) 0
#endif

template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
istream& operator >> (istream &is, T_container &v) {
   for(T &x : v) is >> x; return is;
}

template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T> >;

const int mod = 1e9 + 7, inf = 1e18L + 5;
const string yes = "YES", no = "NO";

const int N  = pow(3, 15);

int score[1 << 16];
int dp[1 << 16][16];

int n, d;
int recur(int mask, int count) {
    if(count == 0) {
        return mask == 0 ? 0 : inf;
    }
    if (dp[mask][count] != -1)
        return dp[mask][count];
    int ans = inf;
    for(int submask = mask; submask; submask = (submask - 1) & mask) {
        int temp = score[submask];
        ans = min(ans, (temp * temp + recur(mask ^ submask, count - 1)));
    }
    return dp[mask][count] = ans;
}

void solve() {
    cin >> n >> d;
    vector<int> a(n);
    cin >> a;
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i <= (1 << n); i++)
        score[i] = 0;
    for(int mask = 1; mask < (1 << n); mask++) {
        for(int i = 0; i < n; i++) {
            if(mask & (1 << i)) {
                score[mask] += a[i];
            }
        }
    }


    double sum = accumulate(all(a), 0ll) * 1.0d;
    double mean = sum / (d*1.0);
    double right = (2.0*mean*sum)/(d*1.0);
    double value = recur((1 << n) - 1, d);
    cout << (double)((value / d*1.0) + (mean * mean) -  right) << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
#ifndef LOCAL
    cin.tie(nullptr);
#endif
    std::cout << std::fixed << std::setprecision(25);
    std::cerr << std::fixed << std::setprecision(10);
// #ifdef LOCAL
    // auto start = std::chrono::high_resolution_clock::now();
// #endif
    int cases = 1;
    // cin >> cases;
    for (int tc = 1; tc <= cases; tc++) {
        solve();
    }
    // #ifdef LOCAL
        // auto stop = std::chrono::high_resolution_clock::now();
        // long double duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start).count();
        // cerr << "Time taken : " << duration / 1e9 << "s" << endl;
    // #endif
    return 0;
}

still showing WA on 6 testcases :(

What is the purpose of problem E?

If I use this

long double ans=(long double)((__int128)D*dp[(1<<n)-1][D]-ave*ave)/(D*D);

That's OK.

But this

long double ans=(long double)dp[(1<<n)-1][D]/D-(long double)ave*ave/(D*D);

is wrong.

I know precision is important but this is too ...

Problem E, I don't understand why the program that uses fewer double get 5 WAs but the program that uses more double get AC?

In the first program, because:

I use a dp to calculate the minimal value of the red part. As all the x are integer, and I can avoid using double in dp, I believe it will be more precise. The second problem simply sums $$$\left(x_{i} - \bar x\right)^2$$$ and uses long double in dp. Why the second program AC but the first not?

why E not output "variance * D * D" as the answer? just to edu us how to "avoid precision problem"？

std:1224489579591846.408203

wolframalpha:1224489579591846.408163

So why does the question ask for an accuracy of 1e-6?

Sorry, but my simple brute force (just do dfs) passed E... Submission.

Can anyone hack it?

In problem D. How the number of operations required to obtain a desired sequence A(A1, A2, ... , An) starting from the sequence (1, 2 .... N) by repeatedly swapping adjacent two elements is given as the inversion number of the permutation A. Can anyone explain that!?

Hi hope you are well!

Could you please check my submissions for problem E, submissions 48412388 and 48412226 should give the same answer mathematically. It does seem like this problem would be better if it requires an output in p/q format rather (maybe mod 1e9+7 or something) rather than output as a fixed point number. Thanks!

Regards Yuhao

Where I can found vedio solutions of today's atcoder contest?

In problem F, how to do the replacement which is mentioned in editorial with lazy segtree.

Can anyone suggest any corner cases for this solution. I am confused.Submission Link

There's a $$$O(lgN)$$$ solution for problem B:

let $$$x = GCD(G, M)$$$, $$$ G=ax; M=bx $$$, so there's a cycle with $$$2a+2b-1$$$ operations. After each cycle, both bottles become empty again. So first we mod $$$K$$$ with $$$2a+2b-1$$$ to make $$$0\lt K\lt 2a+2b-1$$$.

Because bottles only become both empty after each cycle, so in cycle it must formed like this:

• operation type 1/2
• operation type 3

So in each cycle, each operation with odd index is type 1/2 and each operation with even index is type 3.

If we know the total amount of two bottles, we can know how much in each before/after operation type 3:

• Before operation type 3, mug holds as more water as possible.
• After operation type 3, glass holds as more water as possible.

Now we should work out total amount of water.

We can see:

• If total amount less than G, next operation should be type 2(fill water)
• If total amount greator or equal than G, next operation should be type 1(empty water)

If there's i operations of type 2 and j operations of type 1, we got current water amount is $$$iM-jG$$$ . And we can find out:

So we can do all rest calculate in $$$O(1)$$$, the total time complexity will be $$$O(lg(min(G,M)))$$$ for "GCD" function.

submission link

Can anybody explain the second sample in problem C? I think the answer should be 2

The editorial of D is beautiful :)