Hello, Codeforces!
We are happy to announce that we're going to host a new contest at csacademy.com. Round #35 will take place on Wednesday, 28/June/2017 15:00 (UTC). If you want to take part in this round you need to register before the contest begins. 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 geniucos as a problem author.
Prizes
We've decided to continue awarding the same prizes as the previous Div. 1 + Div. 2 round:
- First place: 100$
- Second place: 50$
- One random prize, either 50$ or a custom CS Academy T-shirt, whichever the winner wants. :)
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.
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.
Later Edit:
Congratulations to the winners:
And to the random prize winner, D0GEzilla!
Also, the editorial has been published. Hope you enjoyed the contest!
Just a reminder, the round starts in 5 hours.
Unfortunately, clashes with CEOI warm-up contest :(
Funny that geniucos takes part in CEOI, but he's authoring the CSA round.
CEOI starts in 2 weeks, what warm-up contest?
Nevermind, misread the problem. Great problems though!
It wasn't. I once saw some problem asking for the something that contained max-min of subarrays(like 3 years ago) and when I read it again, I came up with this trick that I thought it is nice: to update some segment tree based on the stacks formed and have an amortized number of O(N) updates. Then, I've tried to invent some interesting problem that would require this trick. I've gone through a lot of variations of it and this was the one that seemed the cutest and was not solvable by other means.
this was the one that seemed the cutest and was not solvable by other meansI solved this using divide and conquer in O(nlogn) (after the contest). For any interval [l,r] find contribution of all intervals passing through the mid of this interval, this can be done in O(r-l). Recursively find the answer for all intervals.
That's a really nice approach I didn't think of. Congratulations on finding a different method:) I guess this makes the problem even better
If you are looking for similar problems, 407E - k-d-sequence is another problem (3 years old), that requires this method.
Can you please give a brief explanation about the Divide and Conquer approach? The editorial mentions a different algorithm.
Contest was interesting, I will become usual participant of CS Academy rounds :)
Editorials are not very clear I think, maybe you should write them a bit longer...
For the fourth task I have different approache:
If our number x has 0 even digits answer is - 1.
If our number x has 2 or more even digits just bruteforce answer with loop on the right and left side.
if out number x has 1 even digit, generate all numbers without even digits and find first bigger and first smaller.