Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### balbit's blog

By balbit, history, 7 weeks ago, ,

Dear All,

It will be even better if there exists an obvious solution that is very hard to implement and also a clever solution (with the same time complexity) that is easier to implement.

Basically, recommend any problem that you were very confident you could solve but somehow landed 5 WA verdicts and/or left in rage.

• +89

By balbit, history, 4 months ago, ,

About halfway through the contest, this message kept appearing:

Even m2.codeforces.com isn't safe:

Note: My internet connection is not broken Did this affect everyone? Anyways, this is extremely annoying and should be fixed as soon as possible. I had to reload my pages many times before Codeforces began functioning again.

• +10

By balbit, history, 5 months ago, ,

Here is a normal implementation of Pollard's Rho algorithm.

ll c = 1;
ll g(ll x, ll n){
return (x*x+c)%n;
}

ll po(ll n){
ll x = 2, y = 2, d = 1;
while (d==1){
x = g(x,n); y = g(g(y,n),n);
d = __gcd(llabs(x-y),n);
}
if (d==n) return -1;
return d;
}


However, the product x*x will overflow if n is too big (outside of int range). Is there a way to do the multiplication quickly (without using bigint or adding another log factor), or replacing the polynomial with some other function?

• +7

By balbit, history, 6 months ago, ,

Hello, Codeforces.

I tried to use hashing to solve 1129C - Morse Code. However, I kept getting the TLE verdict. My time complexity should be O(k * m^2) (where k is the longest string to be tested, or 4) while the editorial's solution has time complexity O(k * m^2 + m^2 * log m).

I've tried many optimizations, such as using 2^64 as a base, switching between unordered_map and map, tweaking the multiplied prime, and even adding huge strings of pragmas. Pre-doing all the hashes gave me an MLE.