We will hold AtCoder Regular Contest 191 (Div. 2).
- Contest URL: https://atcoder.jp/contests/arc191
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20250126T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 5
- Writer: sounansya
- Tester: Nyaan, maspy
- Rated range: 1200 ~ 2399
The point values will be 400-500-600-700-800.
We are looking forward to your participation!
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}$$$
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?
actually, it's
shit
solved D 9 minutes after end....
Solved D by writing a brute force and checking with my solution. Otherwise it's impossible to notice some cases.
Possible
I got ac without stress testing. This means it is not impossible. What's wrong?
Guys don't be shy give me a clue al least
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.
This is a rare complex problem where I had not had to do a stress-test
I find the "2X+4Z+4" case with a stress-test.
Based on several comments,it's my problem
https://atcoder.jp/contests/arc191/submissions/62138147
I passed 63/64. Where did this code go wrong, help me!
hack:
9 8 7 4
1 2
2 3
1 4
2 5
1 6
4 7
1 8
7 9
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
I have an impropriate analogy about today's C and D. Sorry for any insult.
Problem: Please go to the toilet.
I: Went to the toilet and did my business.
The editorial: Went to the toilet, washed hands, and went out.
Problem: Please go to the toilet.
I: No, I'd skip the problem
The editorial went to the toilet and cleaned (ate) up all I had left when I was doing my private things in problem C.
Seeing an IM talking about toliets is a funny thing. :)
Bro now we are all GM!
The first editorial of C is like apple falling on Newton's head.
And the second is like using the gravitation Newton discovered to build a big rocket.
Perhaps it has something to do with the LTE lemma? They look similar in the form.
can anyone please help my why i am getting wrong answer in A — Replace Digits here is my submission
Consider
4 2
2225
92
My screencast (in Rust)
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.
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).
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:
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.
How does one even come up with Solution 1 of problem C?