kayak's blog

By kayak, 7 years ago, In English

In this comment, it's mentioned that the complexity of __builtin__popcount for any integer j with j = O(2N) is O(N) (i.e ) instead of O(1). So to count the number of one in a large binary string of length n with n >  > 64, if I split n into substrings (with N = 64 / 32 / 16) and apply builtin popcount to each of the substrings and add them up, then the total time complexity should be instead of .

But in page 101 of Competitive programmers handbook on the topic Counting Subgrids, based on the time taken to compute the results, the time should be same no matter if N = 64 for N = 32. But it turns out that they're different as "the bit optimized version only took 3.1 seconds with N = 32 (int numbers) and 1.7 seconds with N = 64 (long long numbers)".

Why N = 64 takes less time ?

Full text and comments »

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

By kayak, history, 7 years ago, In English

Hello Codeforces, I'm new to competitive programming (that's I know basic c++ syntax and basic algorithms like what's in first half of "Algorithm Design"). I have a bit of math contest background (nothing good, I couldn't even make to national MO camp. Just saying this because I know a bit of combinatorics/number theory so I don't need to relearn the basic combinatorics again for OI). I have a few questions:

  1. Are Codeforces problems good for practice? Which other judges/contests (eg: COCI) other than USACO are good for OI practice, and where I can find the judge for submission and official editorials ? For USACO, is there some places where I can read the alternative solutions to a problem rather than the ones mentioned in the official editorial?

  2. While learning some C++ libraries (eg STL), should I practice implementing the features myself before learning them ? Also, which sites are good for learning the standard libraries used in OI ? I tried bunch of USACO problems, and silver ones looked easy and platinum ones looked too hard and requiring a decent algorithmic knowledge, and gold seems to be fit (hard but not too hard) for my purposes now but I don't have good implementation skills and knowledge of C++ libraries (eg idk any of <bits>/<algorithm>/<stlib>) required to code the problems.

  3. For learning algorithms, which are better: online blogs or CLRS or other books (eg CP3)? I find the contents in CLRS to be interesting and fun to read but I read in Quora that it's useless and waste of time to learn stuff from CLRS for OI (Also it doesn't provide implementation). I also have CP3 by Halim and Halim but the major problem is that there are huge amount of problems and they're not sorted by difficulty so I fear I may waste a huge chunk of my time solving easy problems and not improving. I also read some criticism for it for being not very good, is this book good or are there any other book better for learning intermediate algorithms/data structures ?

  4. I don't like to work on easy problems (which takes less than thirty minutes), and I prefer to learn algorithms more from solving problems which requires that algorithm and failing to solve them and then learning the algorithms figuring out how I could come up with it rather than learning them beforehand. This takes a twice or more time rather than learning algorithms normally, but I think this is better for practice and building intuition. Is this strategy OK, or should I do it in the reverse way?

Sorry for making this post long. Thanks.

Full text and comments »

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

By kayak, history, 7 years ago, In English

Is there anything similar to AoPS contest collection, but for informatics olympiad rather than math olympiad ?

Full text and comments »

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