csacademy's blog

Round #75 (Div. 1 + Div. 2) with prizes, unusual day
By csacademy, history, 7 years ago, In English

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.

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

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

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

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

I think too many queries have answer K - 1.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

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!

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

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

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

    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.

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

      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.

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

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

      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.

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

      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.

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

      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.

      → Reply