maroonrk's blog

AtCoder Regular Contest 158 Announcement
By maroonrk, history, 20 months 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?
»
20 months ago, # |
  Vote: I like it +41 Vote: I do not like it
Meme
→ Reply
»
20 months ago, # |
  Vote: I like it +56 Vote: I do not like it

C++20 support when

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

C++20 support when

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

qpzc

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

    This platform is not the luogu, so you should think before write this comments.

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

Note to self: brute force for n<=5

→ Reply
  • »
    »
    20 months 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
»
20 months 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
»
20 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Unfortunately a variant of problem E already appeared on HackerRank.

→ Reply
  • »
    »
    20 months 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
»
20 months ago, # |
  Vote: I like it +36 Vote: I do not like it

D is a nice troll problem

→ Reply
  • »
    »
    20 months 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
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      My solution is identical to the editorial.

      → Reply
»
20 months 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
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      20 months 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
      • »
        »
        »
        »
        20 months 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
        • »
          »
          »
          »
          »
          20 months 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
          • »
            »
            »
            »
            »
            »
            20 months 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
          • »
            »
            »
            »
            »
            »
            20 months 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
            • »
              »
              »
              »
              »
              »
              »
              20 months 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
          • »
            »
            »
            »
            »
            »
            20 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
»
20 months 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
»
20 months 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
»
20 months 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