maroonrk's blog

AtCoder Regular Contest 178 Announcement
By maroonrk, history, 7 months ago, In English

We will hold AtCoder Regular Contest 178.

The point values will be 400-600-600-700-1000-1000.

We are looking forward to your participation!

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

»
7 months ago, # |
  Vote: I like it +72 Vote: I do not like it

why put B in contest, nice ACD problems though

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it -35 Vote: I do not like it

    I completely agree with this statement. In my understanding math problem is ok for programming contest if it has at least something to do with programming. Problem B can be equally solved on a paper.

    UPD: Wrong statement removed. I thought post author is contest author as well.

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

      Its not about it being too mathematical. That is perfectly fine. It is not about it being purely solvable on paper. That is also fine. All good problems are purely solvable on paper (by solvable on paper i mean write algorithm and verify correctness, only bad problems need you to experiment with the computer or non provable complexities)

      It is about it being very obvious but yet a lot of effort to actually find the formulas, that too for so many cases.

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

        By being solvable on a paper I mean the following: if you remove online judge and ask participants to submit their solutions as formulas with a little bit of text on a piece of paper, there would be no major difference. All you need to check is if the formulas are correct and all the required cases are considered. I honestly don't understand what problems of this type do in programming contests.

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +26 Vote: I do not like it

          I never understood such comments "I honestly don't understand what problems of this type do in programming contests",

          You are writing contest where you solve algorithmic/math puzzle problems, programming is side dish.

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

            I follow a different philosophy. But yes, I have noticed that lately competitive programming became less about programming and more about math, which is unfortunate for people like me.

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

            +1

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

          The only.difference is that there is a judge which tells us our approach is correct true. What is the issue with that? MO proofwriting cant scale with number of contestants hence we adapt this

          → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Good and interesting problems, thanks for the good round!

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

After more than one hour dealing with mathematics, I finally get B accepted. Somehow I thought that I was attending a mathematics exam :D

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

Thank you for the round, interesting problems as always!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with this code please help me ATCODER ARC 178 B !!!! 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using mint = atcoder::modint998244353;
mint ten = 10;

#define ll long long

void solve(){
    
    int a, b, c;
    cin >> a >> b >> c;

    if(a>b) swap(a,b);

    if(c!=b+1 && c!=b) {
      cout << 0 << endl;
      return;
    }

    mint ans, whole;


    // case 1: if b == c
    if(b==c){
      // subcase1: a==b
      if(a==b){
        ans = (8*ten.pow(a-1)) * (8*ten.pow(a-1) + 1)/2;
        cout << ans.val() << endl;
      }
      // subcase2: a!=b
      else {
        ans = 9*ten.pow(a-1) * (9*ten.pow(b-1) - (11*ten.pow(a-1) -1)/2 );
        cout << ans.val() << endl;
      }
    }
    // case 2: if b+1=c
    else {
        
      if(a==b) {
        
       whole = 81*ten.pow(a+b-2);
       ans = (8*ten.pow(a-1)) * (8*ten.pow(a-1) + 1)/2;
       cout << whole.val() - ans.val()   << endl;

      }
      else {
        whole = 81*ten.pow(a+b-2);
        ans = 9*ten.pow(a-1) * (9*ten.pow(b-1) - (11*ten.pow(a-1) -1)/2);
        cout << whole.val() - ans.val()   << endl;
      }
    }

       fflush(stdout);
       cout << flush;
    }


int main() {
    int t;
    cin >> t;
    for (int T = 1; T <= t; ++T)
    {
      
       solve();


    }

       return 0;
}
→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are dividing without modulo, for example 1/2 is not 0 modulo 998244353, but you will get 0 as the result will be rounded down. Instead of dividing by int 2, using atcoder modint you must multiple by two.inv() with mint two = 2.

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

      Still getting WA. Please Help

      #include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using mint = atcoder::modint998244353;
mint ten = 10;
mint two = 2;

#define ll long long

/*

10^(a1-1)<=x1<10^a1
10^(a2-1)<=x2<10^a2
10^(a3-1)<=x3<10^a3
a2=a3:
a1=a2: sum(10^a2-10^(a2-1)-x1 for 10^(a1-1)<=x1<10^(a1))   here a1=a2
a1<a2: sum(10^a2-10^(a2-1)-x1 for 10^(a1-1)<=x1<10^a1)
a2<a3:
If A3=A2+1 We can find the count when A3=A2 and subtract that value from 81×10^(A1+A2−2).
ans=(10^a1-10^(a1-1))*(10^a2-10^(a2-1))-solve(a1,a2,a3-1)

*/



void solve(){
    
    int a, b, c;
    cin >> a >> b >> c;

    if(a>b) swap(a,b);

    if(c!=b+1 && c!=b) {
      cout << 0 << endl;
      return;
    }

    mint ans, whole;


    // case 1: if b == c
    if(b==c){
      // subcase1: a==b
      if(a==b){
        ans = (mint(8)*ten.pow(a-1)) * (mint(8)*ten.pow(a-1) + 1)*two.inv();
        cout << ans.val() << endl;
      }
      // subcase2: a!=b
      else {
        ans = mint(9)*ten.pow(a-1) * (mint(9)*ten.pow(b-1) - (mint(11)*ten.pow(a-1) -1)*two.inv());
        cout << ans.val() << endl;
      }
    }
    // case 2: if b+1=c
    else {
        
      if(a==b) {
        
       whole = mint(81)*ten.pow(a+b-2);
       ans = (mint(8)*ten.pow(a-1)) * (mint(8)*ten.pow(a-1) + 1)*two.inv();
       cout << whole.val() - ans.val()   << endl;

      }
      else {
        whole = mint(81)*ten.pow(a+b-2);
        ans = mint(9)*ten.pow(a-1) * (mint(9)*ten.pow(b-1) - (mint(11)*ten.pow(a-1) -1)*two.inv());
        cout << whole.val() - ans.val()   << endl;
      }
    }

       fflush(stdout);
       cout << flush;
    }


int main() {
    int t;
    cin >> t;
    for (int T = 1; T <= t; ++T)
    {
      
       solve();

    }

       return 0;
}
      → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Good E but can't figure out the bug until contest end :(:(:(

upd: well i forgot a step for the solution (divide-conquer convolution)

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem c please

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For the problem B, can anyone figure out how the inclusion-exclusion principle is used to get that expression?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is very cool.

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

UPD: Got it.

Can anyone explain this part of the editorial of problem C?

I don't understand the last line. I tried to derive the 3rd equation from the 2nd but i only could derive up to this:

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

    Yours are also correct. But we want to get the equation that is related to the difference between $$$B_k$$$ and $$$B_{k+1}$$$.

    $$$l\le r,B_{r}-B_{l}=(B_{l+1}-B_{l})+(B_{l+2}-B_{l+1})+\cdots+(B_{r}-B_{r-1})$$$. We can think of it as intervals. $$$[l, r]$$$ includes $$$[l,l+1],[l+1,l+2],\cdots,[r-1,r]$$$. Now we have all intervals $$$[l, r], 1\le l<r\le n$$$ and we want to count the number of intervals that include $$$[i,i+1]$$$, which means $$$l\le i, r\ge i+1\Rightarrow i(n-i)$$$.

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The official editorial of problem E noted:

Here, if $$$f(x)$$$ is a polynomial such that $$$[x^{i}]f(x)$$$ is the answer for $$$i$$$, the contribution of $$$j$$$ to $$$f(x)$$$ is $$$A_{j}x^{b+1}(1+x)^{j-b-1}$$$. However, if there exists a $$$j$$$ such that $$$j = b$$$, the contribution of $$$j$$$ to $$$f(x)$$$ is $$$A_{j}x^{j}$$$.

Therefore, if $$$c$$$ is the smallest integer satisfying $$$L \leq 2A_{i}$$$, and $$$B_{i}$$$ is the smallest integer satisfying $$$L - A_{b} \leq A_{i}$$$, the total contribution of all $$$j$$$ to $$$f(x)$$$ can be obtained by evaluating the following polynomial:

$$$ \sum_{i=c}^{N} A_{i}x^{B_{i}+1}(1+x)^{i-B_{i}-1} $$$

Since $$$B_{i}$$$ is monotonically decreasing with respect to $$$i$$$, and $$$i - B_{i}$$$ is monotonically increasing with respect to $$$i$$$, this expression can be evaluated in $$$O(N (\log{N})^{2})$$$ using divide-and-conquer and convolution.

Can anybody gives a clearer analysis of where the $$$f(x)$$$ comes from and how the formula is deduced? Additionally, what's the function of $$$c$$$? It seems that $$$c$$$ didn't appear in the following texts. Thanks a lot.

→ Reply