We will hold Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）.

- Contest URL: https://atcoder.jp/contests/abc348
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240406T2100&p1=248
- Duration: 100 minutes
- Writer: MtSaka, Aus21
- Tester: Nyaan, math957963
- Rated range: ~ 1999
- The point values: 100-200-250-425-475-550-650

We are looking forward to your participation!

Hope can solve problem F this time.

Got it! Solved F and ranked 296!^^

Hope can solve problem F or G this time.

GL&HF.

Good luck with the contest.

GLHF

Hope can solve problem E.rating ++!

Hoping to solve till question D in this contest!!!

felicitously

GL&HFHF

My heart has cooled down

Guys my code is giving correct output for D sample testcase. But after submission it says sample output are wrong. How even it is possible? I am use "Yes" & "No" only as output. my submission:https://atcoder.jp/contests/abc348/submissions/52108589

what's the problem : link

did your sample test case pass in local? Same problem with me. My sample testcase pass in local but failing on submission

i was getting TLE but if i marked some cells as visited ,i would get different results

but why are you getting 1 wa on sample input. Are these sample input different from problem's sample input.

i don't know either

Forcing use of

`__int128`

? Really?Any hint for Problem F? I'm guessing DP or something to do with sets but have not really come up with a solution for it.

It's a dogshit problem. Just write bruteforce with pragmas (that O3 optimization) and it will magically work.

Idk if there's a 'real' smart solution, but this is intended as far as I can see from evima's editorial lmao.

I just saw the video too, and it seems that optimisation is indeed what was expected. Well, I'd say it's still a new trick to learn (for me anyway).

You can also solve the problem using bitsets which are way faster than the video's solution.

Can you give the code?

Code

How to solve D?

I did Bfs

It's just a trivial bfs where you update the maximum remaining steps you can take from point (x,y). It works in O(H*W*N) because you'll update each point (x,y) at most N times.

why does DFS fail ?

It can be done with dfs also see this submission submission D

May you explain a little bit about your approach ?

Can you please help? I solved D using DFS but I got TLE. How can I solve the problem?

Please say how we are sure that we can update atmost N times? Please explain your solution. It would be a great help

I got a simple solution using priority queue, my ideia is use the hightest energy first and reset visited checking ttable every time use a medicine. https://atcoder.jp/contests/abc348/submissions/52162753

can somebody provide me dp code for problem D or any other approach

You can check my video editorials for D and E

You can solve it by BFS. This is my code.

Maybe you can reference my code, $$$f_{i, j}$$$ means maximum from point $$$S$$$ to $$$(i, j)$$$，finally we can check if the point $$$f_{T} \ge 0$$$ and we can see the answer.

code

Not a good problem F.

Agree. I even thought half an hour. qwq

How can did C?

use map.look it. https://atcoder.jp/contests/abc348/submissions/52071264

It seems intended solution for F has O(NNM) time complexity. Don't like it.

Btw, G has appeared before ucup season 2 round 3 problem L (partially free meal). Not complaining because such rounds are meant to be educational so problems that have appeared before are fine

Thanks for linked my blog in the (japanese) editorial though :flushed:

Can someone take a look at it for me? I wonder for a long time what went wrong.Thank you https://atcoder.jp/contests/abc348/submissions/52098958

set ANS to 2*1e18, it works for me.

You're right, thank you!

E is almost same as 1092F - Tree with Maximum Cost

My submission for D pls help me debug problem D

Just do the Brute Force way. Time complexity will be around O(NWH).

A-E Screencast (no audio/commentary this time)

Please give me a hint on the problem G

How to solve $$$\text{problem G}$$$, I saw many submissions using $$$\text{max-plus convolution}$$$ and some using $$$\text{segtree + divide and conquer}$$$. I am unable to understand both of them pls help :(

Sort the items in order of increasing $$$b_i$$$. For two different values of $$$k$$$, say $$$x$$$ and $$$y$$$, let in the optimal choice of elements, the max values of $$$b_i$$$ are $$$b_x$$$ and $$$b_y$$$ respectively. We can prove that if $$$x < y$$$ then $$$b_x \leq b_y$$$.

Also, if you fix some $$$b_i$$$, then the optimal answer for some $$$k$$$ is just the sum of maximum $$$k$$$ $$$a_i$$$$$$s$$$ in the prefix ending at $$$i$$$ minus $$$b_i$$$. So, for a fixed $$$b_i$$$ and $$$k$$$, you can evaluate the answer in $$$O(logn)$$$ using some data structure that gives the sum of $$$k$$$ maximum elements in a range.

To evaluate for each $$$k$$$, you can use the fact that the optimal $$$b_i$$$ values are monotonically non-decreasing. It is a common idea to use Divide and Conquer. Refer to this article for more info on this idea.

english editorial?

https://atcoder.jp/contests/abc348/submissions/52385052

why I am getting wrong answer in D?

update dropbox plz