Kognition's blog

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

If you had a smart friend who liked puzzles, and you could choose one problem that you thought was accessible and interesting enough to get them curious about competitive programming, what problem would you choose?

Edit: To be clear, I’m curious about specific problems, not just general topics.

Read more »

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

By Kognition, history, 15 months ago, In English,

I posted this as a comment on the last contest, but upon request, I turned it into a blog post so that it may get more attention.

Is there any way to hack consistently with regard to a segfault? There were a few times that I've seen people accessing, say, s[n] when s only had n elements allocated to it, which should cause a segfault, but because of the magic of operating systems, segfaults only happen sometimes. These people will probably fail during systests, but I can't reliably hack because even if I submit a hack, the OS might not complain about a segfault and I'll get an unsuccessful hack. Is there any way around this or should I just not try to induce a segfault in a hack?

Read more »

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

By Kognition, history, 16 months ago, In English,

A friend told me a problem that he had been trying to optimize for a personal graphics project, and it involved having an h × w grid, and wanting to do some pre-processing to answer circle-sum queries. A circle here would be defined as having some center, (yc, xc), where 1 ≤ yc ≤ h and 1 ≤ xc ≤ w and some radius r, and it is the set of integer grid points (y, x) such that (x - xc)2 + (y - yc)2 ≤ r2.

The progress he's made is that in O((hw)2) pre-processing, you can just precompute all the possible queries, so one possible set of complexities is O((hw)2) pre-processing and O(1) queries. Another possibility is to precompute prefix sums in O(hw) time and answer the queries in O(r) time.

Is there any clever way to get a better set of pre-processing and query complexity than the two methods mentioned above?

Read more »

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

By Kognition, history, 17 months ago, In English,

Anybody know where I can access old FHC problems? Every time I look this up I just get links to Facebook that are broken.

EDIT: A proper link has been posted, but the links I was trying before that were broken seem to no longer be broken. Weird.

EDIT2: I figured out why the links were broken. FHC does not support mobile viewing. So don't look at any of these links on your phone.

Read more »

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