brezhart's blog

By brezhart, history, 19 months ago, In English

Updating submission 4 times in a row resulting short temporary ban and it's so annoying. Can you make anti-ddos more weaker? Maybe do it more tolerant toward "trusted" users, where trusted can be defined as you like: big rating, old account, big contrib, idk. Pls do something...

Full text and comments »

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

By brezhart, history, 3 years ago, translation, In English

Im working on this problem: Given $$$n$$$ and $$$c$$$, How many sequences $$$A$$$ of length $$$n$$$ satisfy the following conditions:

  • $$$1\leq a_{i} \leq c$$$
  • $$$\forall i \in {1,2,\ldots,n-1}: a_{i} | a_{i+1} $$$ ($$$a_{i+1}$$$ is multiple of $$$a_{i}$$$)

I found really cool fact:

  • lets $$$ANS_{n,c}$$$ be the answer for $$$n$$$, $$$c$$$

  • Lets $$$A_{c} = ANS_{1,c},ANS_{2,c},ANS_{3,c},\ldots$$$

Surprisingly, $$$A_{c}$$$ can be represented as polynomial $$$P_{c}$$$ of degree exactly $$$\lfloor{\log_2{c}}\rfloor$$$, so $$$P_{c}(X) = ANS_{X,c}$$$

Why is even $$$\log_2$$$ came up here?

By the way, im struggle to find pattern for coefficients of $$$P_{c}$$$. I noticed that (Lets coefficient of $$$x^i$$$ be $$$P_{c_{i}}$$$ ) $$$P_{c_{i}} = \frac{F(c,i)}{(\lfloor{\log_2{c}}\rfloor + i)!}$$$ where $$${F(c,i)}$$$ is some weird function I cannot determine.

I attached calculated coefficients and code for calculating them, hope someone will see a pattern there.

coefficients
code for calculating coefficients

If someone have any information about it, please provide!

link to atcoder problem and my solution which uses the fact about polynomial of degree $$$\lfloor{\log_2{c}}\rfloor$$$

Full text and comments »

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

By brezhart, history, 3 years ago, In English

I feel really disappointed after todays Codeforces Round 741 (Div. 2) because of very strong samples in 1562D1 - Двести двадцать один (простая версия).

  • the fact that answer is always <= 2 is not so obvious, but samples made it clear.

  • samples also made it clear that answer is depends on parity of the sign-variable sum

I know a lot of people (including myself) who did not prove it at all. I think problem solving is not about just getting Accepted by staring at samples, but analysing problem and come up with ideas. I spent more time analysing problem A and I don't think it is right

Full text and comments »

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