atcoder_official's blog

AtCoder Beginner Contest 364 Announcement
By atcoder_official, history, 4 months ago, In English

We will hold Japan Registry Services (JPRS) Programming Contest 2024#2 (AtCoder Beginner Contest 364).

We are looking forward to your participation!

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

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

My planned post contest discussion stream

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

Fun fact: 1115449 is a prime number!

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

ACAM in ABC362, then Steiner tree in this round?????? Will ABC365 have a poly multipoint eval as G?????????

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

    imo specific case of NP-Hard problem isn't bad. Or have this G appeared before?

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

      Yes, there is a similar (template) problem on luogu. Someone passed it in 2 min and they probably copied their code.

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

Scream if you love dynamic programming

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

It is not a good habit to present old questions in new competitions.

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

Problem G coincides with a problem from BOI 2016 (link), so it wasn't hard to copy-paste my previous code :)

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

    Last ABC, problem G was a blatant template for ACAM and now it's just a blatant copy of another problem? atcoder_official, if you can't set Gs, then don't. It's better to have a contest with 6 problems than blatantly copying another problem.

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

    In the BOI problem, you are given all $$$k$$$ important cities upfront. Additionally, the constraints on $$$n, m, k$$$ differ substantially. Of course, solving the BOI problem makes it easier to solve G, but it's not an exact copy. I think it's perfectly fine to have this level of similarity. For example, a friend pointed out that I solved 152E - Garden, a problem from 2012 with a similar solution. I could copy-paste parts of my code had I remembered that problem, but I didn't. If you still remember an old problem and realize that the current one is similar then you deserve to have an easier time solving it.

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

what is the problem with this solution for e?

https://atcoder.jp/contests/abc364/submissions/56054692

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

    when he eats the last sweet it can actually exceed x or y , sowhen updating dp you should actually check that j <= x for example not j + sweet <= x .

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

Can someone, please, tell, how can I link my cf Id to my AtCoder account?

UPD: I got the answer

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

can someone explain me why this submission to E didn't pass?

https://atcoder.jp/contests/abc364/submissions/56063726

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

my solution for E got passed but ideally it should give Runtime error can anyone tell me why

https://atcoder.jp/contests/abc364/submissions/56052731

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

Why the problem E and C were almost same, but their input style was different ?

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

    If you read through the problems you'll find that although C and E have similar themes of eating, C is greedy whereas E is DP. It's two completely different problems, and I think both were good problems.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      I think they meant the formatting of the input themselves are different. One was all A then all Bs, the other being pair of A,B. I didn't notice this during the contest and somehow passed all samples.

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

        Actually same as me, this contributes one WA for me...

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

hey why GREEDY doesnt work in E but for c it works only differ is max and min so why ? also ,

How maintaining minimum total saltiness when choosing exactly k dishes solves the problem.

Basically, how to transform from O(NXY) to O(N^2Y)

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

    I don't know if this dp technique has a name, but it's pretty well-known.

    Let's say we have a dp where $$$dp[i] = x$$$, which means that the optimal value at state $$$i$$$ is $$$x$$$. This is not solvable this way when $$$i$$$ is very large.

    If $$$i$$$ is very large and $$$x$$$ has a reasonable limit, say, $$$1\leq i\leq 10^9$$$ and $$$1\leq x\leq 10^5$$$, one way to go about it is to swap the dp state and the result. So the new dp would be $$$dp[x] = i$$$, denoting that optimal value $$$x$$$ is possible using state $$$i$$$.

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

      It’s called state shuffling. There isn’t a lot of articles explaining it though.

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

Can someone Please tell why this Solution of E is giving WA. I have thought it for hours but unable to figure it out. https://atcoder.jp/contests/abc364/submissions/56048006

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

    2 3 4 4 2 2 2

    answer is 2, but you answer is 1. because you can eat 1 after 2.

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

      Thanks a lot. Got the flaw in my approach

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

any recursive/memo (dp) solution for E

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

My F's solution is failing on 3 testcases, can someone help me understand why?

My Idea — instead of connecting l--i+n,l+1--i+n...r--i+n, connect l to i+n then connect l--l+1, l+1--l+2, l+2--l+3... I maintain minimum and maximum index a node is connecting to skip iterating from l to r, and just jump certain number of nodes.

Link to submission

→ Reply