izlyforever's blog

By izlyforever, history, 3 weeks ago, In English

Successful hacks makes Codeforces better. Here are at least two reasons:

  • A successful hack helped stable ProblemSet
  • The defenders can quickly find bugs in their own code through the test provided by hackers

So hackers make contributions to the community, they deserve some contribution.

UDP1

VLamarca's number of hacks(number of problem hacks) also a good suggestion.

If it does increases contribution, $$$\frac{100 x}{100 + x}$$$ contribution may be simple nice, where $$$x$$$ is number of problem hacks.

Fade hacks mentioned by Real_Father_Of_Ash is really annoying, it does know how to improve, but I believe that people who are loving codeforces and care about contribution won't do like this.

Really hope admin: MikeMirzayanov and geranazavr555 could take it into consideration.

Read more »

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

By izlyforever, history, 2 months ago, In English

nihal2001 posted a blog for asking the following question:

There are $$$n$$$ stones, two players take turn to choose $$$x$$$ stones, such that $$$1 \leq x \leq n$$$ and $$$x \And n = 0$$$. The one who cannot make choose lose.

Determine who is the winner, The first one or the second?

I proved that If $$$n$$$ belongs to https://oeis.org/A295897, the second player win(can be solved in $$$O(\log n)$$$).

My Question(Multiple piles version of above question):

There are $$$n_1, \cdots, n_m$$$ stones, two players take turn to choose an index $$$i$$$ and $$$x_i$$$ stones, such that $$$1 \leq i \leq m$$$, $$$1 \leq x_i \leq n_i$$$ and $$$x_i \And n_i = 0$$$. The one who cannot make choose lose.

Who will be the winner?

This turn out to compute Sprague-Grundy function for $$$n_1 \cdots, n_m$$$. The first player win if and only if $$$sg(n_1) \wedge \cdots \wedge sg(n_m) \neq 0$$$

I know how to compute $$$sg(n)$$$ in $$$O(n^2 \log n)$$$, but I can't give it a formula or compute efficiently like $$$O(\log n)$$$ or $$$O(\log^2 n)$$$

Thanks in advance.

UPD: $$$O(n^{log_2 3} \log n)$$$ implement based on wery0's comment.

UPD2: $$$O(n^{log_2 3})$$$ implement based on wery0's talk.

Read more »

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