belowthebelt's blog

By belowthebelt, history, 9 years ago, In English

Hello, Codeforces Community!

I invite you to January Easy '16 today at 2130 IST. The difficulty of the contest will be similar to div2 CF round. The problems have been set by harshil, kunal93 and I.

A lot of you can manage to solve all the 6 problems in 3 hours, for sure. The order of the problems will be random. Each problem is worth 100 points but scoring is partial so try to pass as many tests as possible!

Importantly, I want to thank Kamil (Errichto) — he is the tester and editorialist for the contest. It was amazing to work with him. He is, hands down, the most active setter/tester as of now — and an extremely productive one, too. I hope he was able to tolerate me. :)

Link: https://www.hackerearth.com/january-easy-16/

Enjoy the contest, see you all on the hall of fame!

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

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

Starts in an hour. Have fun!

»
9 years ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

How to solve GJ's invasion (P4)?

I tried to use such dp:

f[i][mask] — answer, when we built some prefix of length i and used numbers, whose bits in mask are 1. ways[i][mask] — number of ways to reach this state

Then, I try to add some guy (j = 0..n-1) and if:

1. i != j

2. (mask & (1 << j)) == 0

I update state:

f[i + 1][mask | (1 << j)] += f[i][mask] + getCount(j, mask) * ways[i][mask]

  ways[i + 1][mask | (1 << j)] += ways[i][mask]

Where getCount(j, mask) returns the numbers of such k, that (mask & (1 << k)) != 0 and k > j.

Why does it get WA?

Thanks in advance!

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Best contest on hackerearth till date!

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

fun contest :)

Had a stupid mistake on the third one because recursion stack was too big and BOOM. That happens when you spend too much time on codeforces with its hulk-strong recursion stack :P

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

fun contest :)

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Congratulations to winners! And to all fighting with problems. Now you can read editorials and upsolve problems. Remember that upsolving is maybe the most important thing in competitive programming. Will you be able to get all problems accepted? And you can always read e.g. my codes — for each problem you will see my code below the editorial.

Kudos to belowthebelt for preparing very nice problems!