maroonrk's blog

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

C++20 support when

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

C++20 support when

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -46 Vote: I do not like it

qpzc

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +21 Vote: I do not like it

Note to self: brute force for n<=5

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

Unfortunately a variant of problem E already appeared on HackerRank.

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +36 Vote: I do not like it

D is a nice troll problem

→ Reply
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      My solution is identical to the editorial.

      → Reply
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
        • »
          »
          »
          »
          »
          21 month(s) 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
          • »
            »
            »
            »
            »
            »
            21 month(s) 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
          • »
            »
            »
            »
            »
            »
            21 month(s) 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
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) 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
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) 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