kool

Wow! Looking forward to solve 5 problems.

Wow! Looking forward to solve 4+ problems.

I am Chinese.

Hope to solved 5 problems!

Wow! Looking forward to solve 4+ problems.

I Hope I Can Go To Brown Name

Hope to solve 4 or more problems!

Hope to accept the problem D!

I love the cuteness of the first 3 problems in ABC contests how submissive and obedient they are, I love the feelings of domination.

I sloved 2 problems.a&b

a and b were very easy. but c ? i could not find any technique.

why so hard on c

E is so hard, even harder than F

In my opinion, the order of the problems isn't quite right. $$$D$$$ and $$$F$$$ are classic problems, while $$$C$$$ and $$$E$$$ require more thinking. The results show that fewer contestants solved $$$C$$$ than $$$D$$$, and fewer solved $$$E$$$ than $$$F$$$. The difference is almost double.

Atcoder needs to use more testers!

That's how I thought during this contest:

why there are so many 2025?

why 2025 is in every problem?

why 2025 is so special?

wait

ac-predictor tells that I could get a new rating of 2025?

2025 is so magical!

very educational contest for me. learned that pow doesnt give good precision + dijkstra is god damn slow.

I solved every problem except C today LOL

What is the intended solution of C? And any hint for E please?

now i need to learn about functional graph, it has been haunting me in every contest

Didn't like C and E :(

only able to solve first 2 question.. I'm doomed!!

Forgot to MOD the ans in F ,realised after contest ended :(

For problem G, the composition of formal power series is not needed.

The editorial calculated $$$F\circ G$$$ where $$$F=\sum_{i\leq 0}\frac{x^in^{i-2}}{i!}$$$. Distribute the $$$n^{i-2}$$$ factor into $$$G$$$, i.e., replace $$$G$$$ with $$$\frac{G}{n}$$$, and the problem becomes calculating the exponent of the formal power series.

why is this failing for problem D: code ?

i cant seem to figure out whats wrong here

Problem C was really cool! Took a lot of time but felt very satisfied after solving it.

After I got stuck in C for 50 minutes:

Me while doing A-B : I can solve every problem in the world!!

Me at C : I think this is not the right world..

E is just testcases , D is garbage implementation ,score distribution is random,this contest sucks.

Problem C surprised me.It was my first time to use Digital DP to solve problem C in ABC.

Personally surprised everyone found E hard; I personally found E to be surprisingly easy when considering that you can extend values by inserting 0 in the middle of the number and then working with "easy" divisibility rules that don't care about that (1,2,3,4,5,6,8,9, but especially 2,3 and 8,9 since they're consecutive and 1 and 5 can immediately be shown to be impossible to manipulate this way under the constraints, though pairing 3 and 4 can work as an alternate construction, specifically by extending (111,112) to (1011,1012), (10011, 10012), etc.).

Was only able to solve A,B,D, Wasted a lot of time on C

For problem E, I solved it case by case, by using one of the following patterns:

starting with 11, 80, 62, 53, 35, 26, 17, while ending with all zeros. A really impressive constructive problem!

An explanation for problem C will be appreciated... I don't even understand how I can approach this problem.

please tell me why I got wrong on D， I had wasted a lot of time and I am upset

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

int dd[1010][1010];
char a[1010][1010];
int visited[1010][1010];

int ans = 1e9;

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

	pii start, goal;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 'S')	
				start = {i, j};
			else if (a[i][j] == 'G')
				goal = {i, j};
		}
	}

	visited[start.first][start.second] = 1;

	vector<int> dx = {1, -1, 0, 0, 1, -1, 0, 0};
	vector<int> dy = {0, 0, 1, -1, 0, 0, 1, -1};

	for (int j = 0; j < 4; j++)
	{
		queue<pair<pii, pii>> q; q.push({start, {1145140000, 1919810000}});
		memset(dd, 0, sizeof(dd));
		memset(visited, 0, sizeof(visited));

		while (!q.empty())
		{
			auto moxi = q.front(); 
			q.pop();
			int x = moxi.first.first, y = moxi.first.second;
			pii d = moxi.second;

			for (int i = 0 + j; i < j + 4; i++)
			{
				int xx = x + dx[i], yy = y + dy[i];
				if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && visited[xx][yy] == 0 && a[xx][yy] != '#' && (d.first != dx[i] && d.second != dy[i]))
				{
					visited[xx][yy] = 1;
					q.push({{xx, yy}, {dx[i], dy[i]}});
					dd[xx][yy] = dd[x][y] + 1;
				}
			}
		}

		if (!visited[goal.first][goal.second])	continue ;

		ans = min(ans, dd[goal.first][goal.second]);

	}

	if (ans == 1e9)	cout << -1 << endl;

	else cout << ans << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);

	solve();

	return 0;
}

void solve() {
   
    ll h, w;

    cin >> h >> w;
    vector<string> mat(h);
    pair<ll, ll> start, goal;

    f(i, 0, h) { cin >> mat[i]; }
    f(i, 0, h) {
        f(j, 0, w) {
            if (mat[i][j] == 'S') { start = {i, j}; }
            if (mat[i][j] == 'G') { goal = {i, j}; }
        }
    }
    function<bool(ll, ll)> ok = [&](ll x, ll y) {
        return x >= 0 && x < h && y >= 0 && y < w && mat[x][y] != '#';
    };
    const ll dx[4] = {1, 0, -1, 0};
    const ll dy[4] = {0, 1, 0, -1};
    queue<pair<pair<ll, ll>, ll>> q;
    vector<vi> dis(h, vi(w, Inf));
    q.push({start, -1});
    dis[start.first][start.second] = 0;
    ll result=Inf;
    while (!q.empty()) {
        ll type = q.front().second;
        ll x = q.front().first.first;
        ll y = q.front().first.second;
        q.pop();
        for (ll i = 0; i < 4; i++) {
          ll in=i%2;
           if (in == type) continue; 
            ll a = x + dx[i], b = y + dy[i];
            if (ok(a, b) && dis[a][b] == Inf) {
                dis[a][b] = dis[x][y] + 1;
                q.push({{a, b}, in});
            }
        }
        result =min(result,dis[goal.first][goal.second]);
        
    }
    result =min(result,dis[goal.first][goal.second]);
    if(result==Inf){result=-1;}
    co(result);
    
    
  
}

can anyone explain whats mistake in this code for que D

(This is from Atcoder Editorial for Problem C) Can anyone explain this with an example: If d1 ≤ di for some i (2≤i≤k), then there are none. Otherwise, the (k+1)-th digit should be less than d1 and d_k+1, and the (k+2)-th and succeeding digits should be less than d1, so there are min{d1,d_k+1} × d1^(n−(k+1)) of them.

I'm sorry I didn't quite get editorial of E. So they just throw some constructions, then there are some dots implying that there are some more constructions? And why there won't be other twin numbers?

Can anyone help where i made mistake in the following code in which i try to solve problem d ....

For this code,, 33 case accept and 24 give wrong answer, a case where it give wrong answer is:

5 10 S........# .........# .........# .........# .........G

the correct answer is 17,but the output of my code is 21,,but i cannot find out where and why it give a mistake....

here is my code................

// this is code
void inc(int pos, int d) {
    for (; pos < n; pos |= pos + 1)
        f[pos] += d;
}

/*********************************************| | Hello Programmer : Let's code the universe. | | Kartik Das........... | |*********************************************/

include <bits/stdc++.h>

using namespace std; typedef long long ll;

define Make ios::sync_with_stdio(false) ;

define fast cin.tie(0);

vector<vector>a; ll minsum(vector<vector>&dp1,vector<vector>&dp2,vector<vector>&vis1,vector<vector>&vis2,int row,int col,int n,int m,int sr,int se,int er,int ee,int var){ // cout<<row<<" "<<col<<endl; if(row<0||row>=n)return -2; if(col<0||col>=m)return -2; if(a[row][col]==-1)return -2; if(row==sr&&col==se)return 1; if(var==1&&vis1[row][col]==true)return -2; if(var==0&&vis2[row][col]==true)return -2; if(var==1&&dp1[row][col]!=-1)return dp1[row][col]; if(var==0&&dp2[row][col]!=-1)return dp2[row][col]; if(row!=er||col!=ee){ if(var==1){ vis1[row][col]=true; ll pack,peak; peak=minsum(dp1,dp2,vis1,vis2,row,col-1,n,m,sr,se,er,ee,0); pack=minsum(dp1,dp2,vis1,vis2,row,col+1,n,m,sr,se,er,ee,0); vis1[row][col]=false; if(peak<0&&pack<0)return dp1[row][col]=-2; peak=peak<0?1e12:peak; pack=pack<0?1e12:pack; return dp1[row][col]=1+min(peak,pack); }else{ vis2[row][col]=true; ll pack,peak; peak=minsum(dp1,dp2,vis1,vis2,row+1,col,n,m,sr,se,er,ee,1); pack=minsum(dp1,dp2,vis1,vis2,row-1,col,n,m,sr,se,er,ee,1); vis2[row][col]=false; if(peak<0&&pack<0)return dp2[row][col]=-2; peak=peak<0?1e12:peak; pack=pack<0?1e12:pack; return dp2[row][col]=1+min(peak,pack); } }else{ ll peak1,peak2,peak3,peak4; vis1[row][col]=true; vis2[row][col]=true; peak1=minsum(dp1,dp2,vis1,vis2,row-1,col,n,m,sr,se,er,ee,1); peak2=minsum(dp1,dp2,vis1,vis2,row+1,col,n,m,sr,se,er,ee,1); peak3=minsum(dp1,dp2,vis1,vis2,row,col-1,n,m,sr,se,er,ee,0); peak4=minsum(dp1,dp2,vis1,vis2,row,col+1,n,m,sr,se,er,ee,0); if(peak1<0&&peak2<0&&peak3<0&&peak4<0)return dp1[row][col]=-2; peak1= (peak1==-2)?1e12:peak1; peak2= (peak2==-2)?1e12:peak2; peak3=(peak3==-2)?1e12:peak3; peak4=(peak4==-2)?1e12:peak4; dp1[row][col]=min(peak1,min(peak2,min(peak3,peak4))); return dp1[row][col]; } } void solve() { ll n,m; cin>>n>>m; vector<vector>ch1(n,vector(m,false)),ch2(n,vector(m,false)); vector<vector>dp1(n,vector(m,-1)),dp2(n,vector(m,-1)); a.resize(n,vector(m)); pair<ll,ll>S,R; for(ll i=0;i<n;i++){ string s; cin>>s; for(ll j=0;j<m;j++){ if(s[j]=='.')a[i][j]=0; else if(s[j]=='#')a[i][j]=-1; else{ if(s[j]=='S')S={i,j},a[i][j]=1; else R={i,j},a[i][j]=1; } }

} // cout<<S.first<<" "<<S.second<<endl; ll ans=minsum(dp1,dp2,ch1,ch2,R.first,R.second,n,m,S.first,S.second,R.first,R.second,-1); // for(ll i=0;i<n;i++){ // for(ll j=0;j<m;j++){ // cout<<a[i][j]; // } // cout<<endl; // } if(dp1[R.first][R.second]==-2){cout<<-1<<endl;return;} cout<<dp1[R.first][R.second]<<endl;

}

int main() { Make fast;

long long t=1;
//cin >> t;
while (t--)
{
    solve();
}
return 0;

}

Could someone please take a look at my solution for F? I believe it is O(NM) but it suspiciously TLE on 3 test cases. Link

My approach is quite straightforward (functional graph, cycle detection, dp with prefix sums) and is essentially the same as that of the official solution.

code

can anyone tell whats wrong with this for que 4