### atcoder_official's blog

By atcoder_official, history, 6 months ago,

We will hold KEYENCE Programming Contest 2023 Summer（AtCoder Beginner Contest 315）.

The point values will be 100-200-300-400-425-500-575-625.

We are looking forward to your participation!

• +82

 » 6 months ago, # |   0 Cool
 » 6 months ago, # |   0 E is worth 425 only!
•  » » 6 months ago, # ^ |   0 Sounds interesting
•  » » » 6 months ago, # ^ |   0 it's interesting indeed.p.s. D was kinda terrible for me.
 » 6 months ago, # |   0 excited
 » 6 months ago, # |   0 Wish I can solve 7!
•  » » 6 months ago, # ^ |   0 Worship the strong.
 » 6 months ago, # |   +6 Did you guys notice that the recent ABC is becoming harder...
•  » » 6 months ago, # ^ |   +3 Yes,I noticed.
•  » » 6 months ago, # ^ |   +3 That's true. For someone who's really good, that's nothing. But for me, not being able to quickly make the first three questions really affects the mood of doing the question.
•  » » 6 months ago, # ^ |   0 Yeah.
 » 6 months ago, # |   +4 Wish I can solve 6!
 » 6 months ago, # |   0 I hope I can solve 3 problem.
•  » » 6 months ago, # ^ |   -10 Me too...
•  » » » 6 months ago, # ^ |   0 And I
•  » » » » 6 months ago, # ^ |   0 That's great. I passed my third question
•  » » » » » 6 months ago, # ^ |   0 Me too.But I just can solve 3 problems.DEFG and Ex is too hard for me.
 » 6 months ago, # |   +4 Look at the Standings! Is the problem F realy easier than the problem D?
•  » » 6 months ago, # ^ |   +3 E is definitely easier than D.D and F are almost equal but i took more time to solve D.
•  » » » 6 months ago, # ^ |   +10 How can u solve D? I think F
•  » » » » 6 months ago, # ^ |   0 so so true
•  » » » » 6 months ago, # ^ |   0 I used something like BFS to solve it in O((n+m)^2),and I think it should be E
•  » » » 6 months ago, # ^ |   0 can you provide solution for D? I mean the clarification confused me even more... would be helpful if you could explain your approach
•  » » 6 months ago, # ^ |   0 Agree,at least this is true in my friends standings.
•  » » » 6 months ago, # ^ |   0 I cant agree more
 » 6 months ago, # |   0 D is quite hard...I think E is quite easier than D. I solved ABCE,but spent more than 30 minutes to try D,and WA 2 cases.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Ah, me too. I have solved ABCE, and the problem E is quite easier than D. I got an Accept in one go. But the problem D and F is so hard to me.
•  » » 6 months ago, # ^ |   0 ME TOO
 » 6 months ago, # |   0 Problem D is too hard. I spend nearly 1 hour to understand the problem.
 » 6 months ago, # |   0 is D simple simulation or what? I think that D is harder than F. But I spent more time to D and didn't have enough time to F
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 I tried doing a simulation, but couldn't fit it into TL (aside from a couple of small implementation mistakes during the contest), my submissionMaybe there are a couple of possible constant-time optimizations to this approach, not sure
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 After some time away I've figured it out: the main observation is that after we delete a row (or a column) of characters, this row/column won't appear in other columns (rows), so we can just store 2 sets of remaining rows and columns, and for each new deletion operation decrease occurrences of the current character c only in those columns/rows, if at any point there is only one kind of character left (we can check it with a map or an array of size 26) and there is more than one character — add it for deletion in the future, submission
•  » » 6 months ago, # ^ |   -8 During the simulation, maintain the frequency map of each row/column and a queue for recording what you must remove in the next turn. Only check rows/columns that have not been touched yet. As a result, every cell is accessed at most twice (once for its row, once for its column), and each cell change will take $O(1)$ or $O(\log(h+w))$. The time complexity turns out to be $O(hw)$ or $O(hw\log(h+w)$.
 » 6 months ago, # |   0 Anyone faced issues with strict TL in F? Quick mafs gave me upper bound on skips as 29 but this was TLEing for me. Submitted with skips limit 20 and got AC.
•  » » 6 months ago, # ^ |   0 I got AC with only 43ms runtime for F even after setting the upper bound as 30. Which language do you use? Or maybe recursive solution is too slow? I'll attach my solution for reference.Link to my submission
•  » » » 6 months ago, # ^ |   0 Yeah, I have seen c++ ones with similar runtime. probably doing something stupid somewhere. Will need to log times and compare ig. My TLEd solution here. AC one too gets 900ms idk here.
•  » » » » 6 months ago, # ^ |   0 Strangely after removing all the pow functions in your code, it passes in 8ms! Modified solution
•  » » » » » 6 months ago, # ^ |   +3 Thanks for taking a look. Well, that was unexpected. I assumed pow would be O(log n) at worst. Even it was linear, I was only calculating till exponent of max_skips. Idk but prob something to remember.
 » 6 months ago, # |   0 Not able to figure our why my submission gave TLE for 2 test cases https://atcoder.jp/contests/abc315/submissions/44754723 Even the editorial mentions that we had to optimize checking the number of unique characters in a row/column for which I am simply selecting the first character that is encountered and if any other character is encountered the row/column is skipped.
 » 6 months ago, # |   0 What's wrong with my solution for Eint n; cin >> n; vector adj[n + 1], indeg(n + 1, 0); for(int i = 1; i <= n; i++){ int c; cin >> c; for(int j = 0; j < c; j++){ int b; cin >> b; adj[i].push_back(b); indeg[b]++; } } queue q; q.push(1); vector order; while(!q.empty()){ int u = q.front(); q.pop(); order.push_back(u); for(int v: adj[u]){ indeg[v]--; if(indeg[v] == 0) q.push(v); } } reverse(order.begin(), order.end()); order.pop_back(); for(int val: order) cout << val << ' '; 
•  » » 6 months ago, # ^ |   0 Can someone provide counter case
•  » » » 6 months ago, # ^ |   0 This may help4 2 3 4 2 3 4 0 0 
•  » » » » 6 months ago, # ^ |   0 Thanks a lot! got the issue.
 » 6 months ago, # |   0 task F: if the max total distance to reach n is N×100000 (it is from editorial) than if we take 32 being the max size of second index( the number of skipped checkpoints ) in our dp.32 is enough for it? why 100 (in editorial)?
•  » » 6 months ago, # ^ |   0 I think $20$ is enough for this problem :)
 » 6 months ago, # |   +4 I wrote an easier solution to problem E #include #define int long long using namespace std; int n; bool vis[200005]; vector e[200005]; inline void dfs(int x) { vis[x] = true; for (auto i : e[x]) if (!vis[i]) dfs(i); if (x != 1) cout << x << " "; } signed main() { cin >> n; for (int i = 1, c; i <= n; i++) { cin >> c; for (int j = 1, p; j <= c; j++) { cin >> p; e[i].push_back(p); } } dfs(1); return 0; } is that correct?
•  » » 6 months ago, # ^ |   0 Looks correct,My AC code is similar with you.
•  » » » 6 months ago, # ^ |   0 thanks
•  » » » 6 months ago, # ^ |   0 me too
•  » » » 6 months ago, # ^ |   0 Why does my solution which is very similar to yours cause TLE? #include using namespace std; vector dfs(const vector> &nodes, const size_t n, vector &toRead, vector &alreadyRead) { if (alreadyRead[n - 1]) { return toRead; } alreadyRead[n - 1] = true; for (const auto &p : nodes[n - 1]) { dfs(nodes, p, toRead, alreadyRead); } toRead.push_back(n); return toRead; } vector dfs(const vector> &nodes) { vector toRead; vector alreadyRead(nodes.size()); return dfs(nodes, 1, toRead, alreadyRead); } int main() { size_t n; cin >> n; vector> books(n); for (auto &b : books) { size_t c; cin >> c; while (c--) { size_t p; cin >> p; b.insert(p); } } auto s = dfs(books); s.pop_back(); for (auto it = s.begin(); it != s.end(); ++it) { cout << *it << " "; } cout << "\n"; } 
•  » » 6 months ago, # ^ |   0 My AC code. Also use DFS, but I wrote a lot of functions to optimize.
•  » » 6 months ago, # ^ |   0 I think it's true. But the method of the editorial is much more complex, and the code is longer. I think they should change the order of D and E.
•  » » 6 months ago, # ^ |   0 Why does my solution which is very similar to yours cause TLE? #include using namespace std; vector dfs(const vector> &nodes, const size_t n, vector &toRead, vector &alreadyRead) { if (alreadyRead[n - 1]) { return toRead; } alreadyRead[n - 1] = true; for (const auto &p : nodes[n - 1]) { dfs(nodes, p, toRead, alreadyRead); } toRead.push_back(n); return toRead; } vector dfs(const vector> &nodes) { vector toRead; vector alreadyRead(nodes.size()); return dfs(nodes, 1, toRead, alreadyRead); } int main() { size_t n; cin >> n; vector> books(n); for (auto &b : books) { size_t c; cin >> c; while (c--) { size_t p; cin >> p; b.insert(p); } } auto s = dfs(books); s.pop_back(); for (auto it = s.begin(); it != s.end(); ++it) { cout << *it << " "; } cout << "\n"; } 
 » 6 months ago, # |   +13 I thought in problem F, the order of visiting can be shuffled, and are wondering why so many contestants pass problem F. When realizing the real meaning of ordered visiting in the last 1 minute before the contest end, I just want to kill myself.
 » 6 months ago, # |   0 In D, I thought it is as graph problem, connecting (i,j) to 1. First cell which is left to it and have same character 2. First cell which is right of it and have same character 3. First cell above it and have same character 4. First cell below it and have same characterAfter making these connections, I just traversed the formed graph and count size of components. If size >1 , cells in that component should be removed. This causes TLE on some cases and WA on some.I don't know what's wrong in this
 » 6 months ago, # |   0 Can Task G be solved without using __int128?
•  » » 6 months ago, # ^ |   0 Is __int128_t allowed in AtCoder?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Yes, it is allowed. Long double leads to WA*8.
 » 6 months ago, # |   0 D is so hard... Tortured me for over half an hour!!! And E is a lot easier!!!
 » 6 months ago, # | ← Rev. 2 →   0 Hello, for the problem B my solution works on my C++ 17 compiler but does not run on AtCoder providing a compilation error , and a wrong answer :Main.cpp: In function ‘int main()’:Main.cpp:11:6: warning: ‘m’ may be used uninitialized [-Wmaybe-uninitialized]11 | m+=arr[i]; | ~^~~~~~~~Main.cpp:6:5: note: ‘m’ was declared here6 | int m,t,middle;Can you explain why the following submission does not work :(header files)using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0);int m,t,middle;cin>>t;int arr[t];for(int i=0;i>arr[i]; m+=arr[i];}middle=(m+1)/2;for(int i=0;i
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 int m,t,middle; change it to: int m=0,t,middle; 
 » 6 months ago, # | ← Rev. 3 →   0 Question E,i used topological sort using DFS.Atcoder please increase the java stack depth, as i had to explicitly increase it to get the AC.
 » 6 months ago, # |   -8 Help In Problem F For Recursive DP. Codedouble dp[maxn][25]; double rec(int prev_idx,int cur_idx,int skipped) { if (skipped >= 22 || cur_idx >= n) { return 1E9; } if(dp[cur_idx][skipped] != -1)return dp[cur_idx][skipped]; if(cur_idx == n - 1) { double dis = calc(prev_idx,cur_idx); double val = 0.0; if(skipped > 0) { int c = skipped - 1; val = (1 << c); } return dp[cur_idx][skipped] = (dis + val); } double left = rec(prev_idx, cur_idx + 1,skipped + 1); double right = rec(cur_idx , cur_idx + 1,skipped) + calc(prev_idx,cur_idx); return dp[cur_idx][skipped] = min(left,right); }
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 you actually don't need the prev_idx, this is my submission: https://atcoder.jp/contests/abc315/submissions/44770131let dp[i][skipped] minimum value to get from i to n having skipped "skipped" stations.j from 1 to 30 dp[i][skipped]=min of( cost(i,i+j)+ dp[i+j][skipped+j])and in the base cases if skipped>=30 just return something BIG else if i==n-1 return 2^(skipped-1); and that's it.
•  » » » 6 months ago, # ^ |   0 Can you please explain why my solution is not working? I have used the same states. My submission.
 » 6 months ago, # |   0 D was a bit hard. I ended up thinking the solution to D for the whole contest and now after reading F I regret not taking a look at it during contest. Overall good contest!
 » 6 months ago, # | ← Rev. 3 →   +29 My solution doesn't use extended_gcd or diophantine_equations for problem G. My solution : We can fix A*i since n<=1e6. Let's call Y = X-A*i. We need to solve this equation: B*j + C*k = Y We can observe that (B*j) % C must be equal to Y % C. I maintained a map of vectors to store all (B*j)%Cs The rest of the solution is doing binary search on the vector corresponding Y % C
•  » » 6 months ago, # ^ |   0 that's nice!
•  » » 6 months ago, # ^ |   +5 Aha. But what if k <= 0? I think in this case you cannot only %C.
•  » » » 6 months ago, # ^ |   0 We do 2 binary_search on our sorted vector (map[Y%c] => vector of B*j). Notice that k = (Y-B*j)/c In the first binary_search, we find the last B*j smaller than Y (don't forget that Y=X-A*i). This way (Y-B*j)/ C can't be <=0. In the second binary search, we find the first B * j that (Y-B*j)/ C is smaller or equal to <=n.
•  » » » » 6 months ago, # ^ |   +5 Oh, like lower_bound&upper_bound? I think I understand it. thx!
•  » » » 6 months ago, # ^ |   0
 » 6 months ago, # |   0 When do the test cases get released? I got runtime errors on 4 of the test cases and I'm not sure why.
•  » » 6 months ago, # ^ |   0 I am getting the same runtime errors on these 4 test cases. Can't figure out why....
•  » » » 6 months ago, # ^ |   0 After looking at accepted solutions, turns out we need to manually adjust the recursion limit of the program to something higher than its default value. I added two lines to the top of my program and it passed import sys sys.setrecursionlimit(10**8) Link to solutionWonder if the contest organizers are going to adjust any points based off this.
•  » » » » 6 months ago, # ^ |   0 Interesting. I switched dfs to bfs, and it got accepted. Must be the recursion depth issue.
 » 6 months ago, # | ← Rev. 5 →   +13 Using dfs with depth in tens of thousands was giving runtime error for Java code. This doesn't happen in previous contest. I double checked on an accepted question with this functionprivate static void dfs(int node) {if (node == 100_000) return; dfs(node + 1);}and dfs(1) in the main function and was getting runtime errorDfs with such depth didn't give stackoverflow errors in previous contest. What happened
•  » » 6 months ago, # ^ |   0 Yeah, it must be a recent atcoder platform judge change. I wonder if it is because atcoder only supports Java17 now, it used to support Java8 as well. I did not run into this recursion depth issue back then.......
•  » » 6 months ago, # ^ |   +8 I noticed that on older contest, I used Java 11 and it's not available on newer contest.It may be caused by the -Xss JVM arguments. May be worth fixing this issue or adding back java 11.
•  » » » 6 months ago, # ^ |   +16 atcoder_official Can you guys look into this issue? Recursive call in Java on AtCoder sometimes result in runtime error now due to the recursion stack depth. It used to work before switched to only Java 17 on the platform.
•  » » 6 months ago, # ^ | ← Rev. 6 →   +1 This is because of small stack size for recursive calls. We can create a new thread and assign stack size. (1<<26) stack size is sufficent for most recursive tasks.RTE with default stack sizeAC with (1<<26) stack size
•  » » » 6 months ago, # ^ |   0 Do you know why this is happening?
•  » » » » 6 months ago, # ^ | ← Rev. 4 →   0 Quite strange, with 1024mb its giving MLE and 256mb AC... i have no clue.But if we reduce thread stack size to 1<<26 it get AC 219687128
 » 6 months ago, # | ← Rev. 2 →   0 Can anybody please say how to solve F?
 » 6 months ago, # |   0 anyone to explain D solution more?
•  » » 6 months ago, # ^ |   0 Starting with a brute force solution. Then optimize it by replacing the original matrix with some small arrays which hold the frequency tables of rows and columns.
•  » » » 6 months ago, # ^ |   0 yes I did that thanks!
 » 6 months ago, # |   0 Is codechef dead?
 » 6 months ago, # |   +14 Where's ABC316?
 » 6 months ago, # |   0 Can someone please explain why my solution for problem F is not working? I have used dp[current index][no. of skipped checkpoints] = minimum distance of path; just as the editorial has mentioned. My Submission.
 » 6 months ago, # | ← Rev. 4 →   0 is G solvable with dp, i think it's quite similar to this problem https://cses.fi/problemset/task/1159upd: i guess it's not possible
 » 6 months ago, # |   0 for E it is giving tle on 2 testcases anyone help pls me?my code link `Your code here... #include #define int long long #define double long double #define superSLOW ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define TxtIO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #define endl '\n' #define pb push_back #define ff first #define ss second #define pii pair const int mod=1e9+7; const int inf=1e18; using namespace std; void dijkstra(vector>> &g , vector &dis , int node){ priority_queue,vector>,greater>>pq; pq.push({0,node}); dis[node]=0; while(!pq.empty()){ auto u=pq.top();pq.pop(); int node=u.ss; int d=u.ff; if(dis[node](dis[node]+ch.ss)){ dis[ch.ff]=dis[node]+ch.ss; pq.push({dis[ch.ff],ch.ff}); } } } } int32_t main() { // your code goes hereTxtIO; superSLOW; int n;cin>>n; vector>g(n+1); for(int i=1;i<=n;i++){ int x;cin>>x; while(x--){ int y;cin>>y; g[i].pb({y,-1}); } } vectordis(n+1,inf); dijkstra(g,dis,1); vectorans; for(int i=1;i<=n;i++){ ans.pb({dis[i],i}); } sort(ans.begin(),ans.end()); for(int i=0;i
 » 6 months ago, # |   0 I used DFS for E, but I get TLE for some tests. Can someone tell me what I'm doing wrong? https://atcoder.jp/contests/abc315/submissions/44953559