fonmagnus's blog

By fonmagnus, history, 9 months ago, In English

Recently I was learning about the Grundy Number (a.k.a. Nimber) about how to convert a state of impartial combinatorial games into a state of a Nim Game and I was quite amazed about this

My question on this blog would be how do we usually find a way to convert a game state to a nimber?

For example consider a look on this mini game that I found recently

Assume a game of grid tiling where two players (name it Kiki and Wiwi) can place a tile to this game grid. Kiki and Wiwi's orientation of movement can be seen here

The question is how do we get a nimber of this game state? I was thinking of something like make a grid becomes a $$$2^{16}$$$ possible state and convert each of them into a nimber

But does anyone thought of another approach? I'm interested to learn it since I'm quite fascinated about this sprague grundy theorem recently.

Thanks. Much appreciated :)

Full text and comments »

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

By fonmagnus, 13 months ago, In English

I can't help but notice this

Is this the first time there will be a contest that involves the 3 divisions at once?

I wonder how the participants dan problemset will be distributed

Can't wait

Full text and comments »

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

By fonmagnus, history, 20 months ago, In English

Hello everyone, yesterday was SG NOI 2023 and I found an interesting problem which can be read here

https://codebreaker.xyz/problem/toxic

Been thinking about it for some time and I find some interesting observation(s) :

  • We can do these following strategy for query :
1
2 2
3 3 3 3
4 4 4 4 4 4 4 4
...

Basically ask 1 for $$$2^0$$$ times, 2 for $$$2^1$$$ times all the way to ask 7 for $$$2^6$$$ times

  • From that, we can determine 3 types of group : (I) group that consists of Strong and Regular bacteria (II) group that consists of Regular and Toxic bacteria (III) group that can be determined whose the Strong bacteria are
How to do that?
  • From group (III), we can find the Toxic bacteria by using this strategy : Compare each bits within the group with the Strong one. If it is dead then it is Toxic

  • Use the Toxic bacteria to determine Strong and Regular bacteria in group type (I) by using these following strategy :

Strategy

I realized there are some flaws in my idea such as :

  1. Group III does not always exist, therefore we cannot always determine the Strong and Toxic bacteria

  2. Supposed we can determine both Strong and Toxic bacteria using the strategy above. How do we identify each bacteria in group II (the one that only consists of Regular and Toxic ones)?

Let's discuss in the comment because I find this problem quite interesting and mind stimulating

Full text and comments »

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

By fonmagnus, history, 2 years ago, In English

Last night I worked on this problem on Codeforces round 823 1730B - Meeting on the Line

I've made two submissions :

  1. Wrong answer on test 3 — 173469198
  2. Accepted — 173524856

The accepted one using a setprecision function while the wrong answer one is not

After I take a look at the cause, then it stumbles upon this following message from checker : wrong answer 36th numbers differ - expected: '40759558.0000000', found: '40759600.0000000', error = '0.0000010'

How come the difference becomes very large? I know floating point has its own "weaknesses" for handling precision and stuff, but how come the difference of using "setprecision" and not using them produce a very different outcome?

Appreciate for the answers because I'm curious. Thanks!

Full text and comments »

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

By fonmagnus, history, 3 years ago, In English

Hello, I'm new to Codeforces Polygon. Right now I'm working on a problem but when I put one of the Testcase Generator it brings me to the white screen and now everytime I access to that problem it brings me to the white screen (funny enough, it doesn't happen to another problem provided as example)

How should I solve this?

Error

Full text and comments »

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