### maroonrk's blog

By maroonrk, history, 3 weeks ago,

We will hold AtCoder Regular Contest 148.

The point values will be 300-500-500-700-800-1000.

We are looking forward to your participation!

• +76

 » 3 weeks ago, # |   0 It seems that C is easier than last one. I'll try to solve more problems. rating++
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +6 I was able to solve A,B in contest not able to solve C. I saw the editorial but didnt got it properly,like this one "These can be shown by naive arguments, but they can also be smartly explained by linear algebra on mod 2."Can you please explain your approach.Thanks for helping in advance
•  » » » 3 weeks ago, # ^ |   0
 » 3 weeks ago, # |   +3 Hope cross 1000 and A~C!Although I usually get AB or only A.
•  » » 3 weeks ago, # ^ |   0 congrats!
 » 3 weeks ago, # |   +7 Hope the contest is great!!!
 » 3 weeks ago, # |   0 In the front of the support!
 » 3 weeks ago, # |   +6 rp++！
 » 3 weeks ago, # |   +1 Easy ABC! I can get higher rating. Thx problem provider.
 » 3 weeks ago, # |   +14 In fact,I think B is easier than A...(Maybe I'm strange.
•  » » 3 weeks ago, # ^ |   0 l agree,but I got stuck by some dots.I am a novice
•  » » 3 weeks ago, # ^ |   0 I solved B, but not able to solve A.
•  » » » 3 weeks ago, # ^ |   0 I solved A,C but wasnt able to solve B
•  » » 3 weeks ago, # ^ |   0 same, maybe I'm just not good at math XD
 » 3 weeks ago, # |   +39 Atcoder modulo contest
•  » » 3 weeks ago, # ^ |   0 agree
 » 3 weeks ago, # |   0 D is a good problem！
 » 3 weeks ago, # |   0 i didn't solve C,how weak am i!
•  » » 3 weeks ago, # ^ |   0 agree with that. i can't cyan.
 » 3 weeks ago, # |   0 In A, why is my submission giving WA: https://atcoder.jp/contests/arc148/submissions/34801963I am checking all the prime factors of a[1]-a[0] to be the possible candidates for M. And I have also handle all equal case
•  » » 3 weeks ago, # ^ |   0 4 5 5 15 20 
•  » » 3 weeks ago, # ^ |   0 why dont you try to get gcd of all adjacent number instead. Since a[i] mod x = a[i+1] mod x then (a[i+1]-a[i]) mod x = 0
 » 3 weeks ago, # |   0 during contest: hmmmmm F should be either montgomery reduction or barrett reduction but idk how to implement either......after reading the editorial: I KNEW IT
 » 3 weeks ago, # |   0 Like, D can be solved without bipartite graphs. Just record the frequency of all numbers and then do some case processing.
 » 3 weeks ago, # |   0 Guys, how to stop writing artificially complicated solutions? Almost every time I try to solve a problem, a lot of hard solutions come to my head. How to write simple solutions, how to come up with such ideas? I will be glad to all your advice!P.S.: Look at my ARC148 problem A solution to understand my "skill" of complicating solutions: https://atcoder.jp/contests/arc148/submissions/34792833
•  » » 3 weeks ago, # ^ |   0 Count your blessings. A pass is good
 » 3 weeks ago, # |   0 Where is E and F's editorial?
 » 3 weeks ago, # |   +8 Could you check this solution to problem E or give a hack to it:https://atcoder.jp/contests/arc148/submissions/34801743Thanks very much!
 » 3 weeks ago, # |   +3 Can problem B be solved in O(N) using idea of KMP or some other algo?
•  » » 3 weeks ago, # ^ |   +3 I tried to find the substring to reverse by searching the lex max postfix (of the substring starting at the first 'p') using suffix_array(). That would be O(n log n)But for some reason that did not worked.
 » 3 weeks ago, # |   +45 Are the tests for problem D a little bit weak?https://atcoder.jp/contests/arc148/submissions/34790673 will fail on 2 16 0 1 2 3
 » 3 weeks ago, # |   0 Anyone please explain Problem C's approach. Thanks in Advance
•  » » 3 weeks ago, # ^ |   0 Mark all the vertexes from query. Then iterate over them. Add to ans amount of descendants of current vertexes because they should be picked if they are not marked. And 1 to ans if parent is not marked else substract 1.
 » 3 weeks ago, # | ← Rev. 2 →   0 Can anyone explain D? Can't understand from editorial.
 » 3 weeks ago, # | ← Rev. 2 →   0 This submission for C has a complexity of $O(N^2)$ yet passed. It can be hacked by : Input#include signed main(void) { printf("200000 1\n"); for(int i=2;i<=200000;i++) printf("%d ",i-1); printf("\n"); printf("200000 "); for(int i=1;i<=200000;i++) printf("%d ",i); return 0; }  Output1
 » 3 weeks ago, # | ← Rev. 2 →   +12 Thanks for participating, hope you enjoyed the problems!After the contest, we found a more intuitive solution to the problem F from the participants' submissions. Briefly, we can compute ab / 1000000007 by using 996491781/998244353^2 as an approximation to 1/1000000007. For more details, see this editorial(In Japanese).
•  » » 3 weeks ago, # ^ |   +10 So I was right about both montgomery reduction and barrett reduction? Darn, I should have tried implementing it...