aniervs's blog

About AtCoder Contests Discussion

By aniervs, history, 3 years ago, In English

Hello. Recently, I started participating on AtCoder contests, and in many cases, I don't see announcements on codeforces, or any posts for discussing the problems. I remember that before, it was very frequent to see at least one AtCoder Contest-related post among the recent actions.

Is there a reason behind it?

Also, maybe we can use this post to discuss about the last ABC.

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

Comments Comments (14)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I felt today's contest was a bit more difficult than usual . Also thought problem D was harder than problem E.

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

I got a only WA on TC 7 in E . Can someone tell me what's wrong with my solution Or what TC 7 is https://atcoder.jp/contests/abc224/submissions/26775221

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

    Even I got WA in just test case 7 :///

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

      If u r going to next smallest greater element in row and column then do remember there can be many vertices to got to.I did that mistake , though till now haven't tried resubmitting.

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

I think E has a similar idea as https://infoarena.ro/problema/zoro. Nice problem!

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

    For me, E was super standard. I've seen similar stuff at old USACO.

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

How did you (people) solve F?

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

    I did the same as the editorial says. Look at the contribution to the answer of each $$$a_i$$$.

    If we consider indexing from $$$1$$$, then each $$$a_i$$$ (for $$$i\in[1,n]$$$) contributes to the answer in $$$a_i\cdot 2^{i-1}\cdot \left(10^{n-i} + \displaystyle\sum_{j=0}^{n-i-1}2^{n-i-j-1}\cdot 10^j\right) = \frac{a_i}{2}\cdot \left(10^{n-i} + \displaystyle\sum_{j=0}^{n-i-1}2^{n-j-1}\cdot 10^j\right)$$$. Thus, we can compute prefix sums ($$$P_j = P_{j-1} + 2^{n-j-1}\cdot 10^j$$$), and then, our answer is $$$\displaystyle\sum_{i=1}^n\frac{a_i}{2}\cdot(10^{n-i} + P_{n-i-1})$$$.

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

For me, i think problem F is much easier than D and E. I stuck on D for 40 minutes , abandoned my code, and solved F in 15 minutes.

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

Can anyone tell what observations you made to solve problem D ( 8 Puzzle on Graph ) .I am not able to think clearly and make any useful observations :( .

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

    So, we have only 9 vertexes, which is very small, due to that there are 9! ways to distribute pieces (because there are 9 ways to choose a free vertex and 8! ways to distribute others => 9 * 8! = 9!). We can just run bfs from out initial state, and for each distribution we find free vertex and iterate over all edges from it, if we didn't get to the new state earlier we update distance and add new state to the queue. Finally we print distance if we can achieve final state or -1 if we can't.

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

    The goal state is a vector of {1,2,3,4,5,6,7,8,-1} where -1 represents an empty space. For sample 1, the initial state is a vector of {-1,3,1,4,5,6,7,8,2}. Use BFS to do state transition to see if the goal state can be reached or not.

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

I tried F in another way than the editorial suggests. It did not work, but I still do not understand why. That was my strategy:

Maintain the answer for a prefix of S, also the sum of all possible last terms for the formulars that can be created of S. Also maintain the count of possible prefixes.

We start with 

cnt[0]=1
post[0]=s[0]-'0';
ans=post[0];

Then iterate S for all subsequent positions, and calc the next ans. Let d be some digit s[i]. That is:

We can add the next digit as a new term to all previous formulars. Also we can add the next digit as the last digit of the last term of the previous prefix. So

ans=ans+cnt[i-1]*d + post[i-1]*10+cnt[i-1]*d

Then calculate the next cnt[], since there are the both above cases, cnt[i]=cnt[i-1]*2

Finally, calculate the current sum of all last terms, that is (again) adding the next digit as last digit of existing term, or adding it as a new last term:

post[i]=post[i-1]*10+cnt[i-1]*d + cnt[i-1]*d

So, after iterating the string ans should contain the correct answer, see submission. But it does not, why?

edit: formulars

→ Reply