i am just a chill guy who participates in every atcoder contest

How to do F :( ?

Anyone, How to do F??

WTF MAN 1 TESTCASE WRONG ANSWER ??? Please help

$$$\mathcal O(n^2)$$$ solution passed problem G lol. 60727006.

Can someone explain why the two pointers method doesn't work for task D?

My code

Did anyone solve F using FFT ??

can someone suggest any testcase for which this code fails?

60750107

Hi all,

Problem : E

Kindly assists, I was unable to figure out why the code is not passing the if (s[nx][ny] < now/r) condition in the first test case. Furthermore, after reviewing the editorial I made changes in the if condition as if(s[nx][ny] < (now+r-1)/r) doesn't seems to pass the below test case:

3 3 2
2 2
14 6 9
4 9 20
17 15 7
Expected: 28
My result: 13

Here is the code:

#include<bits/stdc++.h>
using namespace std;
using ll = long double;
#define rep(i, x) for(int i = 0; i < int(x); i++)
#define all(x) (x).begin(), (x).end()

template<class T> inline bool chmax(T &a, T b){if (a < b) {a = b;return 1;}return 0;}
template<class T> inline bool chmin(T &a, T b){if (a > b) {a = b;return 1;}return 0;}

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w; double r;
    int p, q;
    cin >> h >> w >> r >> p >> q;
    p--, q--;
    vector<vector<ll>> s(h, vector<ll>(w));
    rep(i, h) rep(j, w) {
        cin >> s[i][j];
    }

    vector seen(h, vector(w, false));
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;

    Q.emplace(s[p][q], p*w + q);
    seen[p][q] = true;
    ll ret = s[p][q];

    while (!Q.empty()) {
        auto [now, idx] = Q.top();
        Q.pop();
        int x = idx/w, y = idx%w;
        rep(di, 4) {
            int nx = x + dx[di], ny = y + dy[di];

            if (nx >= 0 && ny >= 0 && nx < h && ny < w && !seen[nx][ny]) {
                // cout << "O " << nx << " " << ny << endl;
                if (s[nx][ny] * r <= now) {
                    // cout << "I " << nx << " " << ny << endl;
                    chmax(ret, now + s[nx][ny]);
                    seen[nx][ny] = true;
                    Q.emplace(now + s[nx][ny], nx*w + ny);
                }
            }
        }
    }
 
    cout << ret << endl;
    return 0;
}

Thanks in advance.

Can anyone explain solution to problem F its a nice problem

How to E??

can any one find runtime bug in my code please it helpful for me.. problem E: https://atcoder.jp/contests/abc384/submissions/60778905

I found the data for question D to be weak, for example, in the example below, the answer should be yes, but in some code the answer is no, and AC is obtained 3 7 1 7 2

Why it is failing E problem

ok problems are good and I respect physics0523 a lot as he was my co-ordinator in TheForces round 26.That's why I won't be over expressive but honestly statement writing wasn't good , statements weren't made clear.In problem $$$E$$$ it really wasn't good especially the part of newly adjacent cells, like no where in the statement it was mentioned old adjacent cells persist , I had to understand by reading sample explanation, but why??The main idea of what the problem wants should be in statement not in sample explanation right?

I wrote a solution using plain BFS, with taking the smallest neighbour and breaking if the smallest neighbour is larger than the criteria. I got WA many times, then read editorial and people's suggestions here and saw that overflow might be happening. I used 128 int type as well, but still getting WA. Is the issue with my logic?

#include <iostream>
#include <vector>
#include <set>
#include <cmath>

using namespace std;

#define ll unsigned long long
#define ppi pair<int, pair<int, int>>
#define vll vector<ll>
#define vvll vector<vll>

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    int p, q;
    cin >> p >> q;
    p--, q--; // zero-based indexing

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

    vvll vis(n, vll(m, 0)); // Initialize visited array

    set<ppi> st;
    st.insert({arr[p][q], {p, q}});
    vis[p][q] = 1;

    ll ans = 0;
    bool is_first = true;

    while (!st.empty()) {
        ppi current = *st.begin();
        st.erase(st.begin());

        __int128_t potential_ans = (__int128_t)current.first * (__int128_t)k;
        __int128_t current_ans = (__int128_t)ans;

        if (is_first || current_ans > potential_ans) {
            ans += current.first;
            is_first = false;
        } else {
            break;
        }

        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (abs(i) + abs(j) != 1) continue;

                int x = current.second.first + i;
                int y = current.second.second + j;

                if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y]) {
                    st.insert({arr[x][y], {x, y}});
                    vis[x][y] = 1;
                }
            }
        }
    }

    cout << ans;
}

int main() {
    solve();
    return 0;
}

Would be grateful if somebody can help with this one. I am trying to get it AC for the past 1 hr.

Finally easier G.

why rating is not updated?

I had a nice solution forProblem D, simply run a loop from 0 to 2n, taking the sum of array elements and check if the remainder = (s%(totalsum)) occurs in this course, Implementation: https://pastebin.com/nYJd9DEG

Can anyone share their idea for F

Can anyone explain why this is giving TLE for problem F?

Submission

There's also a funny solution for problem F:

Our goal is to find a sum $$$ T = \sum_{i=1}^N \sum_{j=i}^N \frac{A_i + A_j}{2^{k_{ij}}} $$$, where $$$ k_{ij} $$$ is largest s.t. $$$ 2^{k_{ij}} $$$ divides $$$ A_i + A_j $$$.

Let's firstly calculate sum $$$S = \sum_{i=1}^N \sum_{j=i}^N \sum_{t=0}^{k_{ij}} \frac{A_i + A_j}{2^{t}} $$$ (can be done in $$$O(n \ log(C))$$$, where $$$ C = 2 * max(A_1, ..., A_N)$$$).

Now, let's fix pair $$$(i,j)$$$. It's occurence into $$$S$$$ would be:

$$$ \sum_{t=0}^{k_{ij}} \frac{A_i + A_j}{2^{t}} = (A_i + A_j) * ( \sum_{t=0}^{k_{ij}} 2^{-t} ) = (A_i + A_j) * (\frac{\sum_{t=0}^{k_{ij}} 2^{t} }{2^{k_{ij}}} ) = (A_i + A_j) * ( \frac{2^{k_{ij}+1} - 1}{2^{k_{ij}}} ) = (A_i + A_j) * ( 2 - \frac{1}{2^{k_{ij}}} ) $$$.

Thus, $$$S = \sum_{i=1}^N \sum_{j=i}^N \sum_{t=0}^{k_{ij}} \frac{A_i + A_j}{2^{t}} = \sum_{i=1}^N \sum_{j=i}^N (A_i + A_j) * ( 2 - \frac{1}{2^{k_{ij}}} ) = ( \sum_{i=1}^N \sum_{j=i}^N 2 * (A_i + A_j) ) - T = 2 * ( \sum_{i=1}^N A_i * (N + 1) ) - T $$$.

Thus, $$$ T = 2 * ( \sum_{i=1}^N A_i * (N + 1) ) - S $$$. Total complexity — $$$O(n \ log(C))$$$. My solution: 60808479.

Can anyone help me please, my solution for E is giving wrong even though I'm performing BFS with int64 everywhere, and its always the last 2 out of the 65 test cases 60833551