balbit's blog

By balbit, history, 3 years ago, In English

Inspired by ivan100sic's problem list blog, I'll pick 10 nontrivial-seeming recent POI (Polish Olympiad in Informatics) problems that I haven't solved and track my progress here.

It seems to me that POI is better suited for this format as their editorials are quite difficult to find (if possible at all).

While Ivan's original challenge was supposed to last an entire year, I'm not nearly as patient, so I won't look for editorials only until February 1st (in just over 2 weeks). Hopefully I'll have completed at least 80% by that time. Until then, GLHF!!!

The List:

  1. Multidrink 2013 [Solved Jan 15]
Fun-ness:
  1. Snake 2014
  2. Arkanoid 2016 [Solved Jan 16]
Fun-ness:
  1. Strikes 2017 [Solved Jan 16]
Oops
  1. Rally 2014 [By the way, I've been stuck on this one for super long. Currently getting wrong answer on one test case (89 pts) for unknown reason.] [UPD: I ACed this problem, but my solution is wrong. It's just very hard to block with a random generator. I'll try to think of & write a proper solution when I have some more time.]
Current Spaghetti Code (with brute force checker and generator...)
  1. Trips 2015 [Solved Jan 18]
Fun-ness:
Help
  1. Panini 2017 [Solved Jan 19]
Fun-ness
  1. Crossroads of Parity 2017 [Solved Jan 19]
Fun-ness
  1. Hydrocontest 2016 [Solved Jan 30]
Fun-ness
  1. Sorcerers 2015 [Solved Jan 31]
Fun-ness
  1. Direction Signs 2015 [Solved Jan 20]
Fun-ness

Note: I'll also leave comments/hints here in case I manage to solve them or (unfortunately) have to dig around CSDN for their solutions :)

Full text and comments »

Tags pow, odz, eni, abh, ai
  • Vote: I like it
  • +149
  • Vote: I do not like it

By balbit, history, 4 years ago, In English

I noticed that finneganpierson's blogs have disappeared. Does anyone know where they are?

I think I'm already forgetting the top 10 ways to get started on your next software development project...

Full text and comments »

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

By balbit, history, 5 years 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.

Full text and comments »

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

By balbit, history, 5 years 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.

Full text and comments »

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

By balbit, history, 5 years 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?

Full text and comments »

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

By balbit, history, 5 years 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!

Full text and comments »

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