Wednesday, December 27, 2017

A F5 week

The Nov 6 - Nov 12 week had two contests on Sunday. First off, it was time for the Open Cup Grand Prix of Ukraine (problems, results, top 5 on the left). Team Past Glory has won their third Grand Prix in a row — what an amazing achievement! Both Moscow IPT Cryptozoology and japan02 teams were quite close and had real chances for the first place as well — congratulations, too!

A bit later, Codeforces hosted its Round 445 (problems, results, top 5 on the left, analysis, my screencast). V--o_o--V was way too fast and thus got an easy first place — great job!

Somewhat surprisingly, problem C was the most difficult to solve (as opposed to implement) for me this round — you can probably find around 20 minutes of staring at its statement in the screencast during the moments I was trying to solve it on paper. It asked: how many permutations of size n have the following property: if you go from left to right, and keep track of the maximum seen so far, there will be no time where it will not change for k consecutive steps, except if it's already equal to n. n and k are up to a million, and the answer needs to be returned modulo 109+7. Is it easy for you?

Thanks for reading, and check back soon for the solution!

No comments:

Post a Comment