csacademy's blog

By csacademy, 7 years ago, In English

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.

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

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Since the customary comment from wefgef is missing.

bump! : Starts in around 30 minutes.

»
7 years ago, # |
Rev. 5   Vote: I like it +69 Vote: I do not like it

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)!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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]);
            }
        }
        
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Do you use tournament tree in this case because iteration is faster than recursion or is there more?

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

          Just because why not..? Tournament trees are easier to implement

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

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

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like it

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

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

Approach for beautiful matrix?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.