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:
- First place: 100$
- 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 contact@csacademy.com
Don't forget to like us on Facebook, VK and follow us on Twitter.
Just a reminder: the contest will start in 1:30
I think too many queries have answer K - 1.
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.
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!
Just a question : Is the thing called "DFS-SPFA" significantly faster than typical O(NM) negative cycle detection algorithm?
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.
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.
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:
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.
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.
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.