Hello, Codeforces!
We are happy to announce that we're going to host a new contest at csacademy.com. Round #13 will take place on Thursday, 27/Oct/2016 16:00 (UTC). If you want to take part in this round you need to register before the contest begins. Just like the previous rounds, this will be a Div1 + Div2, with 7 tasks of varied difficulty that need to be solved in 2 hours and 30 minutes. We are honoured to have josdas, I_Love_Tina and atatomir as problem setters.
We'd also like to thank Yury_Bandarchuk for translating the statements in Russian.
This round is going to have some money prizes, as follows:
- First place: 125$
- Second place: 100$
- Third place: 75$
- Fourth and fifth place: 50$
- After the contest ends we may decide to award one or more special prizes on subjective basis.
Contest format:
- You will have to solve 7 tasks in 2 hours and 30 minutes.
- 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.
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.
Round #11 winners
As we announced before Round #11, we were supposed to award two more special prizes. Again, we decided to choose the winners randomly, using the same algorithm as in the previous rounds. So the winners of the two special prizes, each worth 50$, are Ra16bit and ajinkya1p3. The two will be contacted soon via email.
Platform changes since Round #12
New archive design
As you can see above, we've made some pretty drastic changes to the way our archive looks.
Tags and difficulty
We've also added tags and difficulty to all the existing problems. The tags are of two types: first level tags act like categories and they can nest second level tags. Clicking on a tag displays only problems having that tag OR, in the case of categories, at least one of its nested second level tags.
The difficulty of the problems falls in four categories: easy, medium, hard and hardest.
Multiple workspaces
You can now have up to 10 different workspaces. Each of them is a collection of files, one for each supported language.
Code sharing — now easier than ever
Whenever you compile/run a source, a "Share" button appears to the left of the "Compile" one. You can copy the url and then paste it wherever you want. Accessing the link opens a page like this (notice the "Fork" button):
Forking a source creates a new workspace and initialises it with the shared code.
New interview archive
Although not fully public yet, we'd like to share with the Codeforces community our new interview archive. It currently has 24 problems, some of them from previous CSA rounds, others are brand new. The idea behind this new project is to become a useful tool for everyone who is preparing for interviews with some of the top IT companies in the world. The purpose of these problems in not to AC them, but to help you learn how to explain your solution. Check out the editorials for an example.
We tried to provide you with a unique experience, many tasks supporting interactive widgets as you can see below:
^ Task Min Max Subarray
^ Task Justify Formatting
Task workspace split view
And the final platform change, we modified the task workspace such that split view works not only with the problem statement, but with all the other tabs too (editorial, submissions, etc).
We still 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.
Nice features !
I like Mike's (codeforces) and your team's works. because you really respect to your users needs and you are trying to make your platforms more comfortable and usable everyday ... I think that's why codeforces has become very popular and attracted all the competitive programmers.
I mean Mike don't think about his comfortability but his users and he has created this website by respecting to them. I feel the same about your website ...
Thanks a lot. We'll try to add even more features in the near future.
wtf "Since we had a generous time limit, we announce a special prize for the first user to solve this task in O(N*sqrt(N)) time complexity :)" in the middle of the contest?
Given that it's an announcement for everyone, without really giving any real hint for all users capable of solving the problem, what's wrong with it?
Complexity can be a big hint about how to solve the problem. I don't know many algorithms that work in more than n sqrt (n) but less than n^2.
I don't honestly think it's really a hint in this case for the people that can solve the problem, since complexities between O(N sqrt N) and O(N^2) already occurred to everyone capable of implementing them. It was meant to try to add a challenge for all that solved that ACd that task, but could have done better.
Actually I decided to code O(n * sqrt(n) * log(n)) solution after this announcement. And it passed :)
How to solve D?
You can reduce each integer to its 'reduced form' consisting only of primes whose powers mod 3 != 0. eg. 16*9*125 reduces to 2*9. For each reduced form, you have a complement value, which is the number obtained by swapping each power with 3-p. eg. Complement of 2*9 is 4*3. The sets A and B, will have ONLY complements of each other. Iterate over all reduced forms and take max {count_of_reduced_form^2 + count_of_complement^2}.
Code
So you factorize every number at some time? We are able to factorize every number in at most ~10^2 operations, right? Did you do different/better than this?
All numbers are up to 10^6, so we can factorize every number K in O(logK) with a sieve.
What is the expected approach to solve E? I had to optimize a lot to get AC (replace a 20*1e6 loop with logX*X, where X is max value in input array). :(
Hey ,my code runs in 125 ms with same complexity as yours!
Did someone solve E using Mo algorithm? I could clear 19 test cases but TLE on 20.
Had no problems with the time limit, it ran in about 2600ms in the worst case — http://ideone.com/mLPdHg.
Looks like my code got TLE because of segment tree. :(
What is the first test case for problem D? Great contest though. :)
Well, my solution which initially failed it, 8 to 8 instead of 1. So something like {8} and {1} could make it print -1, but the answer should be 2.
Nice contest, even though the tl on E made it a little easier than it was supposed to be.
About the expected problem, the word random is a bit ambiguous. It means to select from some distribution, but you didn't specify what it was (are all pairs equally likely? Or are the two numbers selected uniformly and independently?)
Of course, I could reverse-engineer the examples to figure out which one, but I wish it were clearer in the statement. For some very weird consequences of not specifying a distribution, see https://en.m.wikipedia.org/wiki/Two_envelopes_problem
We'll make sure to be more specific next time. Thanks!
The deviation of the code running time is very large. For example, during the contest the same code ran in 3.4s and 4.2s. Now I submitted the same code for F 4 times, the maximal running times on tests are 3.6s, 3.9s, 4.3s, 4.8s. Problem F is very disappointing btw.
Sorry, unfortunately that deviation is because we use virtual machines to scale a contest, which might have a 30% variability in runtime. It's impossible for us to have enough machines otherwise, since we can't buy that many physical machine, so that there's nobody waiting to have their source evaluated. We always make sure that a good solution would never fail, even with runtime volatility.
You may consider some other ways of reducing randomness such as running second time if it's TL like CF does
Great idea, didn't know CF does this. We'll try to force another machine in case of TLE.
Thanks for all the constructive feedback.
Concerning problem F, the official solution had a complexity of O(N sqrt N). Unfortunately the time limits allowed optimised Mo to pass :(
Why did you make problem G in 2D? There is easier solution in 1D? I think it makes problem worse. The idea is interesting but you killed it with "And now write ugly 2D-tree".
This was the problem author's (josdas) choice.
It's easy to try to optimise the Nsqrt solution for 1d :)
What does it mean to have "Terminated by signal 8" as a verdict?
Division by 0 or sqrt of a negative number
I tried to upsolve the last problem and I think I understood the idea for the 1D problem. But it seems too ingenious to me, I don't think I could ever come up with such a brilliant idea. So I wonder if storing SCCs or just directed graphs this way is some known technique or contestants were expected to come up with this on their own? Could someone please give me a few problems like this one, so I can get used to it, please? :)