maroonrk's blog

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

We will hold AtCoder Regular Contest 158.

The point values will be 300-500-500-800-800-900.

We are looking forward to your participation!

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

Comments Comments (30)
| Write comment?
»
2 years ago, # |
  Vote: I like it +41 Vote: I do not like it
Meme
→ Reply
»
2 years ago, # |
  Vote: I like it +56 Vote: I do not like it

C++20 support when

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

C++20 support when

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

qpzc

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

Note to self: brute force for n<=5

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

    That was actually not a bad note, considering it was before the round even started

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

E seems to be an easy version of https://qoj.ac/problem/888

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

Unfortunately a variant of problem E already appeared on HackerRank.

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

    ohno,but it seems that the quality of the other problems is high

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

D is a nice troll problem

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

    How did you solve it? I figured out pretty quickly that $$$y=ax, z=bx$$$ has a good chance of giving a solvable linear equation for $$$x$$$ and tried $$$a=2$$$ and sequentially $$$b=3,4,\ldots$$$. Seems it always works fast enough even if I don't have hard proof.

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

      My solution is identical to the editorial.

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

I could have solved E if I've not forgotten sorting the array before binary search.

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

    Stop learning useless algorithms, learn how to use binary search.

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

      what's the essential difference between hard problems(rated maybe 2000) and easy ones(maybe 1000). Is it the depth upto which you have to think? I am facing a dilemma here.

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

        Well I think it that the diffirence between easy problems and the hard problems is that in hard problems the solution is more complex and need to learn some tricks to solve it.

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

          so when we train our brain to be able to think upto a certain complexity, we can easily solve those problems.. right? So this is how to improve..? this my alt account :)

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

            You know that problems usually have two types: classical and adhoc. Classical need more practice and adhoc need more smarts. But if we practice really a lot, then the adhoc problems can be classical, too.

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

            In a word, the more you practice, the better you will be.

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

              But i think it's hard to jump ratings while we practice. I am astonished at my improvement but I can't imagine myself solving 1900 rated problems

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

            And also, without practicing, classical can also to be adhoc, too.

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

Here is another approach for D from lijunyi.

Let $$$y=kx,z=k^2x$$$, we get：

$$$ (k^2+k+1)(k^{2n}+k^n+1)(k^{4n}+k^{2n}+1)x^{3n+1}\equiv (k^{6n}+k^{3n}+1)x^{3n}\bmod {p} $$$

If $$$k^2+k+1\not=0$$$, $$$k^{2n}+k^n+1\not=0$$$, $$$k^{4n}+k^{2n}+1\not=0$$$, $$$k^{6n}+k^{3n}+1\not=0$$$, we can get $$$x$$$, so the problem is solved.

Let us randomize $$$k$$$ until we get $$$x$$$.

But the approach can't pass when $$$p = 7$$$ or $$$19$$$, you can use simple $$$O(p^3)$$$ brute solutions solve them.

I can't prove that, but it passed all cases.

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

after solutions of my own and from editorial I still don't get why B is not 200 pts but 500

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

Here's my solution of D without randomization: https://www.luogu.com.cn/blog/Leasier/solution-ARC158D (in Chinese).

→ Reply