### maroonrk's blog

By maroonrk, history, 5 weeks ago,

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!

• +61

 » 5 weeks ago, # |   +72 why put B in contest, nice ACD problems though
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -35 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.
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   +27 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.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +2 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.
•  » » » » » 5 weeks ago, # ^ |   +26 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.
•  » » » » » » 5 weeks ago, # ^ |   +14 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.
•  » » » » » » 5 weeks ago, # ^ |   0 +1
•  » » » » » 5 weeks ago, # ^ |   0 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
 » 5 weeks ago, # | ← Rev. 2 →   +11 Good and interesting problems, thanks for the good round!
 » 5 weeks ago, # |   +23 After more than one hour dealing with mathematics, I finally get B accepted. Somehow I thought that I was attending a mathematics exam :D
 » 5 weeks ago, # |   +8 Thank you for the round, interesting problems as always!
 » 5 weeks ago, # |   0 What's wrong with this code please help me ATCODER ARC 178 B !!!! #include using namespace std; #include 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; } 
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Still getting WA. Please Help #include using namespace std; #include 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> 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; } 
 » 5 weeks ago, # | ← Rev. 2 →   0 Good E but can't figure out the bug until contest end :(:(:(upd: well i forgot a step for the solution (divide-conquer convolution)
 » 5 weeks ago, # |   0 Can anyone explain problem c please
 » 5 weeks ago, # | ← Rev. 2 →   0 For the problem B, can anyone figure out how the inclusion-exclusion principle is used to get that expression?
 » 5 weeks ago, # |   0 Problem C is very cool.
 » 5 weeks ago, # | ← Rev. 4 →   0 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:
•  » » 5 weeks ago, # ^ |   0 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  » 4 weeks ago, # | 0 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.