chokudai's blog

AtCoder Beginner Contest 212 Announcement
By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 212.

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

We are looking forward to your participation!

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

Comments Comments (32)
| Write comment?
»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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

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

    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 :)

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

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -21 Vote: I do not like it

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

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

Clash with CodeChef Lunchtime!

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

How to solve E?

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

    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.

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

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

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

I used Fast Walsh for H. Is it needed?

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

tourist is too fast.

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

    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.

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

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

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

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

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

      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)

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

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

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

I feel like implementing F was way harder than G.

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

Can someone explain why my code got tle for E

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

    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.

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

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

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

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

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

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

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

    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.

    1. Increase duration a bit (maybe like make it 2 hours ? )
    2. Make problem >= F, more in the reach of actual rated range participants. For me personally today, I was done till E in 25 mins and then I stared at screen for rest whole contest. But yes, I understand its my fault and F was actually not that out of reach, but still I think it was pretty hard. (That can be seen by yellow rating to F, G and orange rating to H at kenkoo)
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

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

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.

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

    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:

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

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

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

    this problem is G

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

      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.

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

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

→ Reply