We will hold AtCoder Beginner Contest 212.

- Contest URL: https://atcoder.jp/contests/abc212
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210731T2100&p1=248
- Duration: 100 minutes
**Number of Tasks: 8**- Writer: kyopro_friends, math957963, Nyaan, penguinman, sugarrr
- Tester: blackyuki, Kodaman, leaf1415
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

Why downvote this blog? It will be a nice contest!

I think the reason being is:

5:30 — 7:10 PM IST: AtCoder Beginner Contest 212

6:00 — 8:30 PM IST: ICPC Amritapuri 2020 Mock Round (For Indians)

6:00 — 9:00 PM IST: July 2021 CodeChef Lunchtime (With Extra Prizes for Indians)

Collision at the peak :)

Simple choice for me.Because I love AtCoder more than any problem solving website

For Indians, the simple choice would be ICPC mock since ICPC >>>> any problem solving website :)

yes i took ICPC option and now regret it ;-;

Clash with

CodeChef Lunchtime!No Codechef Lunchtime is clashing with ABC not the other way around

How to solve E?

just do the following K times: suppose dp[i] is the number of paths that end at i, initially only dp[1] = 1.

For every day, all vertices can go to i except those that are broken(and i, of course). So you can just do $$$nextdp[i] = \sum dp[i] - \sum _{j \in adj[i]} dp[j] - dp[i]$$$ , then just swap nextdp and dp.

I thought it would be TLE . Is not TLE only because size of all adj[i] won't be 5000 ?

yes

I used Fast Walsh for H. Is it needed?

tourist is too fast.

Well this was the only choice he has! Since he has to top the Codechef Lunchtime also and He manage to get 2 min break in between.

E was a great problem, thank you for teaching me dp on trees ( atleast a part of it ).

Can anyone tell me the reason for downvote? Was it not "dp on trees" or is something else the reason for downvote?

I doubt it has a flavor of "DP on tree," but still I don't see any reason on downvoting it... (Some of them may be downvoting you just because you're gray, which attitude I don't like)

Yes I realised it later.....the graph might not even be a tree so dp on trees is wrong...thank you.

I feel like implementing F was way harder than G.

CodeCan someone explain why my code got tle for E

The issue with your code is that in worst case, it runs in approximately $$$O(n^2k)$$$ because there could be maximum $$${n(n-1)/2} - m$$$ valid edges, so for each iteration of $$$i$$$, the inner loop runs in $$$O(n^2)$$$, hence the TLE.

Thank You for the wonderful problemset. The number of tasks was a little too much considering only 100 mins to solve them.

As a writer of ABC(sadly this time I'm not), I'm curious about how do participants feel with the new format.

i wish there was infinity of such genuine,geniosity,pure beauty,attractive,elegant,gorgeous,inspiring,exciting... problems :) thank you .

So you are saying this was not a one time thing ?

Anyways, if the 8 problem ABC is going to be adapted for further ABC too. I wish these 2 points to be implemented.

Is this going to be the new standard format? If so, sounds fun!

Hii, I tried to solve D via method 1, and then method 2, I failed to see why first one didn't work, could u help me out please.

Try the following trivial testcase with your incorrect code and you should easily see what's wrong with it, the correct output is

`2 11`

:Testcasex^n≡y(mod P) ⇔r^an≡r^b(mod P) ⇔an≡b(mod P−1) How is the second step to the third step transformed? Who can explain? Thank you very much

this problem is G

Because for every i(1<=i<=P-1),r^i is distinct ,so we can know for every r^i there is exactly one such i.