Errichto's blog

By Errichto, 5 weeks ago, In English,

Hi. The next Boring Programming Stream will be on Tuesday, 12:00-16:00 CET (youtube link with countdown or Twitch) and some of the things I might do are:

  • Rearranging videos on my channel.
  • Answering comments under videos.
  • Writing editorials for my old problems.
  • Learning Burnside's lemma.
  • Upsolving 1109C - Sasha and a Patient Friend.
  • Reading IOI syllabus.
  • Adding timestamps to my lectures on Youtube.
  • Planning the next lecture (or Facebook posts).
  • Choosing graphics (banner and thumbnails) for my channel.
  • Answering people's questions and comments, also from Codeforces blogs.

See you!

My Youtube channel: https://www.youtube.com/errichto.
I will stream on Twitch at the same time: https://www.twitch.tv/errichto.
Follow me on Facebook, Twitter and Discord.

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

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

It starts in 15 minutes :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The hackerrank's burnside lemma tutorial is super shitty and it is simply incorrect.

You had some doubts which transformations you should consider. You have to have a group of transformations to apply the lemma which means that:

  • there is an identity transformation

  • when you compose two transformations you get another transformation,

  • each transformation has an inverse transformation,

In the example on hackerrank those 3 transformations are not a group, because the composition of the two reflections is not considered.
Usually, the numerator is not divisible by the denominator when you make such a mistake.

So to do this correctly you have to also consider 4th transformation which is a composition of the two reflections.

If I am not mistaken there are 6 fixed arrangements for this fourth transformation, so the correct answer should be

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot! I thought about it today and now I think I understand it much better thanks to your comment. And I agree there are 6 arrangements for the composition of two reflections (so, a reflection with respect to the middle cell).