snuke's blog

AtCoder Beginner Contest 307 Announcement
By snuke, history, 11 months ago, In English

We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307).

We are looking forward to your participation!

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

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

Hope this one's rated, sigh. (Wrote before the contest began, now I hope it isn't)

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

website broke

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

Seems like someone really doesn't like the "Tokio Marine & Nichido Fire Insurance".

Also C looks like the most unfun problem ever.

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

Is the website down, can't submit for a long time now!

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +43 Vote: I do not like it

Hi, no offence, but why are you holding contests every week when you have to make it unrated because of a DDoS attack or site lag? I understand the learning from the contests. Still, after giving a rated contest, if it becomes unrated, then most of the participants do not like it; please try to improve the Atcoder website and then hold contests, hoping today's contest remains rated.

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

    Presumably they have a decent queue of ABC-level problems so they're making ABCs. They're not holding higher level contests every week. Also not sure if problemsetters and site maintainers are the same people since that requires different skills — if they aren't, you just suggest that one group goes idle and prepared low level contests stack up.

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

    no, contests should happen ;we need problems

    → Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 4   Vote: I like it +17 Vote: I do not like it

    I think they do try to make the website better. They just published a report (in Japanese) on the DDoS issue recently.

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

I would request the manga writers to write a manga on the attacks on atcoder

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

Problem C is sh*t.

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

I have another solution on E. Let dp[i] — the answer for n = i. Then dp[i] = m * ((m-1) ** (i-1)) — dp[i-1]. If someone wants to understand why — write me :)

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

    Can you please explain?

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

      After codeTon :)

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

      I think its because there are m ways to color the first vertex, m — 1 ways to colour the last n — 1 vertex. And minus the dp[i — 1] ways where the last and the first vertex's colour match.

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

    Actually E can be solved by solved by mathematical induction and by solving an eigenvalue equation too. For reference, See this.

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

      Yeah, as for me nice math problem!

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

      Also it can be solved by mathematical induction on OEIS, A092297 is $$$2^n + 2(-1)^n$$$, A226493 is $$$3^n + 3(-1)^n$$$, yeah it pretty much seems to me that the rest is $$$(m-1)^n+(m-1)(-1)^n$$$ also

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

        can you explain how to came up with this formula?

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

Problem C ruined my whole contest

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

Solved C in time complexity $$$O(N^3M^3\log NM)$$$ or something with branching, what the actual fuck

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

    How ?

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

      saved black cells as coordinates in a set, decided that we can solve the task by transposing the coordinates, so bruteforced the transposition from $$$-10$$$ to $$$10$$$ in a four-layer loop (seriously I don't even wanna find out the actual TC anymore, the task is a piece of shit)

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

worst problem C

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

how to solve E by inclusion exclusion

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

Hi.For F my algorithm was building a Dijkstra DAG and run a dp[i] = (min_day, max_span) but it gives wrong answer. Can someone help me point out the reason? Thanks!

My implementation: https://ideone.com/N6Y2xR

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

I have a curse about atcoder, that is, every time I have a good performance in atcoder contest, and this contest is unrated! And every time I do shit in a contest, this contest is rated! That is the reason why I am the master on codeforces, but cannot even get blue in atcoder.

I do shitty in this contest, have a ranking of 1300+, and it is rated again!

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

Need Help On Problem D (WA) :https://atcoder.jp/contests/abc307/submissions/42926611

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

    Your solution assumes that there is a single pair of opening and closing brackets covering all the removed substrings. This is incorrect. Consider the case: n = 9, s = (ab)c(ab)

    Your approach marks ind[0] = 0 and ind[8] = 0, and hence would remove the entire string, however the correct answer is "c".

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

Nice contest

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

For problem F, I have confusion. I think the problem is stating that someone becomes infected on the (i-1)th day, and they remain infected through day ith and can spread infection to others. But after that they are no longer infected right, and can become infected again later? But it is only asking to return the earliest day they were infected on.

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

No questions about C++2320, did they added it?

→ Reply