atcoder_official's blog

AtCoder Regular Contest 191 (Div. 2) Announcement
By atcoder_official, history, 15 months 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

Comments Comments (27)
| Write comment?
»
15 months ago, hide # |
← 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 \gt = 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}$$$

→ Reply
»
15 months ago, hide # |
 
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?

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

solved D 9 minutes after end....

→ Reply
»
15 months ago, hide # |
 
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.

→ Reply
»
15 months ago, hide # |
← 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!

→ Reply
  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    hack:

    Spoiler
    → Reply
    • »
      »
      »
      15 months ago, hide # ^ |
      ← 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

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

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

→ Reply
»
15 months ago, hide # |
 
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

→ Reply
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My screencast (in Rust)

→ Reply
»
15 months ago, hide # |
 
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.

→ Reply
»
15 months ago, hide # |
 
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).

→ Reply
  • »
    »
    15 months ago, hide # ^ |
     
    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.

    → Reply
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply