csacademy's blog

Beta Round #3 — csacademy.com
By csacademy, 9 years ago, In English

Hello, Codeforces!

We are happy to announce that we're going to host a new contest at csacademy.com. There were plenty of users who helped us by providing lots of feedback after the last round. We'd like to help everybody for their support :)

Our Beta Round #3 will take place on Tuesday, Mar/22/2016 17:00 (UTC). If you want to take part in this round you need to register before the contest begins. Just like the previous round, the difficulty will be moderate (similar to a Codeforces Div. 2)

Contest format:

  • You will have to solve 5 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 score. 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.

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.

Platform changes since Beta Round #2:

  • Personalised source templates for when you open a new task (access them in your account settings, the worskspace tab)
  • Workspace UI clean-up (Compile/Run/etc buttons are grouped together)
  • Workspace settings persist when you load the workspace again and apply to all workspaces (font size, editor theme, etc)
  • Clean-up some g++ compiler warnings (to ignore scanf return values)
  • Stderr output was not being updated correctly sometimes
  • Backspace key was not working in some circumstances
  • Slight performance tweaks and some other small bug fixes

Unfortunately we didn't have time to fix the browser compatibility issues, so we recommend using an updated version of Google Chrome. 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.

EDIT: The editorial is ready. Congratulations to all the users and we hope you had a great time. We are waiting for you at Beta Round #4.

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

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

Great :D

I really loved Beta Round#2 , but one question:

Before Beta Round#2 you mentioned something about rating, but we didn't see it by that time, Is there gonna be rating in Beta Round#3 ????

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    We still don't have rating yet :(, hopefully by round 4. The rating will be applied retroactively, though.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting this js error: Object.assign is not a function

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm on Firefox and seems it works (with a little lag though). Will there be any features added by the contest that might break things/Is it ok to use Firefox?

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

    You are right, we did fix some bugs. But we still don't recommend using Firefox yet.

    → Reply
»
9 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I love the custom template and UI is pretty sick looking. Keep up the good work!

→ Reply
»
9 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Stack limit is 8MB, the linux default.

Seriously?...

Also perhaps I didn't notice but it would be nice to be able to upload the code instead of copy-pasteing it to the editor.

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

    Agreed, they should really increase the stack limit for later contests. 8MB is far too little...

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      Ok, thanks for the feedback. We didn't realise the stack limit will cause any problems. We will increase the stack limit to be equal to the memory limit.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Tried to submit problem for last ten minutes, but it was impossible even to save it in your online editor(both in chrome and firefox). I have always seen "Saving..." message, and other buttons("Compile" etc.) where inactive. Also tried to reopen problem page, but had the same result.

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

    Everything worked before the last ten minutes?

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

      My last succesful submission was at 0.46 — everything worked fine — and after this I've used online editor only in last 10 or 15 minutes(just copy-paste solution from local IDE). Just checked this problem in archive, my solution was right, hope this round would be unrated for me (if it will be rated in future).

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A game — It is mentioned in the editorial that it is reducible to a game of nim. Proof?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +34 Vote: I do not like it

    Basically you have a game of NIM where a move consists of choosing a heap, removing a non-empty number of objects and additionally splitting the heap in two. You can prove by induction that the Sprague-Grundy value of a heap of size X is X. If let say you split it in two heaps of sizes A and B, the Sprague-Grundy value of this state is SG[A] ^ SG[B] = A ^ B <= A + B < X. So you can only reach states with values in {1, 2,... X-1}.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I keep missing contests! How do other people manage? Is there some application that can set reminders on my cellphone! :(

→ Reply
»
9 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Here's my solution for E:

Root the tree arbitrarily. It's easy to see that all odd depth vertices should be of one color, and all even depth vertices of the other color. Let us fix odd vertices to be of RED color, and even vertices to be of BLUE color. (We'll consider the other case similarly).

Now consider a node u. Iterate over all children of u. For the subtree rooted at a child "v" of "u", calculate these 4 attributes:

  • Number of RED nodes in the subtree = a1

  • Number of BLUE nodes in the subtree = a2

  • Number of nodes at ODD DEPTH in the subtree = a3

  • Number of nodes at EVEN DEPTH in the subtree = a4

Clearly, a1+a2 = a3+a4 = total number of nodes in the subtree. Let x = abs(a1-a3) = abs(a2-a4). Basically x is the number of wrong colors in the subtree at node "v". These colors need to be removed from the subtree, in exchange for the opposite color. Obviously this "exchange" must happen via node "u". Thus for minimum number of moves, node "u" should make exactly "x" swaps with node "v". Sum the value of x for all nodes of the tree, and this gives us the total number of minimum swaps required.

(After seeing the editorial, I see that this solution works in almost the same way as the one described there, only difference being in the understanding of why it works. But since I had written most of it before the editorial came out, I'm still leaving this here in case anyone finds this one easier to understand. Also, because otherwise it would be a mammoth waste of time and effort. ;) )

→ Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Thank you for the round and the amazing simulations. May I ask what is the technology used behind them, and from your experience when preparing a problem is the simulation part the most time consuming?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    We have our own framework for visualisations in pure JavaScript. It takes about a day for one of us to create the simulation for a problem, Thank you for the compliments!

    → Reply
»
9 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Hi Csacademy, I have seen you made some changes, which means you are willing to make some differences to suit the competitors, I would like to have 1 suggestion/experiment:

Since start time has been a big concern to competitive programmer, it would always be great if we can have a start time suits everyone. However, our competitors are from all around the world, this is impossible. But how about this, we will make 2 identical rounds with the separation of 12 hours, e.g: if 1 round is intended to start at 7pm UTC, let's have another round at 7am UTC. Why this might work: because with the separation of 12h, it's very likely that everyone can find a suitable time, e.g if 5am is your sleep time, then 5pm looks like a suitable time (except if you works). Cheating might be possible but participating to the same round in 12h would be boring, also it's unlikely to find 2 suitable time slots with 12h apart. Also, rating is not implemented on csacademy, so cheating is somewhat discouraged. I hope you would consider my suggestion.

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

    Time zones are a big concern, indeed. We were actually thinking of hosting rounds at different hours (similar to TopCoder's policy). But until our platform becomes more stable the rounds will continue taking place at 17:00 UTC.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a different solution to Moving Segments, which I think reflects how weak the time limits are. Instead of doing a sweep line, observe that the answer for a point x and an interval [a, b] is merely just max(0, |x - (a + b) / 2| - |(a - b) / 2|) This function has derivatives  - 1, 0, and 1, so it is effectively unimodal, since we are only trying to solve for the answer. Hence, we may apply a ternary search: 

#include <bits/stdc++.h>

using namespace std;
typedef pair<long double, long double> PII;
static vector<PII> pairs(100005); 
int N;
long double f(long double x){
    long double res = 0.0;
    for (int i = 0; i < N; i++){
res += max((long double) 0.0, abs(x - (pairs[i].first + pairs[i].second)/2) - abs((pairs[i].first - pairs[i].second)/2));
    }
    return res; 
}
int main() {
    long double l = -1e9, r = 1e9;
    cin >> N;
    for (int i = 0; i < N; i++){
        long double a, b; cin >> a >> b;
        pairs[i] = make_pair(a, b);
    }
    for(int i=0; i<200; i++) {
        long double l1 = (l*2+r)/3;
        long double l2 = (l+2*r)/3;
        if(f(l1) > f(l2)) l = l1; else r = l2;
    }
    cout << setprecision(0);
    cout << fixed;
    cout << f(l) << endl;
}

This easily runs under the time limit, even without i/o optimization. Was allowing such solutions intended?

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

    The sum of distances is a convex function, and based on that we have a linear time solution which you can find in the editorial :). So yes, it was intended for O(NlogN) solutions to pass.

    → Reply