atcoder_official's blog

AtCoder Beginner Contest 387 Announcement
By atcoder_official, history, 2 days ago, In English

We will hold AtCoder Beginner Contest 387.

We are looking forward to your participation!

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

kool

→ Reply
»
27 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! Looking forward to solve 5 problems.

→ Reply
»
25 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! Looking forward to solve 4+ problems.

→ Reply
»
25 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

I am Chinese.

→ Reply
»
25 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to solved 5 problems!

→ Reply
  • »
    »
    22 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    But...

    The problems this time are so strange, that solving C,D is harder than usual.

    → Reply
»
24 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! Looking forward to solve 4+ problems.

→ Reply
»
24 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I Hope I Can Go To Brown Name

→ Reply
»
24 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to solve 4 or more problems!

→ Reply
»
24 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to accept the problem D!

→ Reply
»
24 hours ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
23 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

I sloved 2 problems.a&b

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is a general approach to deal with this kind of problems called digit dp.

    → Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

why so hard on c

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

E is so hard, even harder than F

→ Reply
»
22 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    22 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    People needs to think but they don't like thinking so you must push them to think, now a lot of contestants got a change to actually exercise problem-solving by struggling with problem C.

    → Reply
»
22 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

Atcoder needs to use more testers!

→ Reply
»
22 hours ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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!

→ Reply
»
22 hours ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved every problem except C today LOL

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 hours ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    ans = count of snake numbers in [10, R] — count of snake numbers in [10, L — 1]

    Submission

    → Reply
    • »
      »
      »
      22 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I meant how to find answer in [10, R]. I solved it using digit DP, is there an easier way of solving it?

      → Reply
      • »
        »
        »
        »
        22 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        brute force for all possible no. of digits

        → Reply
  • »
    »
    22 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    For E, try to think about the divisibility properties of two consecutive numbers. I tried first 10 and 11, 9 and 10 and so on... The good thing I figure out is that if you find some number with sum of digits 8 and divisible by 8, then the next number will have sum of digits 9 and be divisible by 9.

    → Reply
  • »
    »
    21 hour(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    Hint 4
    Hint 5
    → Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Didn't like C and E :(

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 hours ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

why is this failing for problem D: code ?

i cant seem to figure out whats wrong here

→ Reply
  • »
    »
    21 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The minimum distance travelled to reach a node need not be the same from both directions (as explained in the diagram).

    It is also possible that a node is reachable only from 1 direction.

    So it is possible, for a node $$$(i, j)$$$, that the distance to $$$(i, j)$$$ is less when reached after a horizontal step, but the destination can only be reachable when $$$(i, j)$$$ is reached after a vertical step.

    → Reply
    • »
      »
      »
      17 hours ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      thank you so much! i cant believe i missed this.

      → Reply
»
22 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
22 hours ago, # |
  Vote: I like it +15 Vote: I do not like it

After I got stuck in C for 50 minutes:

→ Reply
»
22 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

→ Reply
»
22 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you don't feel good solving a problem and the problem is not valuable, then refrain from solving it.
    So, you should have refrained from solving at least problem D, no matter how that affects the rating. Do you agree?

    → Reply
»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 hour(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am confused about why I got wrong…… help me plz

    → Reply
    • »
      »
      »
      8 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You should consider if it is the same when arriving at a point from left/right and up/down.

      → Reply
      • »
        »
        »
        »
        8 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I had considered it, but I cant construct a sample to prove that my code is wrong.....

        → Reply
»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it 
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

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you should consider the way your start， first bfs starts horizontally，and bfs again vertically， you can try this sample 5 5 ..S.. ..... ..... ...G. .....

    → Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 hours ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    For suppose take example 8695 there is a digit 9 which is greater than 8 so it is not a snake number largest snake number less than 8695 is 8677 (if u find any digit>=first digit) from that position make all digits after that position first digit-1

    calucuate snake numbers less than that number.8677. <8000 it is easy to calculate using combinatorics 7^3+6^3+...1^3+dp[2] dp[2] is no of snake numbers less than 10**2 .

    For 8000-8677 867_ for last digit 7 possibilities

    86__ 0-6 digits possible for 3rd digit and for 4th digit 7 possibilities 7*6=42 ...so on

    → Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    void solve() {
    string l, r;
    cin >> l >> r;
    vector<ll> dp(19, 0);
    ll n = l.size(), m = r.size();
    f(i, 2,19) {
        dp[i] = dp[i - 1];
        ll val=0;
        f(j, 1, 10) {
          val += expo(j, i-1);
        }
        dp[i]+=val;
    }
    auto ans = [&](string s) {
        ll res = 0, sz = s.size(), val = s[0] - '0';
        bool ok = 0;
        char c=s[0];
        c--; 
        for (ll i = 1; i < sz; i++) {
            ll g = s[i] - '0';
            if (g >= val) ok = 1;
            if (ok) s[i] = c;
        }
        res += dp[sz - 1];
        f(i, 1, val) res += expo(i, sz - 1);
        ll mult = 1;
        for (ll i = sz - 1; i >= 1; i--) {
           if(i==sz-1){res+=(s[i]-'0');}
           else res += (s[i] - '0') * expo(val,sz-i-1);
        }
        return res;
    };
    bool ok = 1;
    ll result=ans(r)-ans(l);
    f(i, 1, l.size()) if (l[i] >= l[0]) ok = 0;
    if (ok) result++;
     co(result);
}
    → Reply
»
54 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply