Блог пользователя csacademy

Автор csacademy, 6 лет назад, По-английски

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.

Facebook event

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$

About the penalty system:

  • 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.

If you find any bugs please email us at [email protected]

Don't forget to like us on Facebook, VK and follow us on Twitter.

  • Проголосовать: нравится
  • +92
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Since the customary comment from wefgef is missing.

bump! : Starts in around 30 minutes.

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится +69 Проголосовать: не нравится

Hope you enjoyed the contest! I'm sorry for difficulty distribution :/

Line Enemies
Diamond Dogs
MST and Rectangles

Thanks to Konijntje for providing problem F (Diamond Dogs)!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      tournament tree is often referred as "bottom-up segment tree". Maybe you might know what it is.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Something like this?

        void build(vector<int>& v) {
            int n = v.size();
            vector<int> 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]);
            }
        }
        
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    I used segment tree and i got TL; but then i random shuffled dogs before sorting and it passed!

»
6 лет назад, # |
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 ?

»
6 лет назад, # |
  Проголосовать: нравится -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%...

  • »
    »
    6 лет назад, # ^ |
    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 score

    You may disagree, but I dont see why any of this is such a big deal

    Talking about the pretest system in codeforces though...

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Approach for beautiful matrix?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        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 smallest

        last row is second smallest

        I 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.