Hello, Codeforces!
Welcome to the Codeforces Raif Round 1 (Div. 1 + Div. 2) supported by Raiffeisenbank, that will start on Oct/17/2020 16:05 (Moscow time). It will be a combined rated round for both divisions. Note that the start time is unusual.
All problems were authored and prepared by bensonlzl, oolimry, errorgorn, dvdg6566, shenxy13.
Ari gato to:
isaf27 and KAN for round coordination and help with preparation
zhangguangxuan99 for being epic IOI trainer <3
Our army of testers: Ari, KAN, Monogon, prabowo, SYY, SleepyShashwat, TeaTime, Tlatoani, -rs-, agul, cstuart, dantoh, jhkoh, kai824, kymmykym, lperovskaya, mango_lassi, morzer, Retired_cherry, socho, zhangguangxuan99, zscoder for their invaluable advice and suggestions.
MikeMirzayanov for great systems Codeforces and Polygon.
You will be given 8 problems, one of which would be divided into easy and hard versions, and 150 minutes to solve them.
We hope that statements are short and pretests are strong and that you find the problems interesting! Good luck, have fun and we wish everyone high ratings!
The scoring distribution will be announced closer to the beginning of the round.
Thanks to Raiffeisenbank, winners will get awesome swag:
1st-3rd place = Bluetooth speaker
4th-10th place = Bumbag
11th-20th place = Power Bank
Random 50 participants outside of top-20, who solved at least one problem will receive:
Thermos Mugs
Raiffeisenbank t-shirt
About Algorithmic Trading team in Raiffeisenbank
We develop a high-frequency trading (HFT) system for equity, currency and derivative markets. Our business edge is in technology. The main goal is to create a top-notch platform based on fundamental and statistical models and machine learning, with low latency and high throughput. The efficiency and scalability of our code give us a competitive advantage. We are passionate about code quality and strive for highest standards in product development.
If you are interested in internship and employment opportunities in the Raiffeisenbank algo-trading team Capital Markets, or want to get in touch with the bank's recruitment , fill out a form below.
UPD: Scoring distribution: 500 — 1000 — 1000 — 1500 — 1750 — 1750 — (2250+750) — 4000
UPD2: Editorial out!
UPD 3: First ACs and winners
First ACs
A: 300iq
B: icecuber
C: Not-Afraid
D: Radewoosh
E: Errichto
F: fmota
G: Radewoosh
H: Radewoosh
Top 5
Congratulations to everyone!
As a tester, make sure to stay hydrated!
if you get more upvotes than blog i will swallow a battery
go swallow your battery
Let poor errorgorn think that at least he's got a chance
errorgorn: "NO" !)
Would you like recipes?
I'll press charges.
Please, some things are not good to joke about
The press charges is an involuntary good joke though. Because battery.
Check the previous edition of the comment.
I'm aware, not a good topic to joke about haphazardly. Just saying there was a decent involuntary joke in there.
Blog: 20 upvotes Comment by Monogon: 28 upvotes!
errorgorn, I think it's happening because of your reply to the comment.
Good Luck :) Let's see who wins xD
Well I upvoted the blog because of his comment. Haha no t didn't. I expected atleast one upvote from errorgorn
Did you also downvote Monogon's comment?
Videos or it didn't happen
(Please don't actually swallow batteries)
You can swallow potato battery, lemon battery, etc
ohya i think you can use potatoes / lemons to charge phones / be used as a weak electricity source (i think it might have something to do with electrolytes?). So they are batteries in that sense.errorgorn Just swallow a cherry or smth.
Also apple battery, grape battery can be the better choice
Err......I don't think so. Because once the potatoes or the lemons are used as battery,it will be filled with heavy metal ions.So it will still be harmful.
Swallowing batteries is pretty dangerous, right? (like what happens then it's in your stomach?)
You must be very fun to have around at parties.
I believe Monogon asked you to comment. Truly wonderful the mind of monogon is. The way you harvest upvotes is simply brilliant.
Monogon is a record holder, and I think you said so because you are a master at swallowing batteries
GL
Actually, fruit can be used as batteries.
I believe that the real purpose of errorgorn's comment is to help Monogon hit 200 contribution.
You actually won the bet against the almighty Monogon!
Monogon's Masterplan to hit 200 contribution with just one comment
Absolutely strange prizes distribution, but ok. Waiting for nice contest!
All the author are from Singapore zoo. Why zoo?
Will be answered in task description (implicitly or explicitly)
Don't worry though, statements will still (hopefully) be short.
Firstly finish your drink then we would talk about it.
Please don't upvote the above comment. It is aesthetically pleasing as of now.
Okay
It was 69 when I saw it :(
People just don't listen.
But unfortunately it will reward us a big negative delta :'(
Ok it's not funny my bad
.
I just want T-shirt
Amazon has some.
Guys, list of participants looks weird.. There are lots of unrated users with the strange handles..
Very interesting, there is probably just one person behind them all.
Should tag MikeMirzayanov, I don't think setters can do much about it.
What if they change the rules a little bit so only rated participant can receive the prizes?
any many more
Yeah, rules should be changed.Prizes should be only for rated participant.
For which the participation of accounts seemingly would be much more. Mainly the submission of problem A can be huge with copied code in different account
If all these accounts are created by a single person, I wonder how can someone remember so ugly handle names!!
His browser will remember it with password.
Microsoft UI Automation can certainly do some nasty stuff.
Looks like now these accounts have disappeared from the registrants list.
what if new users will not write this round? (I think everyone wants T-shirts from legendary codeforces.)
Fixed it.
None of the japanese coders here have noticed the Arigato pun in the statement :(
I think they're trying their hardest to forget it :)
CF has really given us a variety of rounds this year :o
We've had a polish round, indian round, russian round, chinese round, japanese round and now we're being blessed with a singapore round followed by a romanian round.
Also this year was the first Cuban round.
And the first my little pony round...
Codeforces Round 259 (Div. 1)
Also there was my round this year
next round when
The proposal is already in queue
Hope none of the duplicate account get prizes.. Not because I am envious it's just that it would be undeserving... (And now don't downvote me from your duplicate account else I will understand this world is doomed).
Just curious about the facts on score distribution, I don't know--- what is the basis of scoring distribution? Why is scoring distribution announced before the round, and not before that? Also, do the rounds get tested without scoring distribution?
We haven't announced scoring distribution because we're still discussing it :) I'm not sure about other round authors. Usually scoring will have some basis in difficulty, since we want to make sure that solves are rewarded fairly. As a result, obviously rounds must be tested without scoring distribution, since we get difficulty feedback (and thus basis for scoring) from testers.
It clashes with COCI can you delay the contest?
These weekends: Codeforces Raif Round 1, SRM, COCI, AGC, Kickstart, CF Div2, Cook Off. Pls tell how to fit everything without intersections.
Sounds like a problem statement
There are multiple number of rounds these weekends, and coordinator antontrygubO_o needs to schedule the contests so that there will be no intersections! Please help poor antontrygubO_o figure out how to reschedule the contests! The first line contains N, the number of contests. For the next N lines, two inputs A and B, respectively the starting and end time of the contests will be given. Print the optimal number of...
I think you missed today's ABC xD
Which was shit tbh :(
Just like last week, I will go live just after the round ends to discuss my solutions https://www.twitch.tv/errichto
Also, that's the ugliest bluetooth speaker I've ever seen.
Is that an excuse for not coming in top 3?
Yes. Prizes in top20 aren't interesting so I will aim for 21st place. Or around 300th again, just like in last contest just to avoid getting unnecessary stuff. True story.
Try not solving a problem. Who knows you might get the random one :D
Seems like, you'll have to do with the unnecessary power bank now :p
You should always follow "True story" with "Yeah yeah"
UPD: going live now!
Google Translate told me that swag means goods that be stolen. How funny it is :)
Hope this contest will be a good contest UwU
Hey, I'm flattered! Can't skip this one now
[
Is contest rated ?
It will be a combined rated round for both divisions.
Not rated for you, rated for others.
Codeforces ain't perfect, but when you compare it to other sites like codechef, it's considerably better imo.
Is this supposed to mean that Mike does a bad job?
I suppose not
Do you believe world's best boss was bad at his work? That's offensive.
i guess you got it wrong. my context was, after getting the same compliment for so many time, that will be Mike's reaction if this handshake happen in real right now
I don't think being imperfect means you are doing a bad job. Every system will always have its faults, but codeforces is comparatively far better than anything else that is available.
You went philosophical there. I'm just asking about the meaning of this meme. Michael in pic doesn't seem to know what he's doing.
Are there remote jobs at Raiffeisenbank?
There is a form to join them at the end of the blog
Another global round!!
I hope to solve all of problems
[Deleted]
answered in annoucement (implictly or explictly)
Sorry,that was sent by my classmate. I owe you an apology for not looking after this matter.
Tell us his/her handle...
I remember I read short statements XD
How to hack a problem i locked?
Go to room tab at the top. Click on some submission. Read his/her code. If you believe you have a counter case, click on the Hack! button below.
But why submissions is unclickable?
maybe you are trying hack submissions of people not in your room, click on room on the dashboard and then try clicking on submissions of the people in there
Is there a way to delete an accepted submission? I got C accepted at 00:24, and then I thought I would test another solution, and it turns out the system only counts the last submission even if all of them are accepted. Please tell me why this is a thing, so annoying going down 2k places for something that doesn't make any sense
Passing pretests during the contest does not mean it is correct. Therefore, sometimes a contestant may want to resubmit their solution which the pretests may not have caught their bug. This is why the rules are designed this way.
Did I choose wrong problem?
Good contest!!
Amazing problem D!
What was amazing about D? Seemed like mindless implementation to me. Unless there is some elegant way of solving it?
Of course there is a elegant way!
How can you call this elegant?
What is test 4 in D ??
well you can send your code to figure out where is your problem : ) (and dont send your submission link because ig seeing others code is unavailable rn)
also, I think my code isn't clear enough to read :) so this is my solution
1- I tried to make the columns with number 2 ok by matching them with a column with number one in front of it
2- we can't do anything with the remaining columns with number 2 so if anything was remaining from them, there is no answer
3- let's match the last column with number 3 by a column with number one in front of it witch isn't used while now
4- now we can make the other columns with number 3 ok by matching it with the column 3 in front of it
5- we can easily make the columns with number 1 ok now
well you can match the number 3 with 3 type of things. 1) the ones who is not match with any 2(free one). 2) all of the columns with number 2 -> just put a higher mark on top of the last one and another one with the same height. 3) with another 3.
You can match a 3 with a 2.
probably
3
3 2 1
what the fuck is pretest 3 of E
wtf is pretest 4 of E?
try:
2 4
9 4
43?
it should be 45, right? 4, 9 -> 4, 4, 5 -> 4, 4, 2, 3
but we can do better by 4 9 -> 4 3 3 3. Aren't we?
Nah 4,9 -> 4,3,3,3 so 43
How to solve G?
How to do E?
Let's consider you converted the first part into x1 part, the second one into the x2 part ...
find out how much you can reduce from the final answer if you cut the i_th part another time(convert it from x_i part to x_i + 1 part)
put the values inside a priority queue and do the best option each time
how to do b?
Let's first iterate over the string and check if we have any
cw
oracw
paths. Now, everytime we encounter anoff
path, we can mark it as a good path. If we encounter acw
path, we need to make sure that there are no otheracw
paths and vice versa. Also, another case is when the previous or the next path (leading to and from a node/snake) is off, we can mark this node as good.Isn't E just about always taking the maximum number
m
and separating it intop = m / 2
andq = m - p
for all maximums, which can be implemented by priority queue? If not, could someone explain why?1 3 8 you way : 4 2 2 the better answer : 3 3 2
Hi my logic gives correct answer for this case...but i got WA on test 4.
My logic : https://codeforces.me/blog/entry/83730?#comment-710946
n = 2, k = 2, array = {1, 9}, your answer : 50, the real answer 82.
4 8
2 4 5 8
You algo give answer 49 (2, 2 2, 2 3, 2 2 4)
But correct answer is 47 (2, 2 2, 2 3, 2 3 3)
It isn't always an optimal option. For example for input $$$[2, 4, 10, 5]$$$ your algorithm would divide $$$[10, 5]$$$ into $$$[2, 3, 5, 5]$$$ while an optimal division would be $$$[3, 3, 4, 5]$$$.
Ah, crap, I didn't realise we were allowed to do that. RIP my problem reading skills. I'll leave trying to become better at problem solving and go and start learning primary school english.
For E, to generate k carrots with minimum eating time, I derived that the $$$a[i]$$$ carrot should be split into $$$\frac{a[i]}{\sum_ia[i]} * k$$$ parts. But since each carrot should contribute to atleast 1 piece, I could not incorporate this fact into that. Can anyone provide insight on this?-
Any final split is equivalent to splitting $$$a_i$$$ into $$$j$$$ pieces, which can be optimally solved by for any $$$j$$$. The final answer will be the smallest that has a total of $$$K$$$ times. The function for the difference between $$$j$$$ and $$$j+1$$$ is nondecreasing, so it's optimal to maintain the sorted list of current changes for each $$$i$$$ using a priorityqueue/set.
one stupid bug made me submit WA on E if my solution is correct I'll throw myself from the window
I just corrected my code for both E and F less than 5 minutes from the end of the contest... I think :(
Go ahead, don't hesitate.
At least you would stop crying in the comments.
nah it's probably wrong I won't suicide unluckily for you
check it after the testing
u can do it now
I did it's WA it seemed correct to me Idk why it's wrong but I'm not that good to solve E so it's not a surprise
I got an idea for E : Was trying to make all k numbers as close as possible to give the minimum sum of squares. This follows directly from the well known QM>=AM>=GM>=HM inequalities.
Take QM>=AM Here QM is sqrt((L1^2 + L2^2 + ...... + LK^2)/K) WHERE Li is the length of carrot we give to ith rabbit.
Also AM is = (L1+L2+L3+....LK)/K.
Now L1+L2+.......+LK is equal to sum of lengths of all carrots.
From here we can see the minimum value is [(sum of all carrots)/k].
I was trying to implement a similiar approach on these lines but got WA on pretest 4 what am I missing ? Also I saw Errichto solve it in the first 15 minutes after (in addition to solving A,B,C obviously) and knew it was some clever problem.
We cannot combine the lengths of 2 carrots.. hence i guess your approach is wrong.
CASE:
4 4
1 1 1 9
The answer is 84
but you will print 36
which is wrong. I hope i have not read the question wrong xD
https://www.youtube.com/watch?v=cYL4Nh0-vwA https://www.youtube.com/watch?v=g22-5e5xAGA Video Editorial Other videos are in process
Lol, F is a "segment-tree-beats" problem. https://codeforces.me/blog/entry/57319
F has linear time solution. We relaxed it to logarithmic due to tester feedback.
Actually, if I remember correctly, errorgorn discovered segment tree beats solution quite early on, and we spent some time trying to kill it.
In fact, majority FSTs were caused by testdata that was meant to kill segment tree beats (sorry!)
My solution works (982ms), so I enjoyed the contest :)
Even $$$O(n^{\frac32})$$$ works! On worst case locally it works 0.2s for me, on systests it worked in 62ms ;)
I did a O($$$n^{\frac{3}{2}}$$$) solution but it did not pass test 48 :/ can you share your submission please?
Mine is pretty lightweight. https://codeforces.me/contest/1428/submission/95782858
I add characters one by one and compute contribution of all substrings ending at each character. When doing that I am interested in intervals of ones of growing lengths when looking from (current) end to beginning. There can be at most $$$O(\sqrt{n})$$$ of them, so I can iterate over all of them. This solution can be easily changed into linear, but it was easier to leave it as it is and it was fast enough.
Thanks!
In fact, you can set them to 0 using brute force.
It's also a $$$O(n \log n)$$$ solution, but i don't know if it will FST.
Well, it get Accepted.
https://codeforces.me/contest/1428/submission/95778097
I solved F with normal segment tree though. The idea is to iterate l from high to low and maintain the lowest r such that f(l,r)>=k for each k.
Submission: 95806181
My solution was O(n)
I spent most of my time trying to solve D. I thought my construction was perfect, however, the judge didn't think so. T_T
Hey, is there anyway to solve Problem 'E' using Binary Search ? I tried to solve 'E' using Binary Search, but could not pass pretest 3 link to my code : https://codeforces.me/contest/1428/submission/95803093
Didn't you forget to call
fans.clear()
?And I think it's just a wrong solution.
I passed pretests for Problem C. But forgot to lock it. Does that count?
It's not necessary to lock problems if you don't want to hack somebody.
Thanks!
fastest editorial I've ever seen
we've had fast editorials in most recent contests. It's a great improvement for codeforces i think!
I wish i could know what is the test case 4 of problem E....
Exactly...can you have a look at my logic and submission ? https://codeforces.me/blog/entry/83730?#comment-710946
4 4 1 1 1 9 will give WA in your code...but my submission gives right value for that too
I am so sad that my solution to problem D was wrong just because the grid numbering started from top. Couldn't change it as it was in last minutes of the contest.
For E is there a fault in logic if I try to binary search for the max height of the carrot such that the total number of carrots is K. then evenly divide the carrot heights and find the answer??
Yes. Consider the case where you cannot actually evenly divide things, for eg
4 5 100 100 10 1
AAHH wow.. Thanks a lot mateeee :D
Yes, the optimum set of lengths might not be the one with the minimum maximum length. Consider the case n = 2 k = 5 and initial lengths 235683 and 675850 (sorry for the big numbers).
The optimum lengths are 235683, 168962, 168962, 168963, 168963.
However it is possible to get to 117842, 117841, 225284, 225283, 225283. And the maximum value of this sequence is smaller than the optimum one.
Yes totally makes sense.. I know the other solution using priority_queue (didn't click during contest tho) but i couldn't find why this wouldn't work... bad dayyyy.. But good round!! Thanks for the help!! :D
Sample test cases in E were literally useless
I think the samples were fine. They should just be there to make sure that you understand the problem properly. Creating your own nontrivial samples to test on and see if your algorithm works is something that's important and should be done by the contestant.
https://www.youtube.com/watch?v=g22-5e5xAGA
Watch Video Editorial of all problems
Also do watch , cp experiences of IIT Madras students
https://www.youtube.com/watch?v=8n12sCm0VUI
Great round!!! Fun Fun Fun!
P.S. Problem D 122+ system tests? O_o
https://www.youtube.com/watch?v=VI5bL7Csc7w
Video Editorial of all Problems
Thanks for the contest. :)
I really liked problem D!
errorgorn, will there be a list of t-shirt recipients?
i have no idea how the ppl getting shirts are selected
When your last attempt of saving your rating in last 10 seconds of contest got rejected by a semicolon
(It got accepted after fixing the semicolon)
Sad life :(
Was log^2 with segtree intended to pass in F? I got TLE on recursive version and accepted (<500ms) on iterative one. If log^2 complexity can easily pass why not set the limit to 4s?
where we can know who is winner ?
The most important question for many of the CF users who gave round today. xd
As a human, I'm going to die without becoming a Grandmaster :"
Nooo I'm not. Yayy
Congrats!
Enjoyed This Round clear problems statements !!
Here's my solution to H:
Firstly for each ring choose a random number from $$$[-20, 20]$$$ and move it by such shift to make sure that nothing very bad will happen.
Now consider the rings in random order. Let's take some ring $$$i$$$. Move it clockwise and stop and the moment when the result decreases for the first time. After this, shift this ring counter-clockwise by one.
After such a phase all arcs are grouped. By grouped I mean that every two arcs either share their exact position or don't touch each other at all and the size of each group is at least $$$2$$$.
The number of groups is ofc $$$\leq 50$$$, but it'll be a bit less in average. Now it'd be nice to discover how the indexes are grouped. To do this, initialize a set of groups, initialy empty and consider all the rings (again in random order). When we consider ring $$$i$$$, then move it by one clockwise. Nextly, loop over all the existing groups, and for each of them take its representative and move it once clockwise and once counter-clockwise. It's possible to know to which group ring $$$i$$$ belongs (or if it's in a new group). Then shift ring $$$i$$$ counter-clockwise by one to fix the situation.
So we know how the rings are grouped, but we need to know their order (and distances). Take one group and it's representative. Let's move it clockwise and stop when it bumps into another group. In this moment iterate over all other groups, for each of them take one representative, move it once counter-clockwise and once clockwise. It's possible to know if we bumped into this group (and ofc we know the travelled distance). Then move the ring back to its group.
After this we know everything.
fun fact: When code forces ran your solution during contests on systests, it gave "runtime error on test case 21" from too many queries.
In the end, it ended with 14848/15000 queries, what a clutch rng!
Why does the random shifting in the first step stop very bad things from happening WHP?
Imagine having the results $$$0$$$ at the beginning. Wouldn't we need $$$O(n \cdot m \cdot \log(n))$$$ moves to move the arcs to the groups (even with an optimal order)?
Not sure what you're asking. There's a one-parameter family of test cases of the form 0 (k times), 20 (k times), 40 (k times), ..., 20*ceil(100/k) (100%k times), and variants with distributions more skewed to the one end than the other.
You're randomising the order in your "move clockwise until gap" phase to avoid a quadratic blowup when k is small. When k=1, for instance, each iteration of "move clockwise until gap" creates a new gap, giving you an expected O(mn log(mn)) moves or so. When k >= 2, though, the new gaps take a while to form. In particular, the first sqrt(n)-ish iterations won't create a new gap.
Numerically, when k=2, I get a mean of 13060 steps and a standard deviation of 2500 steps just in the "move clockwise until gap" phase.
I can imagine a tight arithmetic progression being bad too. Intuitively, random jitter shouldn't change the nature of an arithmetic progression instance too much. Why does the initial randomisation step help with this dynamic?
I didn't say that it's a correct solution.
How much time does it take to update ratings?
Congratulations to prize winners!
Bluetooth speaker:
Bumbag:
Power Bank:
Thermos Mugs & Raiffeisenbank t-shirt:
Note that it is possible that some cheaters will be removed, but we will not recompute prizes unless one of them is a cheater.
Congratulations to the Lucky 50!
THANK YOU!!
Thanks for the contest! Can I request a power bank instead of a bumbag? :)
I'll check if it's possible.
Damn it feels good when your friend is in the list...
My rating has dropped by 100, but I won the T-shirt and Thermos! Should I be pleased? Or should I be sad?
Lol
When will we receive the gifts?
In a week or two you will be contacted by System or someone with bold black handle to check your address and they'll provide you further info.
okay,thank you!!
I didn't receive my t-shirt yet. Will it take some more time to reach?
Nice Job ! =)))))))
Why does this get WA in E ?
4
3 3 2 1
6
1 1
2 2
3 3
2 3
3 4
1 4
Your output is
which would translate to
5 3 2 1
instead of your input.got it, thank you
Does someone know how to download full test cases for a problem? My C attempt gave WA at the second test set's case #92, but couldn't see what it is.
nope..no way bro
Ah that's sad.
Essentially I tried to find a counterexample for my WA attempt, in which I consider the input string as "(some_number_of_B)(start with A and end with B)(some_number_of_A)". The middle part (start with A and end with B) is then reduced to contain only As or Bs, so the string is further reduced to (some_number_of_B)(some_number_of_A). I know the editorial solution is correct and simpler but struggled to find the counterexample for the idea above.
Any suggestion is really appreciated!
The contest was very well prepared and I actually had fun competing, so thanks to the organizer. But I have a doubt.
I am not sure this kind of contests should be rated for "strong contestants" (let's say IGM). Problems E and F were quite standard, and also G was just a variation on the knapsack-problem (it was not easy to understand the details of the associated knapsack-problem, but it was pretty clear that it shall be stated as a knapsack). I think this kind of problems are a bit too standard to play a role in the rating of high-rated contestants. Once again, I am not saying that this contest was not good, I am sure it was interesting and pleasant for 99,9% of the participants and therefore it was a very good contest (clear statements, nice problems, good pretests and good tests... high-quality overall). I am wondering whether it would be better to make it clear in some way (before the round) how original the problems are (adjusting accordingly the rating range).
I am implicitly suggesting that a system similar to the AtCoder one (only AGCs are rated for strong contestants) might be beneficial also for Codeforces. In general, I feel that what I consider interesting is quite different from what a contestant with rating 1910 considers interesting (and I guess that this difference is even bigger for contestants stronger than me) so it is strange that we have exactly the same set of rated contests. The main reason is that there are many nice problems (for example E and F of this round) that are incredibly cool for a candidate master but quite standard for an IGM (in the same way that sorting an array in $$$O(n\log(n))$$$ is incredibly cool for a novice, but standard for anyone who knows a bit of stuff).
I would like to hear the opinion of some strong contestants... maybe I am the only one with this opinion (and maybe noone will ever read this late comment).
Hi, thanks for the feedback!
I'm not exactly a strong contestant but I do agree largely with your comments. I'd say the problems E and F are kind of classic at higher levels, and that the contest is easier than what you'd expect from a normal div1.
About problem G, I didn't think that it was that standard when I set it. That's probably because I found the observation about 0,3,6,9 the hardest part of the question. So while the knapsack part is classic, I found the hardest part of the question the ad hoc observation at the start. Also interestingly no tester solved G during contest time (although some almost solved it).
About differentiating "original" and "classic" contests, I think it'll be a good idea. However, I'm not sure about the feasibility since usually problem setters don't have much flexibility in choosing the type of problems since we don't have enough good problems to play around with the style of the contest.
An idea is to look at the problems after they're proposed and then decide which category it falls under? Random thought I had: what if combined rounds are more of the classic type and have a rating cap. Rounds which are div1 + div2 (5/6 problems each) be more of the original type (at least for div1), and possibly harder now.
I agree that problem G was less standard than E, F; I mentioned it because if G had been very original it would have made the whole contest original. Regarding "no tester solved G during contest time". I am not claiming that G is easy, in fact it is not. But originality and difficulty are almost orthogonal properties.
Regarding your proposals and comments on how to solve the issue... I simply have no opinion. I don't know whether combined rounds should be capped, or if separated rounds should be capped (or if the capping should be independent of the type of round) or if the threshold for div1 should be raised.
Is anybody able to access the editorial right now? It was available an hour ago but now when I click on the link to editorial, it says "You are not allowed to view the requested page" and redirects me to the last opened page on codeforces. Please confirm if you are facing the same problem.
Upd: Fixed Now, Thanks
it wasnt public for some reason. shld be fixed now!
It is not accessible again, can you please check?
Please make the editoriala public.
It is still not accessible.
errorgorn I guess there is a glitch with the editorial, It says the editorial is not accessable. Please check once
It is still not accessible.
I'd highly recommend watching this tutorial https://www.twitch.tv/errichto by Errichto until they make the tutorial accessible.
Help wanted :
For problem E, I binary searched on the length and found out the maximum possible length in which the carrots may be divided. It'll be great if someone can explain me why its wrong.
https://codeforces.me/contest/1428/submission/95793574
Who's this cutie pie muah muah
Consider splitting 100 into three slices.
When you take a cut of size 33, you split it into 3 '33' length cuts and 1 length '1' cut.
33 33 33 1, and hence you say this is suboptimal and you proceed to 34, which results in this splitting: 34 34 32 which you falsely claim optimal. (Your answer will print sigma square of this array)
However, you could have split it as 33 33 34, which is a case your code doesn't test. (Turns out this is the most optimal split)
i.e it is not optimal to always take arr[i]/mid portions along with arr[i]%mid extra. sometimes merging arr[i]%mid with another is more optimal.
Makes sense, Thanks !
..