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 ;-;

New rule of ABC : 8 Tasks 100 minutes It will take speedsolving to another level

Unusual score distribution

Spoiler8 problems in 100 minutes

do not clickSpeedcoder

It must be a nice contest!

Clash with

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

8 problems, still burned all remaining time on O(n^gajillion) approach to E.

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.

D was nice, even though I couldn't pass all test cases

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.

I am not able to understand the editorial of E. Can somebody explain it or refer to some other resource for it?

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.

You should use adjacency list instead of adjacency matrix for checking the banned ways, improving from $$$n^2$$$ to $$$n + 2*m$$$ for the inner loop when reducing the banned ways

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`

:TestcaseGot it.

Thank you. !!

x^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.

I think problem E could be solved by using kitamasa method. Anyone have AC code?