GDCass1ni's blog

By GDCass1ni, history, 6 months ago, In English
Statement
Hint 1
Hint 2
Hint 3
Solution

UPD Thanks to nonrice and sammyuri, I fix the solution.

Full text and comments »

  • Vote: I like it
  • -44
  • Vote: I do not like it

By GDCass1ni, history, 7 months ago, In English

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 ?

Full text and comments »

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

By GDCass1ni, history, 8 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • -24
  • Vote: I do not like it

By GDCass1ni, history, 9 months ago, In English

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.

Full text and comments »

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

By GDCass1ni, history, 10 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • -42
  • Vote: I do not like it