atcoder_official's blog

By atcoder_official, history, 4 weeks ago, In English

We will hold AtCoder Regular Contest 191 (Div. 2).

The point values will be 400-500-600-700-800.

We are looking forward to your participation!

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

»
3 weeks ago, # |
Rev. 7   Vote: I like it +15 Vote: I do not like it

Solved problem C after 10 tries, thanks to the corner case $$$2\times p$$$ when $$$p >= 3.5 \cdot 10^8$$$

(If $$$n = 2^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3} ...$$$ then my $$$m$$$ was $$$2^{a_1+2}\cdot p_2^{a_2+1} \cdot p_3^{a_3+1} ...$$$ which was greater than $$$10^{18}$$$)

Edit: this solution is a little crazy and unproved, but seems to work. I bruteforce for that $$$m$$$ to find the first $$$a$$$ such that $$$a^{nk} \equiv 1\ (mod\ m)$$$ and $$$nk$$$ is the smallest. when $$$n = 2^{a_1}\cdot p_2^{a_2}$$$ I chose $$$m = 2^{a_1+1}\cdot p_2^{a_2+1}$$$ instead of $$$m = 2^{a_1+2}\cdot p_2^{a_2+1}$$$

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Bad C. During the contest I used Solution 2 , and it seems that it is much harder than Solution 1. Are you palying brain teasers with us?

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

solved D 9 minutes after end....

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Solved D by writing a brute force and checking with my solution. Otherwise it's impossible to notice some cases.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Possible

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I got ac without stress testing. This means it is not impossible. What's wrong?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Guys don't be shy give me a clue al least

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ignore it

          Codeforces downvotes and upvotes are very weird. You did nothing wrong.

          Its best not to try to understand or focus on whether your comment was downvoted or upvoted.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is a rare complex problem where I had not had to do a stress-test

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I find the "2X+4Z+4" case with a stress-test.

      Based on several comments,it's my problem

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/arc191/submissions/62138147

I passed 63/64. Where did this code go wrong, help me!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    hack:

    Spoiler
    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you very much!

      upd:

      At line 118, I copied line 111 and changed it to:

      y = min(x, dis3[u]);

      Actually, it should be

      y = min(y, dis3[u]);

      So, maybe I'm a clown

»
3 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

I have an impropriate analogy about today's C and D. Sorry for any insult.

C
D
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Seeing an IM talking about toliets is a funny thing. :)

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

The first editorial of C is like apple falling on Newton's head.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    And the second is like using the gravitation Newton discovered to build a big rocket.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Perhaps it has something to do with the LTE lemma? They look similar in the form.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there anyone who solves problem C using solution 1 ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I come up with such (A, M) in solution 1 in C?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please help my why i am getting wrong answer in A — Replace Digits here is my submission

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My screencast (in Rust)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

okay, I thought of solution 2 of C during the contest but did not even think about randomized search!

To be honest, I did not find D to be that bad. I solved it after the contest.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share some insights on how to solve/approach C without pulling the idea out of thin air?

I wrote some brute force and observed that $$$A$$$ was a prime and $$$M$$$ was of form $$$kN + 1$$$ seemed to work. I tried to generate 100 random primes and brute force $$$k$$$, which run okay for $$$N\le10^5$$$. But it didn't for some very big $$$N$$$ like $$$999999001$$$ (due to number overflow).

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    My thought process (for solution 1 of C), not the nicest way of solving problems but it works: Let's try to find $$$M$$$ first. We know that the multiplicative order of every number modulo $$$M$$$ must be divisible by $$$\varphi(M)$$$ (Euler's totient function). So, $$$N$$$ must divide $$$\varphi(M)$$$. How do we find such an $$$M$$$? Let's look at the formula for Euler's totient function:

    $$$ \varphi(M) = M \prod_{p \mid M} \left( 1 - \frac{1}{p} \right) $$$

    We can probably find a suitable $$$M$$$ by finding the prime factorization of $$$N$$$ and increasing the power of each prime factor by $$$1$$$, but $$$N$$$ and $$$T$$$ are too large (there still exist ways to factorize $$$N$$$ fast enough, but they're rarely seen in contests). An easier way to increase power of each prime factor of $$$N$$$ by at least $$$1$$$ would be using $$$M = N^2$$$. Does it work? Write a bruteforce to find all suitable values of $$$A$$$ for $$$M = N^2$$$ for small $$$N$$$. Observe that $$$N+1$$$ is always present.

    Not a fan of this problem in a programming contest because such ways of solving exist. Seems more suitable for a subjective math contest maybe.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How does one even come up with Solution 1 of problem C?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Atcoder I think is just basically they made for Japanese people editorials are worst and no videos are there for any type of prob of contests...