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

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

Now we can paste the problem statements into google and we can get the link of that problem.

But sometimes the statement is modified and only the samples keep the same.

So how to find problems by samples ?

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

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

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

I have a class during the contest, so I need it to be adavanced by 1 hour so that I can participate it fully.

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

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

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

I got completely comfused in the editorial of DIV2 E.

let it be number $$$y$$$. Then it is clear that all bits from $$$w$$$ will be included in the answer, then we make a new pair $$$(x'_i, y'_i)$$$ = $$$(x_i - w, y_i - w)$$$

What is $$$w$$$? Where did the $$$w$$$ come from? Are you meaning $$$y$$$ ?

Iterate over bit $$$i$$$ and similarly to the case $$$x = 0$$$ consider the same cases, but for the array $$$y'$$$. Also, take into account that the bit occurs in $$$W$$$.

I think this sentence is written for people who have already known how to solve this problem. It is completely unreadable and meaningless.

Don't write editorials for MIKE. Please, write something understandable.

Please always remember, people who read your editorials do not know how to solve this problem, and not all readers can understand it as easily as tourist.

UPD1: It seems that the writter has modified the editorial and the first issue has been fixed.

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

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

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

Today I'm going to introduce an amazing algorithm — Prefix Sum.

First, let's consider below problem.

Problem

You could solve it by brute-force, but it was too slow.

Let's consider Prefix Sum — let $$$s_i = \sum \limits_{j=1}^i a_j$$$, we could answer queries in $$$\mathcal O(1)$$$, the sum of $$$[l,r]$$$ is $$$s_r - s_{l-1}$$$.

Then let's learn how to perform changes. When $$$a_x \gets y$$$, $$$s_x \sim s_n$$$ will change. We could just change it one by one and perform a change in $$$\mathcal O(n)$$$.

Time complexity: $$$\mathcal O(nq)$$$, which is fast enough to pass the tests.

implementation

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

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