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

Автор csacademy, 8 лет назад, перевод, По-русски

Привет, Codeforces!

Мы рады сообщить, что через два дня стартует новый бета раунд на csacademy.com. Сразу же хотели поблагодарить Вас за отклики, которые Вы оставляли. Спасибо огромное, ребят! Вы даёте нам шанс стать лучше:)

Наш бета-раунд #3 состоится во вторник, 22.03.2016 в 20:00 (мск). Если Вы хотите принять участие в этом раунде, Вам необходимо зарегистрироваться перед началом соревнования. Как и в предыдущем туре, уровень сложности будет средним (похожим на codeforces Div. 2)

Формат состязания не изменился:

  • Вам предлагается решить 5 задач за 2 часа.
  • Вы будете видеть ваш результат в режиме он-лайн, сразу после решения проблемы в таблице результатов;
  • Задачи не будут засчитываться частично: то есть либо вы выполнили задание, либо нет (ACM-style);
  • Оценки будут присваиваться в динамике: в зависимости от количества пользователей, которые справились с проблемой, оценка будет варьироваться от 100 до 1000.
  • Помимо баллов, у каждого участника будет "пенальти", который будет учитываться при определении победителя.

Что такое система "пенальти"?

  • Пенальти вычисляется по следующей формуле: время, потраченное на выполнение последнего выполненного задания + "пенальти" за каждую решённую задачу. "Пенальти" для каждой решенной задачи равен log2 (no_of_submissions) * 5.
  • Решения, которые не компилируются или не подходят для примеров тестовых случаев игнорируются.
  • После того, как вы решили задачу и отослали результат, вы можете поэкспериментировать с решением, все последующие ответы уже не будут учитываться.

А ещё, мы приправили этот раунд новыми ништяками, читайте на странице регистрации ;)

Мы все еще работаем над тем, чтобы исправить проблемы с совместимостью браузеров, поэтому пока мы рекомендуем использовать обновленную версию Google Chrome. Если вы обнаружите какие-либо ошибки, пожалуйста, напишите нам на [email protected] или в комментариях.

Вы можете найти нас на Facebook, ВКонтакте и Twitter

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

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

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

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

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

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

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?

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

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

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

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

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

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.

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

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

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

      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.

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

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.

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

    Everything worked before the last ten minutes?

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

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

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

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

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

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

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

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

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

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

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

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?

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

    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!

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

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.

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

    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.

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

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?

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

    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.