maroonrk's blog

AtCoder Regular Contest 148 Announcement
By maroonrk, history, 2 years ago, In English

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!

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

Comments Comments (27)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that C is easier than last one. I'll try to solve more problems. rating++

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

Hope cross 1000 and A~C!

Although I usually get AB or only A.

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

Hope the contest is great!!!

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

rp++！

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

Easy ABC! I can get higher rating. Thx problem provider.

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

In fact,I think B is easier than A...

(Maybe I'm strange.

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

    I solved B, but not able to solve A.

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

Atcoder modulo contest

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

D is a good problem！

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

i didn't solve C,how weak am i!

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

In A, why is my submission giving WA: https://atcoder.jp/contests/arc148/submissions/34801963

I 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

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

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

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

Like, D can be solved without bipartite graphs. Just record the frequency of all numbers and then do some case processing.

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

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

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

Could you check this solution to problem E or give a hack to it:

https://atcoder.jp/contests/arc148/submissions/34801743

Thanks very much!

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

Can problem B be solved in O(N) using idea of KMP or some other algo?

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

    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.

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

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

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

Anyone please explain Problem C's approach.
Thanks in Advance

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

    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.

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

Can anyone explain D? Can't understand from editorial.

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

This submission for C has a complexity of $$$O(N^2)$$$ yet passed. It can be hacked by :

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

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

→ Reply