eku's blog

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

I wrote a blog post on generalizing segment trees: https://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html

It's about a method of generalizing segment trees by expressing query outputs as elements of a monoid and updates as functions. The blog post explains what a monoid is, why these abstractions are suitable and demonstrates concepts with examples.

Can I please get comments/reviews/opinions on it? Do you think it is (or can be slightly altered to make it) useful or interesting?

You can see the templated C++ code here: https://gist.github.com/sharmaeklavya2/99ed35efbb639bbe7d7b46b89b74fea0

The blog post turned out to be more detailed and theoretical than I was expecting. It's more concerned with mathematical and algorithmic aspects than the practicality of using it in contests. But I can change that if you think that would make it better.

Read more »

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

By eku, history, 3 years ago, In English,

It's difficult to test solutions to interactive problems during or after a contest. For non-interactive problems, I usually redirect input from a file. For interactive problems I have to type out input manually, since input depends on output. If the interaction is long, this can take time.

A more automated way will require 2 more programs:

  1. A judge program with whom our solution will interact.
  2. A program which connects stdout of solution to stdin of judge and stdout of judge to stdin of solution. I call this program a 'croupier'.

The judge program will have to be written by the user each time since it's problem-specific. But the croupier is generic and can be reused.

My implementation of the croupier, apart from connecting inputs and outputs of the two programs, also prints the output from each program so that it's easier to debug.

You can find my implementation here: https://github.com/sharmaeklavya2/croupier

I wrote the croupier so that it could help me debug 750F - Новый год и поиск корня. The croupier helped me find out many mistakes in my solution, but it seems like there are more, because I can't get my solution accepted. Here is the judge program I used for it: https://gist.github.com/sharmaeklavya2/fb9751ba0d9d5df883d4d29288db8315

Update: There was a small bug in croupier because of which it sometimes printed output incorrectly. Thanks you PikMike for reporting this. PikMike also tested this program on Windows, which I couldn't do myself because I don't have Windows. You can find a detailed description of the bug here: https://github.com/sharmaeklavya2/croupier/commit/a2fcd82a52a83df71518dfec248271d752a55b66

Read more »

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