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

- Contest URL: https://atcoder.jp/contests/abc315
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230819T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: cn449, physics0523, evima, Nyaan
- Tester: leaf1415, yuto1115
- Rated range: ~ 1999

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

We are looking forward to your participation!

Cool

E is worth 425 only!

Sounds interesting

it's interesting indeed.

p.s. D was kinda terrible for me.

excited

Wish I can solve 7!

Worship the strong.

Did you guys notice that the recent ABC is becoming harder...

Yes,I noticed.

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.

Yeah.

Wish I can solve 6!

I hope I can solve 3 problem.

Me too...

And I

That's great. I passed my third question

Me too.But I just can solve 3 problems.DEFG and Ex is too hard for me.

Look at the Standings! Is the problem F realy easier than the problem D?

E is definitely easier than D.D and F are almost equal but i took more time to solve D.

How can u solve D? I think F<E<<<G<D qwq

so so true

I used something like BFS to solve it in O((n+m)^2),and I think it should be E<F<D

can you provide solution for D? I mean the clarification confused me even more... would be helpful if you could explain your approach

Agree,at least this is true in my friends standings.

I cant agree more

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.

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.

ME TOO

Problem D is too hard. I spend nearly 1 hour to understand the problem.

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

I tried doing a simulation, but couldn't fit it into TL (aside from a couple of small implementation mistakes during the contest), my submission

Maybe there are a couple of possible constant-time optimizations to this approach, not sure

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, submissionDuring 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 notbeen 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)$$$.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.

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

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.

Strangely after removing all the pow functions in your code, it passes in 8ms! Modified solution

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

What's wrong with my solution for ECan someone provide counter case

This may helpThanks a lot! got the issue.

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

I think $$$20$$$ is enough for this problem :)

I wrote an easier solution to problem E

is that correct?

Looks correct,My AC code is similar with you.

thanks

me too

Why does my solution which is very similar to yours cause TLE?

My AC code. Also use DFS, but I wrote a lot of functions to optimize.

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.

Why does my solution which is very similar to yours cause TLE?

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.

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 character

After 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

Can Task G be solved without using __int128?

Is __int128_t allowed in AtCoder?

Yes, it is allowed. Long double leads to WA*8.

D is so hard... Tortured me for over half an hour!!! And E is a lot easier!!!

Hello, for the:problem Bmy solution works on my C++ 17 compiler but does not run on AtCoder providing a compilation error , and a wrong answerMain.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 here

6 | 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<t;i++){

}

middle=(m+1)/2;

for(int i=0;i<t;i++){

}

}

Thank you for your response

change it to:

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.

Help In Problem F For Recursive DP.

Code}

you actually don't need the prev_idx, this is my submission: https://atcoder.jp/contests/abc315/submissions/44770131

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

Can you please explain why my solution is not working? I have used the same states. My submission.

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!

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

that's nice!

Aha. But what if k <= 0? I think in this case you cannot only %C.

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.

Oh, like lower_bound&upper_bound? I think I understand it. thx!

My submission

When do the test cases get released? I got runtime errors on 4 of the test cases and I'm not sure why.

I am getting the same runtime errors on these 4 test cases. Can't figure out why....

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

Link to solution

Wonder if the contest organizers are going to adjust any points based off this.

Interesting. I switched dfs to bfs, and it got accepted. Must be the recursion depth issue.

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 function

private static void dfs(int node) {

if (node == 100_000) return;

}

and

dfs(1) in the main function and was getting runtime error

Dfs with such depth didn't give stackoverflow errors in previous contest. What happened

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

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.

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.

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 size

AC with (1<<26) stack size

Do you know why this is happening?

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

Can anybody please say how to solve F?

anyone to explain D solution more?

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.

yes I did that thanks!

Is codechef dead?

Where's ABC316?

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.

is G solvable with dp, i think it's quite similar to this problem https://cses.fi/problemset/task/1159

upd: i guess it's not possible

for E it is giving tle on 2 testcases anyone help pls me?

my code link

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