Блог пользователя Svlad_Cjelli

Автор Svlad_Cjelli, история, 2 месяца назад, По-английски

I ran into a clever trick while reading the solutions here https://codeforces.net/blog/entry/133382 (look at problem 2006C, "Implementation — Two Pointers")

The problem is: let's say there's an array $$$a$$$ and an associative operation $$${*}$$$ and we are interested in computing $$${f(l, r) := a_l * a_{l+1} * \ldots * a_r}$$$ , where we want to be able to increment $$$l$$$ or $$$r$$$ and easily recompute $$$f$$$. If we can do that, then we can solve all kinds of two-pointer-style problems.

If $$$f$$$ is invertible, e.g. addition, we can easily do this by just keeping track of a single aggregated value. But what if $$$f$$$ is something like $$$\gcd$$$? In this case, this simple solution won't work. But there is a trick.

With the simple solution, the hard part is incrementing $$$l$$$ because if we only keep the aggregated value for $$$f(l, r)$$$, we can't recover the value for $$$f(l+1, r)$$$. To do that we would ideally need to keep a list of values $$$f(l, r), f(l+1, r), \ldots, f(r,r)$$$ and then incrementing $$$l$$$ would just involve popping the front of the list. But then, incrementing $$$r$$$ is hard because we'd need to recompute the whole list.

To combine these two approaches, we keep $$$f(l, m), f(l+1, m), \ldots, f(m, m)$$$ for some intermediate $$$m$$$, and also $$$f(m+1, r)$$$. In the beginning, $$$l=m=r=0$$$ . Then:

  • to increment $$$r$$$ we simply recompute the tail value by taking $$$f(m+1, r+1)=f(m+1, r) * a_{r+1}$$$
  • to increment $$$l$$$:
    • if $$$l < m$$$ we pop the list.
    • otherwise, $$$l = m$$$. We set $$$m := r$$$, and recompute the whole list from $$$l$$$ to $$$r$$$. This may seem slow but the subarrays recomputed in this manner don't overlap and therefore this has amortized constant cost.
  • to query $$$f(l, r)$$$ we simply compute $$$f(l, m) * f(m+1, r)$$$.
  • EDIT: we can decrement l too! Just compute $$$f(l-1, m)$$$ and push to the front of the list. This doesn't break the amortized performance because we never decrement $$$m$$$.

That's it!

Note that this requires we never increment $$$r$$$, so it doesn't fit every problem.

Does this trick have a name? Is it "lore"? I haven't seen it before. But it's been a while since I've done a contest (hard to find time these days...) so maybe it's already well known. For those who haven't seen it, hopefully you find it interesting!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

Автор Svlad_Cjelli, история, 2 года назад, По-английски

I have been trying out Rust in contests and I'm curious about other people's impressions of the language, in comparison with C++. In particular I am interested in the possibility for building higher abstractions, and for better error detection.

C++ definitely has the potential to be error-prone, but I became much more consistent with it once I started using an LSP that shows me warnings/errors as I type. That plus avoiding global variables. Now I feel like almost all of my errors are logic-based rather than due to the unsafety of the language.

Here are some of my first impressions from using Rust to solve some contest problems.

Things I enjoyed:

  • iterators, map, filter, etc. I feel like the syntax is often cleaner than C++, where I would almost always default to mutable variables instead.

  • Type inference is usually good

  • Lightweight tuple and array syntax

  • Ranges

  • "const" is default

  • Automatic error tracing when compiling in debug mode

Dislikes/annoyances:

  • Recursive functions. This is the big one. In C++, recursive lambdas (with a Y combinator) are very convenient and allow for things like DFS without passing in a million parameters (and without global variables).

  • Index has to be usize

  • Casting to and from references

  • The borrow checker doesn't seem to be that useful for contest problems

I'm interested in what else the language can offer! Looking forward for Egor to weigh in.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +81
  • Проголосовать: не нравится

Автор Svlad_Cjelli, история, 4 года назад, По-английски

So, I got this email recently:

Attention!

Your solution 91837075 for the problem 1409E significantly coincides with solutions Svlad_Cjelli/91837075, SeismicToss/91842722. Such a coincidence is a clear rules violation. ...

The first weird thing is that it's accusing me of plagiarizing my own solution. OK, that's probably just a glitch.

But what about the other accusation? Here are the two solutions: https://codeforces.net/contest/1409/submission/91837075 https://codeforces.net/contest/1409/submission/91842722

They do have similar-looking logic. But this is a very simple problem — there aren't that many things to try. It's very natural to have a loop to find the best answer for a single interval, and then another loop to find the answer for two intervals.

I also have never used IDEOne or anything like that during a contest. I do everything locally.

So the possibilities are:

  • It's just a coincidence.
  • SeismicToss somehow hacked into my computer or the CF servers, using his master hacking skills to cheat on a Div3 contest.
  • I am a master hacker, and used my abilities to cheat on a Div3 contest by stealing a solution from the future (I'm also a time traveler in this scenario).

Keep in mind this contest wasn't rated for either of us so it would be even sillier for any of us to cheat.

Is there some way to manually review the plagiarism accusation? It doesn't seem to have any effect so far, but I don't want to get banned for a different false positive later. I am also a bit worried because there's another blog post (https://codeforces.net/blog/entry/60663) calling for a stricter plagiarism checker. I think that could be a disaster...

Полный текст и комментарии »

  • Проголосовать: нравится
  • +199
  • Проголосовать: не нравится