Блог пользователя aniervs

About AtCoder Contests Discussion

Автор aniervs, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      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.

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How did you (people) solve F?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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})$$$.

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :( .

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить