We will hold Toyota Programming Contest 2024#9（AtCoder Beginner Contest 370）.

- Contest URL: https://atcoder.jp/contests/abc370
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240907T2100&p1=248
- Duration: 100 minutes
- Writer: Nyaan, cn449, ynymxiaolongbao
- Tester: sotanishy, MtSaka
- Rated range: ~ 1999
- The point values: 100-200-300-400-475-575-650

We are looking forward to your participation!

Seems to be the highest point value of F+G in recent contests. Good luck :D

I love atcoder problemset

till what problem are you able to solve generally?

I do ABCDEF mostly

Makes sense, have a nice day.

I do ABCDE mostly...my username Sunset_

The most interesting problems at the moment. I don't care if those problems are not new and have been used in some other contests. I still love classical problems with algorithms and data structures much more than ad-hocs/observations.

I think question A is to determine whether the sum of the first two digits of a three-digit number modulo ten is equal to the last digit.

How do you know it?

Yes,how do you know about it???

But it's wrong...

Thank you

Can anyone explain how the flow of 2nd question is going ?

I feel like this contest was harder than usual

When will the rating come out?

Getting RE for C. What's the correct approach towards solving the problem?

Contest is still going on, please do not ask questions about the contest now.

Nvm I gotit

Problem D is too complex for ABC, I think. I considered a DSU solution and I'm not even able to implement it.

I disagree, it is just a simple brute force.

I implemented a Segment Tree solution in about 30 minutes (creating a segment tree for every row and every column, and then find the first/last occurence of the number "1" in a specific range)

I thought of DSU/Path compression and implemented it in around 25 minutes.

I think problem E was much harder than usual.

I did the same brute force in problem A but it did not work, my rating went down to 69.

so you did F ?

I have implemented a DSU solution too but it is giving WA ,can you help me

https://atcoder.jp/contests/abc370/submissions/57561766

can u explain the DSU approach ?

Just Path compression along 4 directions and keeping an visited array to check if the cell has a wall or not.

codeThere is a simple solution that doesn't require DSU.

SpoilerStore a set of cells for each row and each column. Lets call them $$$row_i$$$ for the $$$i$$$-th row and $$$col_j$$$ for the $$$j$$$-th column.

Then for a query $$$(r, c)$$$, we just find:

The largest value $$$\leq c$$$ and the smallest value $$$\geq c$$$ in $$$row_r$$$ using binary search (lower_bound / upper_bound trivially works if Set in your language implements it).

The largest value $$$\leq r$$$ and the smallest value $$$\geq r$$$ in $$$col_c$$$ similarly.

Then erase the corresponding cells from both sets.

Code

i did very similar to this.

I followed the same approach!

Kinda bold of you to assume everyone uses C++

same idea using python SortedList then binary search time limits.

i wrote at first brute force then optimized using vectors of sets for rows and columns and do binary search upon them.

its just binary search ._.

i did a simple binary search solution with sets, it wasnt that hard

Pain~~What is the expected way to find the cuts in F? I'm pretty sure my solution of calculating the min distance for $$$k$$$ segments starting from each point with binary lifting is overkill and not the intended.~~Wow, apparently binary lifting is the intended solution based on the official editorial.

if possible, can you share your code, just curious to see and debug where it failed. my approach is just the same as yours.

For Question D, can any one tell me why my code is failing on 2nd example testcase,

i don't know what is the issue but my code is working fine on vscode and when i run it on atcoder compiler then it is giving me runtime error. please help me to solving my problem. code link

Any hints on how to solve problem E?

You can solve it naively in $$$O(n^2)$$$ with DP, try to kick out the second loop.

My submission: https://atcoder.jp/contests/abc370/submissions/57538962

You can do in O(n) as well using prefix sums and map

My submission : Link

because you've used map, so the correct time complexity should be O(nlogn)

Bro,can you plz explain your code? I mean your thought process!

Let $$$dp_i$$$ represent the number of ways to partition the first i elements of the array into continuous subsegments such that none have sum $$$K$$$. For the transition you can extend from any index before $$$i$$$ such if $$$p_i - p_j != K$$$. In other words the sum of all $$$dp$$$ values before $$$i$$$ minus the sum of $$$dp$$$ values where the prefix sum equals $$$p_i - K$$$ which you can maintain with std:map.

hard enough in spite of starting at 20 minutes. My submission

PSA: For the editorial of problem G it mentions Lucy DP, DO NOT SEARCH IT UP

yeah same, i also google searched, and it gave me inappropriate results. Any resources for this Lucy Dp to learn?

Checking the original editorial in japanese shows what they actually meant by Lucy DP. The term is coined from a comment by user Lucy_Hedgehog in the thread for Project Euler: Problem 10, which simply asks you to find the sum of all prime numbers below $$$2\cdot 10^6$$$. Lucy_Hedgehog shows a solution using dynamic programming instead of using the sieve of Eratosthenes. It can be read here. (Only visible if you have solved the problem)

the ABC problem is easy for me

A question: when doing F, I set the lower bound to do binary search to 0, and that results in WA*1 on

`testcase55.txt`

. When I set it to 1, it passed. That's strange to me: not check(1) is obvious impossible, or is it?I think there might be a subtle mistake somewhere else in your code which is causing this change to somehow affect the answer.

My code which uses a lower bound of 1 (with $$$l \lt r$$$ as the break condition, so printing $$$0$$$ is impossible) gets AC on

`testcase55.txt`

.Gave my first contest at Atcoder any idea when do editorials come out, i found the problems to be great but had little issue understanding prob B,could only solve till C sadly.

Well, I think it would be easier to talk about it if I post out my code for checking:

The logic is a bit different from others, so I wonder if there's a legal piece of input can make a difference.

Problem E, have the difficult statment, the authors should have included the full explanation of at least a single test. If any body have understood the problem statement, please describe it. Thanks in Advance!

For each $$$M (1\leq M\leq N)$$$, partition the array into $$$M$$$ non-empty subarrays.

Example: If $$$A = [1, 2, 3, 4]$$$ and you choose $$$M=3$$$, you can partition the array in 3 ways: $$$([1,2], [3], [4]), ([1], [2, 3], [4]), ([1], [2], [3, 4])$$$. If you choose $$$M=1$$$, you can partition the array into only 1 way: $$$([1, 2, 3, 4])$$$.

Out of all of these partitions of the array, how many partitions exist such that it does not have a subarray with sum $$$K$$$?

Let me know if you have further queries!

Can u explain how to solve E? I don’t get the Editorial solution!

Replied to your comment below.

Can anyone explain which concept used in problem D?? i got TLE in it.

Binary search and sets

I'm stuck in ABC problem.

I dont understand the official editorial. Can anyone explain how to solve E?

Let's define a few things.

A "good subarray" is a subarray with the sum of elements not equal to $$$K$$$. A "bad subarray" is a subarray with the sum of elements equal to $$$K$$$.

$$$dp(i)$$$ is the answer for the prefix of length $$$i$$$ (ending at $$$i$$$), i.e. $$$A[1...i]$$$. The final answer is $$$dp(N)$$$.

$$$pf(i)$$$ is the prefix sum of $$$i$$$, i.e. the sum of the elements $$$A[1...i]$$$.

We go from left to right and calculate the answer.

How do you calculate $$$dp(i)$$$ if you know $$$dp(j)$$$ for all $$$j (1\leq j < i)$$$?

Imagine you want to take $$$[j...i]$$$ as the last subarray. You can take it if and only if it is "good", i.e. $$$pf(i)-pf(j-1)\neq K$$$. So, $$$dp(i)$$$ is the sum of all $$$dp(j)$$$ such that $$$pf(i)-pf(j-1)\neq K$$$. The condition can also be written as $$$pf(i)\neq K+pf(j-1)$$$.

Notice that $$$dp(i)$$$ can also be defined like this instead: $$$dp(i)$$$ is the sum of all $$$dp(j)$$$ such that $$$1\leq j < i$$$, minus the sum of $$$dp(j)$$$ such that $$$1\leq j < i$$$ and $$$pf(i) = K+pf(j-1)$$$. This is easier because you can keep a sum of all $$$dp(j)$$$ upto $$$i$$$, and also keep a track of the sum of $$$dp(j)$$$ for each $$$K+pf(j-1)$$$ using a map.

Submission: 57540996

why tot = 1 ? Is not it should be 0 ? as we start form 0 ?

It's because $$$dp(0) = 1$$$. So the total sum of $$$dp(j)$$$ we currently have is $$$1$$$. (Implementation detail)

I found B much harder to understand than all other problems.

In Question F, how is it ensured that there is no overlap of intervals which is given to each person ?and how does " Noticing that there is at least one i such that cut line i is used by a division if and only if the N pieces can be divided into K segments so that each segment has a mass of at least" hold. Link to editorial: https://atcoder.jp/contests/abc370/editorial/10900

so what is the DSU approach to solving D?:(

(Newbie here)Is it just me or is the field stacked against Python users? After the contest I tried cobbling together, for Problem D, a SortedSet equivalent in python using Segment Trees. Whilst my solution ran into TLE with low margins, I find that C++ solutions with same complexity comfortably passing the time constraints.

can anybody check my code for problem D pls? code

I don't think that my solution should be AC, since I am using binary search only partially(only for finding down located and right locted walls but for left and upper sides I just did brute force).

is it supposed to be AC using such approach?

g1: an array whose i-th element is an ordered set maintaining the column index the remaining walls in the i-th row; g1: an array whose j-th element is an ordered set maintaining the row index the remaining walls in the j-th column; amazing editorial which has 2 g1 and no g2(

When will you publish test cases for abc 370?

For problem E, i have been trying to do segment tree for optimizing dp, but it gives me wrong answer.

My code:

CodeCan anyone tell what am i doing wrong?

Can someone please explain how to quickly compute f_k(i+1) for every 1<=i<=N using doubling method.

I believe the author is referring to powers of 2 where if I have information about f_k(2) and f_k(4), i can use it to calculate f_k(6) but I don't know exactly how to do that.

Thanks.

You can search for binary lifting for better understanding.