brezhart's blog

By brezhart, history, 4 weeks ago, In English

Each of those submission scores exactly: 16331.003 and shares time/memory usage

when (UTC)	handle	        ms	mem     link
08-19 10:10	mojo__hugo	500	400 KB	387664604
08-20 03:39	Lao_mang	500	400 KB	387745570
08-19 11:25	mojo__hugo	437	400 KB	387672276
08-19 17:22	Lao_mang	437	400 KB	387712808
08-20 01:53	Lao_mang	437	300 KB	387740311

mojo__hugo and Lao_mang are from the Guangzhou University. Both participants are in top15 on pretests (top 10 and top13 accordingly) and expected to win 3000 euro each.

Treat this post as call to action. Call to investigate those solutions carefully, before posting final results. This is not direct cheating accusation

Cheating in the contests with such high monetary prices should not be tolerated.

Full text and comments »

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

By brezhart, history, 3 years 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, 5 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, 5 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