We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307).
- Contest URL: https://atcoder.jp/contests/abc307
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230624T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: kyopro_friends, math957963, evima, m_99, Nyaan
- Tester: MMNMM, leaf1415
- Rated range: ~ 1999
- The point values will be 100-200-300-400-475-550-550-600.
We are looking forward to your participation!
Hope this one's rated, sigh. (Wrote before the contest began, now I hope it isn't)
website broke
Seems like someone really doesn't like the "Tokio Marine & Nichido Fire Insurance".
Also C looks like the most unfun problem ever.
Is the website down, can't submit for a long time now!
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.
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.
no, contests should happen ;we need problems
I think they do try to make the website better. They just published a report (in Japanese) on the DDoS issue recently.
I would request the manga writers to write a manga on the attacks on atcoder
Problem C is sh*t.
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 :)
Can you please explain?
After codeTon :)
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.
Yeah:)
Actually E can be solved by solved by mathematical induction and by solving an eigenvalue equation too. For reference, See this.
Yeah, as for me nice math problem!
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
can you explain how to came up with this formula?
Problem C ruined my whole contest
Solved C in time complexity $$$O(N^3M^3\log NM)$$$ or something with branching, what the actual fuck
How ?
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)
worst problem C
how to solve E by inclusion exclusion
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
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!
Need Help On Problem D (WA) :https://atcoder.jp/contests/abc307/submissions/42926611
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".
Nice contest
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.
Okay I think I understood it correct first, time, once infected you are infected and can spread any day. But I can't figure out why my code is getting WA. I think the approach should work.
https://atcoder.jp/contests/abc307/submissions/42940997
No questions about C++
2320, did they added it?