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, In English,

Dear All,

Please recommend some annoying, implementation-heavy, and case-loaded Codeforces problems.

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.

Read more »

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

By balbit, history, 4 months ago, In English,

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.

Read more »

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

By balbit, history, 5 months ago, In English,

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?

Read more »

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

By balbit, history, 6 months ago, In English,

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.

Here is a link to one of my many failed submissions : 58709459. Please help!

Read more »

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