### 1000--7's blog

By 1000--7, history, 11 months ago,

Hello, Codeforces! 74TrAkToR and I were solving problems and have noticed one super interesting fact.

So, check this out. 801E - Vulnerable Kerbals is a very nice problem we have solved. There is an interesting solution with DP on a DAG. I won't go into detail, but in the end we had to solve this problem:

You are given an array (a) with n different numbers from 0 to m — 1. You need to create an array (b) (with same length) with (not necessary different) numbers, so if you multiply first i numbers of b and get in by modulo m, you will receive a[i]. It's guaranteed, that we can create such array.

Ok, it's easy to understand, that we must solve some equations like $a \cdot x \equiv b \pmod m$.

How to solve it? We wrote 2 similar solutions, but we had one similar mistake, but.... we got AC. I've checked jury solution and.... there is this idea toox.

Well, this solution is based on the following fact. We can get $b \pmod m$ by multiplying $a$ on some $x$ if and only if $gcd(b, m) \vdots gcd(a, m)$. Let's find x. Let $a' = gcd(a, m)$, $b' = gcd(b, m)$, then $p_a = \frac a {a'}$, $p_b = \frac b {b'}$. Easy to realize that $p_a$ and $p_b$ are coprime with m, we can get ${p_a}^{-1} = {p_a}^{\phi(m) - 1}$, so our $x = \frac {b} {a} = \frac {b'} {a'} \cdot \frac {p_b} {p_a} = \frac {b'} {a'} \cdot p_b \cdot {p_a}^{\phi(m) - 1}$. So, wasn't so hard, really? Mmmaybe, but that's not true, because $p_b$ can be not comprime with $m$. $m = 24$, $b = 16$. $b' = 8$, $p_b=2$. Holy... Idk, i can't found some information about it. It's getting AC and the author of this problem uses this formula too, I think, it's right. But why??? If we use formula $x = b \cdot {a}^{\phi(m) - 1}$, it's getting WA7. Maybe are weak tests.

I also came up with the right solution: let's solve diophantine equation $ax+my=c$. ex_gcd can help you, but we must use $(x = 0, y = c / gcd)$ at the end.

I have observed one thing: all of numbers $a$ with the same $gcd(a, m)$ have the same ${a}^{\phi(m)}$ that have partly the same $gcd$ with $m$, but all of the prime divisors (p) in maximum power (it power that $m \vdots p^x$, x — maximal), so, ${a}^{\phi(m)}$ may have other prime divisors.

Can you help us? Thank you in advance. It's really shocking, that we pass a similar mistake.

• +74

By 1000--7, history, 16 months ago, translation,

You are given two arrays: a, b

We need to calculate for each x: c[x] = max(a[j] + b[x — j]), for each 0 <= j < x

a, b are sorted

• +14

By 1000--7, history, 3 years ago,

Hi, Codeforces. As known, Codeforces is huge platform, where programmers can compete in a single rankings. Platform, where sport programmers can chat and discuss their questions. Also, Codeforces have a big testers team. Many organizators use Codeforces to hold theirs events. For example, Codeforces is hosting a significant first level Russian Olympiad "Technocup". Recently, Codeforces is a place for education Olympiad programming.

But no matter how many advantages there are on Codeforces, it has no rating team competitions. I think, many people would like to see their realization on Codeforces. Even more, a lot of local team events held on Codeforces. Sometimes Codeforces organize contests mirrors. So why not organize such competitions? I'm sure, that many problemsetters have tasks that aren't very good for classic rounds on Codeforces, but will look great on team events. You can create a particular domain. There can be not only teams created from multiple accounts on Codeforces, but also create make particular accounts for teams. All in all, I ask MikeMirzayanov and the whole Codeforces team to listen this idea. And also I suggest all Codeforces to discuss this idea and offer yours. I hope you like our idea. Thank you for your reading:)

And thanks Prokhor08 && Renatyss for development this idea.

• +65

By 1000--7, history, 3 years ago,

I was solving Codeforces Round #658 (Div. 2) and decided to watch the virtual participation of JooDdae. When I opened the "Friends Standings" tab, I saw what his solved problems moved right for 1 task in the plate (he solved ABCD).

• +26

By 1000--7, 3 years ago, translation,

Hey, Codeforces! Why did you put likes on this post?

Is that probably good news? Maybe Mike updated Codeforces somehow? Maybe it's some really funny joke about Codeforces/Programming?

NO!

The authors of this round tried very hard, came up with tasks, and because of Mike's problems all their work was almost in vain!

NO!

Mike's post, in which he said he screwed up and got a lot more likes than Monogon's post about this round!

What did you like Michael's post? Because he is Michael?

I have absolutely no blame for him. Yes, everyone makes mistakes, but for mistakes there should be dyslaiki!

Yes, MikeMirzayanov tried to fix it, but it didn't work out, and the authors suffered, and you (those who wrote the contest) lost your precious time. Are you happy about this? Did you push "I liked it" because you liked the post? Did you like the round being postponed? Did you like what you were told 10 minutes before it started? Did you come to the round for that? To lose time?

Now Mike has written another post, I'm urging him to like this post so that the authors don't feel so bad about the lost time.

I understand that maybe not everybody will like this post, but if you put dyslaic on it, please write a comment that says what is wrong with this post, maybe I am in something really wrong, and if you tell me about it, I will definitely update the post and write about it.

Thank you for understanding and sorry for my English!

• -58

By 1000--7, history, 3 years ago,

Yesterday my coach give me a hard problem "a + b".

In standard input gives two numbers a and b.

I must output sum a + b.

Please help me with this hard problem

UPD: YEE, I KNOW HOW TO SOLVE!

import time

a, b = map(int, input().split())
start = time.time()
time.sleep(a)
time.sleep(b)
print(time.time() - start)

• -96