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&HF
HF
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
I think atcoder user Syxqwq cheated in abc348. Reason: Use of a lot of strange code in https://atcoder.jp/contests/abc348/submissions/52112317 and in very many recent atcoder contests to confuse her submissions in order not to get her account banned. It is recommended that Atcoder admins ban her. atcoder_official please banned Syxqwq, her atcoder account is Syxqwq too. qwq
I implemented DFS for D but failed to pass, is it because DFS is just a wrong approach? Can't find the reason.