flash_7's blog

Burnside Lemma
By flash_7, history, 8 years ago, In English

I was trying to learn burnside lemma and now i feel it's one of the very rare topic in competitive programming.

Here are some resources i found very useful:

  1. math.stackexchange

  2. petr's blog

  3. imomath

  4. Hackerrank Blog

  5. AlgoWiki

Here are some problems related to burnside lemma:

  1. Necklace

  2. Necklace of Beads

  3. The Beautiful Board

  4. Lucy and the Flowers

  5. Count the Necklaces

  6. Cube Coloring

  7. Magic Bracelet

  8. Sorting Machine

  9. Pizza Toppings

  10. Drum Decorator

  11. Alphabet Soup

Is there some other good resources or problems related to burnside lemma? Please suggest some more.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's another problem of some previous Ad Infinitum contest on Hackerrank. These Ad Infinitum contests are math-based contests so it is likely that Burnside's Lemma has appeared in them, although I could find only this one.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Added it. But the problem is same as the 1st problem in the list. Thanks though :)

    → Reply
»
8 years ago, # |
  Vote: I like it -15 Vote: I do not like it

I know this from the best judge in the world, CS Academy! However, I didn't look very careful to check if it's different from the ones above.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

There are a couple more problems here. The next step is then to learn about the Pólya enumeration theorem. Probably even less common in competitive programming, but still very neat.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problems link is not working.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you so much. Will try to learn the theorem soon. I'm adding the problems from the list. There are so many problems now :D

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by flash_7 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Colorful Grids : https://www.codechef.com/problems/ICPC16E

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Timus 1661 requires little coding and a lot of analysis, excellent for understanding the lemma.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the smallest set of books I should read to cover all math topics needed in CF/TC :( ?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is another problem

→ Reply