Hello, Codeforces!

We're going to host a new contest at csacademy.com. Round #72 will take place on Wednesday, 07/March/2017 15:05 (UTC). This contest will be a Div1 + Div2, with 7 tasks of varying difficulty that need to be solved in 2 hours.

We are glad to have ko_osaga as a problem setter.

Recently, Facebook has reintroduced the possibility of recurring events. If you choose "Interested" here, you will be notified before each round we organise from now on.

#### Contest format:

• You will have to solve 7 tasks in 2 hours.
• There will be full feedback throughout the entire contest.
• Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
• Tasks will have dynamic scores. According to the number of users that solve a problem the score will vary between 100 and 1000.
• Besides the score, each user will also get a penalty that is going to be used as a tie breaker.

#### Prizes

We're going to award the following prizes:

1. First place: 100$2. Second place: 50$

• Computed using the following formula: the minute of the last accepted solution + the penalty for each solved task. The penalty for a solved task is equal to log2 (no_of_submissions) * 5.
• Solutions that don't compile or don't pass the example test cases are ignored.
• Once you solve a task you can still resubmit. All the following solutions will be ignored for both the score and the penalty.

• +92

 » 5 years ago, # |   +13 Since the customary comment from wefgef is missing.bump! : Starts in around 30 minutes.
•  » » 5 years ago, # ^ |   0 Thanks for the fast editorials! What's the difference between a tournament tree and a standard max segment tree? Does anyone have resources for learning about this?
•  » » » 5 years ago, # ^ |   +5 tournament tree is often referred as "bottom-up segment tree". Maybe you might know what it is.
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 Something like this? void build(vector& v) { int n = v.size(); vector tree(2 * n + 1); for (int i = 0; i < n; ++i) { tree[i + n] = v[i]; } for (int i = n - 1; i; --i) { tree[i] = max(tree[2 * i], tree[2 * i + 1]); } } 
•  » » » » » 5 years ago, # ^ |   0 Yup
•  » » » 5 years ago, # ^ |   +8 Yeah, tournament tree is nothing new but a standard max segtree. There's a ton of way to call such binary tree, for example "indexed tree", "non-recursive segment tree", "bottom-up segment tree", "RMQ", "max segtree", etc..However, recently I started to use the word "tournament tree". This word expresses the nature of the DS very well, and it's also short and clear.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Do you use tournament tree in this case because iteration is faster than recursion or is there more?
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +8 Just because why not..? Tournament trees are easier to implement
•  » » 5 years ago, # ^ |   -10 I used segment tree and i got TL; but then i random shuffled dogs before sorting and it passed!
•  » » » 5 years ago, # ^ |   0 I just got an AC with normal segment tree with no randomization. Here, is the link to my submission https://csacademy.com/submission/1420487/
 » 5 years ago, # | ← Rev. 2 →   0 ko_osaga Please take a look at this for problem circle kingdom.https://csacademy.com/submission/1421015 (Acc solution after contest)https://csacademy.com/submission/1412943 (TLE during contest)Both have same code with just Input difference. I suppose scanf is fast enough but it times out. Why ?
•  » » 5 years ago, # ^ |   0 https://csacademy.com/submission/1413832/I also had the same issue, but with the memory problem , one leads to TLE(with lower memory)and other one to AC(with higher memory usage).
 » 5 years ago, # |   -10 This dynamic scoring is a piece of crap. It should be turned off. Not only it does not work: in div 2 contests, div 1 participants affect dynamic scoring. But also it provides strange point values, i.e. 300 points for C and D even though one was solved by 49% and the other by 34% and 100 pts for A which was solved by 96%...
•  » » 5 years ago, # ^ | ← Rev. 2 →   +31 It seems that your arguments are against the way the dynamic scoring is implemented, not against dynamic scoring itself. Would you prefer a wider range of score distribution? (so that C and D would have diferent scores)Also using Div1 contestants to change the dynamic score in Div2 contests is arguably better because it is a larger sample of people to define better the scoreYou may disagree, but I dont see why any of this is such a big dealTalking about the pretest system in codeforces though...
 » 5 years ago, # |   0 Approach for beautiful matrix?
•  » » 5 years ago, # ^ |   0 Border row/column contributes A[1] + 2*(A[2]+A[3]+..+A[N-1]) + A[N], whilst middle 2 times more. Calculate such sum for every row/column and consider exchanging border ones with 3 smallest middle ones. Chose the best swap.
•  » » » 5 years ago, # ^ |   +3 Well my approach was same but I replaced border row/column with only 1 smallest row/column. Can you explain how you arrived at the conclusion of replacing with 3 smallest row/column. Thanks.
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 Even trying to replace with every other row will fit time limit. Now, when I'm thinking about it, it looks like 2 is enough.You may have the following case:first row is smallestlast row is second smallestI was thinking that you may not be able to replace the first 2 smallest values, but... it is already an optimal case. No need to replace anything. You must check 2 in case the smallest is already placed on the border.Edit. When I looked again on my previous answer — 1 smallest middle value is definitely enough. But as I already mentioned, in order to get that, you should check 3 globally smallest values. And as I wrote above looks like just 2 of them will be fine.