atcoder_official's blog

AtCoder Beginner Contest 387 Announcement
By atcoder_official, history, 16 months ago, In English

We will hold AtCoder Beginner Contest 387.

We are looking forward to your participation!

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

Comments Comments (52)
| Write comment?
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Wow! Looking forward to solve 5 problems.

→ Reply
»
16 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I am Chinese.

→ Reply
»
16 months ago, hide # |
← 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
»
16 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

I sloved 2 problems.a&b

→ Reply
»
16 months ago, hide # |
 
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
  • »
    »
    16 months ago, hide # ^ |
     
    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
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

E is so hard, even harder than F

→ Reply
»
16 months ago, hide # |
← 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
  • »
    »
    16 months ago, hide # ^ |
     
    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
»
16 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Atcoder needs to use more testers!

→ Reply
»
16 months ago, hide # |
← 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
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I solved every problem except C today LOL

→ Reply
»
16 months ago, hide # |
 
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
  • »
    »
    16 months ago, hide # ^ |
     
    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
  • »
    »
    16 months ago, hide # ^ |
    ← 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
  • »
    »
    16 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +2 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    Hint 4
    Hint 5
    → Reply
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Didn't like C and E :(

→ Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
 
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
  • »
    »
    16 months ago, hide # ^ |
     
    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
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

After I got stuck in C for 50 minutes:

→ Reply
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
← 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
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
 
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
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      16 months ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        16 months ago, hide # ^ |
         
        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
        • »
          »
          »
          »
          »
          16 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          You just considered it cannot move as the same direction.But you should split every point into two points,which represent the last step is left/right or up/down.Because they are different but your code regards it as the same.

          → Reply
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Stuck with C for 40 min. Maybe AtCoder should swap E and F?

→ Reply
»
16 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Can anyone please tell me what is wrong with my implementation of problem C, my approach is almost same as given in editorial. submission

→ Reply