Блог пользователя atcoder_official

Автор atcoder_official, история, 7 месяцев назад, По-английски

We will hold Toyota Programming Contest 2024#4(AtCoder Beginner Contest 348).

We are looking forward to your participation!

  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope can solve problem F this time.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope can solve problem F or G this time.

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

GL&HF.

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Good luck with the contest.

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

GLHF

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hope can solve problem E.rating ++!

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

felicitously

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

GL&HF

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

HF

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My heart has cooled down

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

what's the problem : link

»
7 месяцев назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Forcing use of __int128? Really?

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Not a good problem F.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can did C?

»
7 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

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:

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My submission for D pls help me debug problem D

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please give me a hint on the problem G

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

english editorial?

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

update dropbox plz

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I implemented DFS for D but failed to pass, is it because DFS is just a wrong approach? Can't find the reason.