atcoder_official's blog

Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348） Announcement
By atcoder_official, history, 4 weeks ago, In English

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

We are looking forward to your participation!

  • Vote: I like it
  • +38
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope can solve problem F this time.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope can solve problem F or G this time.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

GL&HF.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Good luck with the contest.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

GLHF

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope can solve problem E.rating ++!

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

felicitously

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

GL&HF

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

HF

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My heart has cooled down

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

what's the problem : link

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Forcing use of __int128? Really?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like 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.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can check my video editorials for D and E

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

Not a good problem F.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How can did C?

→ Reply
»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it +47 Vote: I do not 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:

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission for D pls help me debug problem D

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please give me a hint on the problem G

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :(

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

english editorial?

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

why I am getting wrong answer in D?

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

update dropbox plz

→ Reply