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

Round #75 (Div. 1 + Div. 2) with prizes, unusual day
Автор csacademy, история, 6 лет назад, По-английски

Hello, Codeforces!

We're going to host a new contest at csacademy.com. Round #75 will take place on Thursday, 05/April/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 pb0207 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.

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

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

Just a reminder: the contest will start in 1:30

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

I think too many queries have answer K - 1.

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Any smart solution for E?
I have something like O(N * log(N) * block * log(block)) (easy to code, a bit hard to squeeze into TL), passed in 863 ms with block=1000.

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

Hope you liked the contest! If you have any feedback about the statements or examples, we can try to fix them. Also, good luck to ACM World Finalists and deadline24 contestants!

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

Just a question : Is the thing called "DFS-SPFA" significantly faster than typical O(NM) negative cycle detection algorithm?

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

    To be honest, I just found out about DFS SPFA and the first link it's a codeforces article where it states that "Time complexity : Unknown!." I'll ask pb0207, maybe he has some more insights about this matter.

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

      In my opinion, a normal contest always cannot use unknown time complexity algorithm like SPFA as the official solution.

      I have seen some contests which have SPFA as official solution and I can let it get TLE.

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

    The execution time of "DFS-SPFA" is not stable and usually we can hack the solution with "DFS-SPFA".

    For example, we can use the following generator to hack the author's solution:

    #include<bits/stdc++.h>
using namespace std;
int main(){
    int n=27,m=n*2-1;
    printf("%d %d\n",n,m);
    for(int i=0;i<n-1;i++){
        long long v1=1LL<<(n-i-1);
        long long v2=1LL<<(n-i);
        printf("%d %d %d %lld\n",n+i,n+i,0,v1);
        printf("%d %d %d %lld\n",n+i,n+i,0,v2);
    }
    printf("%d %d %d %lld\n",n,n*2-1,0,(1LL<<(n+1)));
}
    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      This hacks author's solution indeed. Is ainta's solution correct? It passes above gen but I don't know if there are any counter examples.

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

      Well, I read some reference on the internet and find out it works good at most of the test cases, but at some bad cases it's complexity is O(n^m). So sorry for the mistake I made and I'll find another better algorithm instead of this.

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

      https://csacademy.com/submission/1490838/

      I think this one won't be hack.

      It is stable O(nmlog(10^9)) algorithm with BFS spfa.

      But it's a little bit slow.

      → Ответить