Hello, Codeforces!
We're going to host a new contest at csacademy.com. Round #54 will take place on Wednesday, 25/October/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 khadaev as a problem author.
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 round starts in 7 hours.
Why contests are always on Wednesdays?
Empirically, we noticed this is when we have most users. Are there more people who would like another day/hour?
Well, it would be better if contests are on Saturday/Sunday in my opinion.
Saturday is already taken by AtCoder :P
So, Sunday seems good.
I think that it would be better if contests are on different days.
For each day and time there are some(or a lot of?) users that can't participate at this day and time. For example, i have classes on Wednesday evenings, so it is hard for me to participate.
I wonder not only about Wednesday, but also contest time. Recently, it seems CS Academy contest starts at 00:05 UTC+9 / 15:05 UTC. I think changing starting time is better.
can someone post last problem's statement if they have it open already. (The site is down)
In CF and AtCoder first thing I do is to open all problems in different tabs to prevent exactly such situation as yours. But on csacademy doing that is a real pain :(. I can't click "open in new tab" on a name of task :(
If you click on the "Tasks" button in the navbar (yes, it's also a button, even though on hover it acts as a dropdown), you can then open each task in a different tab by ctrl+clicking.
P.S.: As I was trying to check if this is working I discovered a bug on Windows, it will be fixed later today.
Is it only me or is it showing 'Bad Gateway' for everyone?
Same here
My submit button is not working for the past 10 minutes. :(
Sorry for that. We hope we fixed it. It should be ok now. We extended the contest by 20 minutes. Enjoy!
Hmm, someone blamed codeforces for being slow and now I cannot access problems in csacademy even though there are only 900 people in the contest...
Probably will be unrated... Finally I could get to yellow (I did well) and then it's unrated...
Edit: Seems like it isn't.
We extended the contest by 20 minutes. It will be rated.
Will it be rated or unrated? (If you've decided it, we are happier if you announce it sooner.)
I have waited 30 minutes to submit D (it get AC now). It cost me a lot of penalty :(
"Closest Numbers" is online version of this.
oh, I was an author of our icpc quarterfinal in 2015, and I prepared very similar problem (online too, but less constraints).
endagorion was a tester for this problem. times later he prepared task that you shared.
now there a CSA Round #54, I have registered... but in my house turned off the electricity!!!
now its on, and I see what I missed...
anyway, as I understand, solution in editorial on csa better, bcs my used nsqrt memory.
Did I miss anything? What does logic to write the contest where you already know some problems?
There is no logic. I just noticed funny situation.
Anyway, you dont know problem until read it. But in div1 round I never read last problem first. So if I participated in this round, most probably I would see this problem after the end.
And tell me, where is the edge of "knowing" problem? What if I see problem where all needed is a classic segment tree (and maybe some additional thinking)? I need to leave contest? I need to blame myself for cheating? No, bcs this kind of logic does not work here.
And where is edge of "knowledge" of the problem? When I see this 645F - Cowslip Collections problem on contest, I say "wow, I have prepared similar, but easer, problem for camp some months ago, and I know half of the solution already, the only needed is to bit thinking to completely solve this". And I solve it. And win T-shirt. It is cheating? It is unfair? No. This logic does not work here.
And last example. Past summer I decided to participate in Snarknews Summer Series. And during one round I... saw MY problem! Just title and some terms are renamed. But this is problem that I prepared for our local competition some months ago. What was I should do? I already solved some problems on contest, and I came to compete in this contest. And I just write my solution and submit them... And I dont feel anything bad. Does I guilty? Does snark, creator of contest, is guilty? NO. This logic does not work here.
After writing this big answer, I noticed, that your question probably meaning something else. Maybe I word "logic" need to replace for "pleasure"? If yes, then ok. I dont feel competition pleasure in those situations. Only good feeling I is like — Oh, I created this/similar problem before, so its not shitty problem...
O, I wasn't right if you understood me not in full. Of course, I meant "What is the logic to write the contest [which you write only for pleasure] where you already know some problems, [and why you said "I see what I missed"]". And also I just was interested in this. I didnt mean anything bad. Good round :)
Is it CSAcademy or Codechef? Because taking an old problem and requiring online approach by using persistent trees is not the most glorious way of problemsetting. http://mirror.codeforces.com/contest/765/problem/F
By the way my solution with persistent segment tree gets OK on csacademy, but receives MLE on CF, although the constraints on csacademy are higher, and MLs are equal.
It seems that limits on csacademy are actually 5 * 104 and not 5 * 105.
I checked and this is true.
¯\_(ツ)_/¯
khadaev wtf?
How would you expect to pass
otherwise? :)
For N 500.000 if you have a constant-friendly pure sqrt, it shouldn't be that hard to fit in 4 seconds (nsqrt ~ 350 millions). If i knew N was that small, I would've used persistent segment trees...
I tried mo on codeforces problem and it got TL.
"If i knew N was that small, I would've used persistent segment trees..." — but persistent segment trees are
, aren't they? If so then there's no reason to be afraid of them, in partciular it should be significantly faster than 
which you convince us may pass.
Yes, but the other part of the algorithm was NlogNlogVmax and my implementation used more segment trees than needed, so I was afraid about the first part of the algorithm, not about the persistent segment trees themselves. logN*logVmax is about the same as sqrt for the given constraints, so everything depended on the constant, which was huge in my code.
Ahh, yes, I forgot that we perform n log V queries which gives additional log to complexity (even to memory). Now it makes sense, sorry for that
Persistent tree creates too many nodes — my solution doesn't fit into ML in CF problem for example. With 5·105 queries it would not work too.
I am sure MrDindows will be able to squeeze O(nq) in TL :D
I tried, but unsuccessful... Can't pass just single test, and I think that 20-30% speed up will be enough. But idk how.
Btw, my solution with Persistent Segment Tree works 201 ms with 58 MB memory, so I think it will pass for N = 500k too.
Haha, I didn't expect you will actually try this :D. That reminds me of http://mirror.codeforces.com/blog/entry/53457?#comment-375222 :P
Oh, know I understand why I got AC.
Yeah, it was a terrible idea to prepare this contest in just two days :(
Wut xd? I thought for a moment about exploring "n^3/2 ideas", but disregarded them as unlikely to fit into TL :(