This week was extremely packed with competitions - I think this might be the new record for the number of scoreboards in one summary. Consequently, there were a couple nice problems, so if you haven't solved all of this week's competitions (:P), read on!
First off, Codeforces held its Round 399 on Monday (problems, results, top 5 on the left, analysis). y0105w49 and W4yneb0t had a fiery challenge competition and have managed to overtake the only contestant who solved all problems, V--o_o--V. Congratulations to all three!
TopCoder SRM 709 on Tuesday offered the deceptively little 800 points for the hard problem (problems, results, top 5 on the left, my screencast). Just 3 competitors have managed to grab (some part of) those points, and thus -XraY-'s dominating victory is even more impressive!
Codeforces Round 400 on Thursday continued the non-stop week (problems, results, top 5 on the left, analysis). The challenges were not in abundance this time, and thus the coding speed and accuracy came to the forefront. ainta was a tiny bit faster this time, and made fewer submissions that didn't pass pretests - congratulations on the win!
On Saturday, Mujin Programming Challenge 2017 on AtCoder offered monetary prizes for the top performers (problems, results, top 5 on the left, analysis, my screencast). Tourist has claimed the first prize by being way ahead of everybody on the hardest problem - well done!
I think problem B in this round provided a nice way to practice one's skill for dissecting a problem step by step until it becomes trivial. You were given a square n times n matrix with each cell either black or white. In one step, you could take an arbitrary row of the matrix, and replace an arbitrary column of the matrix with the values from the chosen row. Your goal is to make all cells black. What is the minimum number of steps required to achieve that?
Right after the AtCoder round ended, Codechef held its February Lunchtime 2017 competition (problems, results, top 5 on the left, my screencast). The problems were a bit easier than in other competitions mentioned in this summary, but still provided a nice challenge!
Codeforces Round 402 started at the same time with the Open Cup round (problems, results, top 6 on the left). As a result, many active ACM ICPC participants have skipped the Codeforces Round, but the competition remained fierce. Congratulations to bmerry on finding a unique set of problems to solve and winning thanks to that strategy!
Finally, the aforementioned Open Cup 2016-17 Grand Prix of Wroclaw also took place today (results, top 5 on the left). Problem F was right in the middle by difficulty level, and required a nice observation to come up with a O(n2) solution.
Consider a permutation of size n. For each number, we can compute its radius: the largest number r such that r numbers to the left of our number, and r numbers to the right of our number, are all smaller than that number. For example, for the permutation "1 3 2 6 4 5" the radii are "0 1 0 2 0 0". Given the sequence of radii, how many different permutations correspond to it?
Thanks for reading, and check back next week! (which promises to be much calmer)
I think problem B in this round provided a nice way to practice one's skill for dissecting a problem step by step until it becomes trivial. You were given a square n times n matrix with each cell either black or white. In one step, you could take an arbitrary row of the matrix, and replace an arbitrary column of the matrix with the values from the chosen row. Your goal is to make all cells black. What is the minimum number of steps required to achieve that?
Consider a permutation of size n. For each number, we can compute its radius: the largest number r such that r numbers to the left of our number, and r numbers to the right of our number, are all smaller than that number. For example, for the permutation "1 3 2 6 4 5" the radii are "0 1 0 2 0 0". Given the sequence of radii, how many different permutations correspond to it?
No comments:
Post a Comment