By errorgorn, 6 days ago,

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:

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

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.

FILL OUT FORM →

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

E: errichto

F: fmota

Top 5

Congratulations to everyone!

• +1237

 » 6 days ago, # |   +1154 As a tester, make sure to stay hydrated!
•  » » 6 days ago, # ^ |   +520 if you get more upvotes than blog i will swallow a battery
•  » » » 6 days ago, # ^ | ← Rev. 2 →   +199 go swallow your battery
•  » » » » 6 days ago, # ^ | ← Rev. 2 →   +19 Let poor errorgorn think that at least he's got a chance
•  » » » » 5 days ago, # ^ |   +42 errorgorn: "NO" !)
•  » » » 6 days ago, # ^ |   +163 Would you like recipes?
•  » » » 6 days ago, # ^ | ← Rev. 2 →   +102 I'll press charges.
•  » » » » 6 days ago, # ^ |   +54 Please, some things are not good to joke about
•  » » » » » 4 days ago, # ^ |   +21 The press charges is an involuntary good joke though. Because battery.
•  » » » » » » 4 days ago, # ^ |   0 Check the previous edition of the comment.
•  » » » » » » » 4 days ago, # ^ |   0 I'm aware, not a good topic to joke about haphazardly. Just saying there was a decent involuntary joke in there.
•  » » » 6 days ago, # ^ | ← Rev. 3 →   +33 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
•  » » » » 5 days ago, # ^ | ← Rev. 3 →   +2 Well I upvoted the blog because of his comment. Haha no t didn't. I expected atleast one upvote from errorgorn
•  » » » » » 5 days ago, # ^ |   +29 Did you also downvote Monogon's comment?
•  » » » 6 days ago, # ^ | ← Rev. 2 →   +110 Videos or it didn't happen(Please don't actually swallow batteries)
•  » » » 6 days ago, # ^ |   +197 You can swallow potato battery, lemon battery, etc
•  » » » » 6 days ago, # ^ | ← Rev. 2 →   +10 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.
•  » » » » 5 days ago, # ^ |   0 Also apple battery, grape battery can be the better choice
•  » » » » 4 days ago, # ^ |   0 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.
•  » » » 6 days ago, # ^ |   +13 Swallowing batteries is pretty dangerous, right? (like what happens then it's in your stomach?)
•  » » » » 6 days ago, # ^ |   +116 You must be very fun to have around at parties.
•  » » » 6 days ago, # ^ |   +75 I believe Monogon asked you to comment. Truly wonderful the mind of monogon is. The way you harvest upvotes is simply brilliant.
•  » » » 6 days ago, # ^ |   +8 monogon is a record holder, and I think you said so because you are a master at swallowing batteriesGL
•  » » » 6 days ago, # ^ |   -23 Actually, fruit can be used as batteries.
•  » » » » 5 days ago, # ^ |   -12 This is awesome.
•  » » » 5 days ago, # ^ |   +77
•  » » » 5 days ago, # ^ |   -6 I believe that the real purpose of errorgorn's comment is to help Monogon hit 200 contribution.
•  » » 6 days ago, # ^ |   +33 Monogon's Masterplan to hit 200 contribution with just one comment
 » 6 days ago, # |   +90 Absolutely strange prizes distribution, but ok. Waiting for nice contest!
 » 6 days ago, # | ← Rev. 2 →   -37 score distribution?
 » 6 days ago, # |   +16 All the author are from Singapore zoo. Why zoo?
•  » » 6 days ago, # ^ | ← Rev. 2 →   +15 Will be answered in task description (implicitly or explicitly)Don't worry though, statements will still (hopefully) be short.
•  » » 6 days ago, # ^ |   +80 Firstly finish your drink then we would talk about it.
•  » » » 4 days ago, # ^ |   -18 Please don't upvote the above comment. It is aesthetically pleasing as of now.
•  » » » » 4 days ago, # ^ |   0 Okay
•  » » » » » 4 days ago, # ^ |   +5 It was 69 when I saw it :(People just don't listen.
 » 6 days ago, # |   -30 But unfortunately it will reward us a big negative delta :'(
 » 6 days ago, # | ← Rev. 2 →   -28 Ok it's not funny my bad
•  » » 6 days ago, # ^ | ← Rev. 2 →   -28 .
 » 6 days ago, # |   -26 Because of prize there might be a DDOS. I Noticed many times, whenever there are prizes in CF round there happened a DDOS for sure.Hope things will be fine this time. :)Thank You
 » 6 days ago, # |   -21 I just want T-shirt
•  » » 6 days ago, # ^ |   +80 Amazon has some.
•  » » » 6 days ago, # ^ |   -24 wow... so much informative, thank u
 » 6 days ago, # | ← Rev. 4 →   +349 Guys, list of participants looks weird.. There are lots of unrated users with the strange handles..
•  » » 6 days ago, # ^ |   +59 Very interesting, there is probably just one person behind them all.
•  » » 6 days ago, # ^ |   +73 Should tag MikeMirzayanov, I don't think setters can do much about it.
•  » » » 6 days ago, # ^ | ← Rev. 3 →   +146 What if they change the rules a little bit so only rated participant can receive the prizes?any many more
•  » » » » 6 days ago, # ^ |   +31 Yeah, rules should be changed.Prizes should be only for rated participant.
•  » » » » » 5 days ago, # ^ |   0 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
•  » » 6 days ago, # ^ |   +7 If all these accounts are created by a single person, I wonder how can someone remember so ugly handle names!!
•  » » » 6 days ago, # ^ |   +5 His browser will remember it with password.
•  » » » 3 days ago, # ^ |   +3 Microsoft UI Automation can certainly do some nasty stuff.
•  » » 5 days ago, # ^ | ← Rev. 2 →   +7 Looks like now these accounts have disappeared from the registrants list.
•  » » 5 days ago, # ^ | ← Rev. 2 →   0 what if new users will not write this round? (I think everyone wants T-shirts from legendary codeforces.)
•  » » 4 days ago, # ^ |   +53 Fixed it.
 » 6 days ago, # |   +3 None of the japanese coders here have noticed the Arigato pun in the statement :(
•  » » 6 days ago, # ^ |   +122 I think they're trying their hardest to forget it :)
 » 6 days ago, # |   +7 CF has really given us a variety of rounds this year :oWe'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.
•  » » 6 days ago, # ^ |   +14 Also this year was the first Cuban round.
•  » » » 5 days ago, # ^ |   +21 And the first my little pony round...
•  » » » » 5 days ago, # ^ |   +39
•  » » » 5 days ago, # ^ |   +28 Also there was my round this year
•  » » » » 5 days ago, # ^ |   +4 next round when
•  » » » » » 4 days ago, # ^ |   +18 The proposal is already in queue
 » 6 days ago, # | ← Rev. 2 →   0 Nice timing for Indians, will have dinner on time which is unusual...
 » 6 days ago, # |   +3 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).
 » 6 days ago, # |   -12 Note that the start time is unusual.
 » 6 days ago, # |   0 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?
•  » » 6 days ago, # ^ |   +13 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.
 » 6 days ago, # |   +3 It clashes with COCI can you delay the contest?
•  » » 6 days ago, # ^ |   +194 These weekends: Codeforces Raif Round 1, SRM, COCI, AGC, Kickstart, CF Div2, Cook Off. Pls tell how to fit everything without intersections.
•  » » » 5 days ago, # ^ |   +180 Sounds like a problem statementThere 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...
•  » » » 5 days ago, # ^ |   +5 I think you missed today's ABC xD
•  » » » » 4 days ago, # ^ |   0 Which was shit tbh :(
 » 6 days ago, # |   +92 Just like last week, I will go live just after the round ends to discuss my solutions https://www.twitch.tv/errichtoAlso, that's the ugliest bluetooth speaker I've ever seen.
•  » » 6 days ago, # ^ |   +45 Is that an excuse for not coming in top 3?
•  » » » 6 days ago, # ^ |   +149 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.
•  » » » » 5 days ago, # ^ |   +12 Try not solving a problem. Who knows you might get the random one :D
•  » » » » 4 days ago, # ^ |   +9 Seems like, you'll have to do with the unnecessary power bank now :p
•  » » » » 4 days ago, # ^ |   0 You should always follow "True story" with "Yeah yeah"
•  » » » » 4 days ago, # ^ |   0 Wait I thought you didn't want any unnecessary stuff
•  » » 4 days ago, # ^ |   +4 UPD: going live now!
 » 5 days ago, # |   +21 Google Translate told me that swag means goods that be stolen. How funny it is :)
 » 5 days ago, # |   0 Hope this contest will be a good contest UwU
 » 5 days ago, # |   +48 Hey, I'm flattered! Can't skip this one now
 » 5 days ago, # |   +64 [
 » 5 days ago, # |   -117 Is contest rated ?
•  » » 5 days ago, # ^ |   +40 It will be a combined rated round for both divisions.
•  » » 5 days ago, # ^ |   -17 Not rated for you, rated for others.
•  » » 5 days ago, # ^ |   -6 It's a common downvoted question these days..
 » 5 days ago, # |   -86 Let's start an errorgorn orz chain! errorgorn orz
 » 5 days ago, # |   +114
•  » » 5 days ago, # ^ |   +6 Codeforces ain't perfect, but when you compare it to other sites like codechef, it's considerably better imo.
•  » » » 3 days ago, # ^ |   0 Then tell a platform better than codeforces.
•  » » 5 days ago, # ^ |   +18 Is this supposed to mean that Mike does a bad job?
•  » » » 5 days ago, # ^ |   +7 I suppose not
•  » » » 5 days ago, # ^ |   0 Do you believe world's best boss was bad at his work? That's offensive.
•  » » » » 5 days ago, # ^ |   +3 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
•  » » » 4 days ago, # ^ |   +14 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.
•  » » » » 4 days ago, # ^ |   +58 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.
 » 5 days ago, # | ← Rev. 3 →   -39 nice
 » 5 days ago, # |   0 Are there remote jobs at Raiffeisenbank?
•  » » 5 days ago, # ^ |   -18 There is a form to join them at the end of the blog
 » 5 days ago, # | ← Rev. 2 →   -21 Ok. Finally, I have a chance to get a prize. Although it depends o my luck.
 » 5 days ago, # |   -18 Will try for the random 50 as a noob :D
•  » » 4 days ago, # ^ |   0 I think they want to attract to the new comers.
 » 5 days ago, # |   -26 Another global round!!
 » 5 days ago, # |   -32 I hope to solve all of problems
 » 5 days ago, # | ← Rev. 2 →   -25 [Deleted]
•  » » 5 days ago, # ^ |   +31 answered in annoucement (implictly or explictly)
•  » » » 5 days ago, # ^ |   +61 Sorry,that was sent by my classmate. I owe you an apology for not looking after this matter.
•  » » » » 4 days ago, # ^ |   +3 Tell us his/her handle...
 » 4 days ago, # |   +6 I remember I read short statements XD
 » 4 days ago, # |   0 How to hack a problem i locked?
•  » » 4 days ago, # ^ |   0 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.
•  » » » 4 days ago, # ^ |   +1 But why submissions is unclickable?
•  » » » » 4 days ago, # ^ |   +1 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
•  » » 4 days ago, # ^ |   0 All dont works,ok?
 » 4 days ago, # |   0 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
•  » » 4 days ago, # ^ |   +13 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.
 » 4 days ago, # |   0 I am eagerly waiting to see the test case no:2 of problem "B".
•  » » 4 days ago, # ^ |   0 me too
 » 4 days ago, # |   +3 Did I choose wrong problem?
 » 4 days ago, # |   0 Good contest!!Amazing problem D!
•  » » 4 days ago, # ^ |   +32 What was amazing about D? Seemed like mindless implementation to me. Unless there is some elegant way of solving it?
•  » » » 4 days ago, # ^ |   -26 Of course there is a elegant way! Code/* { ###################### # Author # # Gary # # 2020 # ###################### */ //#pragma GCC target ("avx2") //#pragma GCC optimization ("O3") //#pragma GCC optimization ("unroll-loops") #pragma GCC optimize(2) #include #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a mp; /*} */ int n; bool cmp(mp A,mp B){ return A.SEC>n; rb(i,1,n) scanf("%d",&a[i]); vector v; int row=n; stack pos; vector pos2; rl(i,n,1){ if(a[i]==1){ pos.push(II(row,i)); v.PB(II(row--,i)); } } rb(i,1,n){ if(a[i]==2){ while(pos.size()&&pos.top().SEC
•  » » » » 4 days ago, # ^ |   +9 How can you call this elegant?
 » 4 days ago, # |   0 What is test 4 in D ??
•  » » 4 days ago, # ^ |   +6 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)
•  » » » 4 days ago, # ^ |   0 my code using namespace std; typedef long long ll; typedef long double ld; typedef pair pll; #define all(x) (x).begin(),(x).end() #define X first #define Y second #define sep ' ' #define endl '\n' #define debug(x) cerr << #x << ": " << x << endl; ll poww(ll a, ll b, ll md) { return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md)); } const ll MAXN = 1e6 + 10; const ll INF = 8e18; const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9; set O, T2, T3; set T2t; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n; cin >> n; vector v3; for (int i = 1; i <= n; i++) { ll x; cin >> x; if (x == 1) O.insert(i); if (x == 2) T2.insert(i); if (x == 3) T3.insert(i), v3.push_back(i); } vector ans; ll r = n; for (ll e : T2) { if (O.lower_bound(e) == O.end()) return cout << -1 << endl, 0; else { auto it = O.lower_bound(e); ans.push_back({r, e}); ans.push_back({r, *it}); O.erase(it); } r--; } reverse(all(v3)); for (ll e : v3) { if (T3.upper_bound(e) == T3.end()) { if (O.lower_bound(e) != O.end()) { auto it = O.lower_bound(e); ans.push_back({r - 1, e}); ans.push_back({r - 1, *it}); ans.push_back({r, *it}); r -= 2; O.erase(it); } else return cout << -1 << endl, 0; } else { auto it = T3.upper_bound(e); ans.push_back({r, e}); ans.push_back({r, *it}); r--; T3.erase(it); } } for (ll e : O) ans.push_back({r, e}), r--; cout << ans.size() << endl; for (pll e : ans) cout << e.X << sep << e.Y << endl; return 0; } also, I think my code isn't clear enough to read :) so this is my solution spoiler1- I tried to make the columns with number 2 ok by matching them with a column with number one in front of it2- we can't do anything with the remaining columns with number 2 so if anything was remaining from them, there is no answer3- 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 it5- we can easily make the columns with number 1 ok now
•  » » » » 4 days ago, # ^ |   +7 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.
•  » » » » 4 days ago, # ^ |   +3 You can match a 3 with a 2.
•  » » 4 days ago, # ^ |   0 probably33 2 1
 » 4 days ago, # |   0 what the fuck is pretest 3 of E
•  » » 4 days ago, # ^ |   0 wtf is pretest 4 of E?
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 try:2 49 4
•  » » » 4 days ago, # ^ |   0 43?
•  » » » 4 days ago, # ^ |   0 it should be 45, right? 4, 9 -> 4, 4, 5 -> 4, 4, 2, 3
•  » » » » 4 days ago, # ^ |   0 but we can do better by 4 9 -> 4 3 3 3. Aren't we?
•  » » » » 4 days ago, # ^ |   0 Nah 4,9 -> 4,3,3,3 so 43
 » 4 days ago, # |   0 How to solve G?
 » 4 days ago, # |   0 How to do E?
•  » » 4 days ago, # ^ | ← Rev. 2 →   +3 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
 » 4 days ago, # |   +1 how to do b?
•  » » 4 days ago, # ^ |   0 Let's first iterate over the string and check if we have any cw or acw paths. Now, everytime we encounter an off path, we can mark it as a good path. If we encounter a cw path, we need to make sure that there are no other acw 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.
 » 4 days ago, # |   -7 Isn't E just about always taking the maximum number m and separating it into p = m / 2 and q = m - p for all maximums, which can be implemented by priority queue? If not, could someone explain why?
•  » » 4 days ago, # ^ |   +12 1 3 8 you way : 4 2 2 the better answer : 3 3 2
•  » » » 4 days ago, # ^ | ← Rev. 2 →   0 Hi my logic gives correct answer for this case...but i got WA on test 4. Submission//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> n >> k; vector a(n); ll s=0; for(i=0;i> a[i]; s+=a[i]; } ll x = s/k; ll rem = s%k; vector v(k,0); for(i=0;i
•  » » » » 4 days ago, # ^ |   +1 n = 2, k = 2, array = {1, 9}, your answer : 50, the real answer 82.
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 4 82 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)
•  » » » 4 days ago, # ^ |   0 Hi my logic gives correct answer for this test case but WA on pretest 4. My code and logic : https://codeforces.com/blog/entry/83730?#comment-710946
•  » » 4 days ago, # ^ |   +8 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]$.
•  » » » 4 days ago, # ^ |   0 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.
 » 4 days ago, # |   +1 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?-
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 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.
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 Hi i was following a similiar approach can you have a look at my comment just below? https://codeforces.com/blog/entry/83730?#comment-710946
 » 4 days ago, # |   -12 one stupid bug made me submit WA on E if my solution is correct I'll throw myself from the window
•  » » 4 days ago, # ^ |   +13 I just corrected my code for both E and F less than 5 minutes from the end of the contest... I think :(
•  » » 4 days ago, # ^ |   +5 Go ahead, don't hesitate. At least you would stop crying in the comments.
•  » » » 4 days ago, # ^ |   -11 nah it's probably wrong I won't suicide unluckily for you
•  » » » » 4 days ago, # ^ |   +11 check it after the testing
•  » » » » 4 days ago, # ^ |   +8 u can do it now
•  » » » » » 4 days ago, # ^ |   0 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
 » 4 days ago, # |   0 So,fast tutorial!!!Thank you.
 » 4 days ago, # | ← Rev. 2 →   0 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. My submission//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> n >> k; vector a(n); ll s=0; for(i=0;i> a[i]; s+=a[i]; } ll x = s/k; ll rem = s%k; vector v(k,0); for(i=0;i
•  » » 4 days ago, # ^ |   0 We cannot combine the lengths of 2 carrots.. hence i guess your approach is wrong.CASE:4 41 1 1 9The answer is 84but you will print 36which is wrong. I hope i have not read the question wrong xD
•  » » » 4 days ago, # ^ |   0 Oh damn..I see...you right we cant combine...I knew we cant combine but still combined them idk.
 » 4 days ago, # | ← Rev. 2 →   0 https://www.youtube.com/watch?v=cYL4Nh0-vwA https://www.youtube.com/watch?v=g22-5e5xAGA Video Editorial Other videos are in process
 » 4 days ago, # | ← Rev. 2 →   +45 Lol, F is a "segment-tree-beats" problem. https://codeforces.com/blog/entry/57319
•  » » 4 days ago, # ^ | ← Rev. 2 →   +43 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.
•  » » » 4 days ago, # ^ |   +19 In fact, majority FSTs were caused by testdata that was meant to kill segment tree beats (sorry!)
•  » » » » 4 days ago, # ^ | ← Rev. 2 →   +6 My solution works (982ms), so I enjoyed the contest :)
•  » » » 4 days ago, # ^ |   +34 Even $O(n^{\frac32})$ works! On worst case locally it works 0.2s for me, on systests it worked in 62ms ;)
•  » » » » 4 days ago, # ^ |   0 I did a O($n^{\frac{3}{2}}$) solution but it did not pass test 48 :/ can you share your submission please?
•  » » » » » 4 days ago, # ^ |   0 Mine is pretty lightweight. https://codeforces.com/contest/1428/submission/95782858I 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.
•  » » » » » » 4 days ago, # ^ |   0 Thanks!
•  » » 4 days ago, # ^ |   0 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.
•  » » » 4 days ago, # ^ |   +8 Well, it get Accepted.https://codeforces.com/contest/1428/submission/95778097
•  » » 4 days ago, # ^ |   0 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
•  » » 4 days ago, # ^ |   0 My solution was O(n)
 » 4 days ago, # | ← Rev. 4 →   0 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
 » 4 days ago, # |   -8 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.com/contest/1428/submission/95803093
•  » » 4 days ago, # ^ |   0 Didn't you forget to call fans.clear()?And I think it's just a wrong solution.
 » 4 days ago, # |   +10 I passed pretests for Problem C. But forgot to lock it. Does that count?
•  » » 4 days ago, # ^ |   +19 It's not necessary to lock problems if you don't want to hack somebody.
•  » » » 4 days ago, # ^ |   +10 Thanks!
 » 4 days ago, # |   -13 fastest editorial I've ever seen
•  » » 4 days ago, # ^ |   0 we've had fast editorials in most recent contests. It's a great improvement for codeforces i think!
 » 4 days ago, # |   0 I wish i could know what is the test case 4 of problem E....
•  » » 4 days ago, # ^ |   0 Exactly...can you have a look at my logic and submission ? https://codeforces.com/blog/entry/83730?#comment-710946
•  » » » 4 days ago, # ^ |   0 4 4 1 1 1 9 will give WA in your code...but my submission gives right value for that too
 » 4 days ago, # |   -10 It was a nice contest! Interesting Cool Problem Ststements!!!
 » 4 days ago, # |   +9 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.
 » 4 days ago, # |   0 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??
•  » » 4 days ago, # ^ |   0 Can you have a look at my submission and logic? https://codeforces.com/blog/entry/83730?#comment-710946
•  » » 4 days ago, # ^ |   +16 Yes. Consider the case where you cannot actually evenly divide things, for eg4 5 100 100 10 1
•  » » » 4 days ago, # ^ |   +11 AAHH wow.. Thanks a lot mateeee :D
•  » » 4 days ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 4 days ago, # ^ | ← Rev. 2 →   +8 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
 » 4 days ago, # |   +3 Sample test cases in E were literally useless
•  » » 4 days ago, # ^ |   +38 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.
 » 4 days ago, # | ← Rev. 3 →   0 https://www.youtube.com/watch?v=g22-5e5xAGAWatch Video Editorial of all problemsAlso do watch , cp experiences of IIT Madras studentshttps://www.youtube.com/watch?v=8n12sCm0VUI
 » 4 days ago, # |   0 Great round!!! Fun Fun Fun!P.S. Problem D 122+ system tests? O_o
 » 4 days ago, # |   -8 why kosaraju algorithm gave TLE on the 2nd question????????
 » 4 days ago, # |   0 wrong answer on pretest 2
 » 4 days ago, # |   -22 https://www.youtube.com/watch?v=VI5bL7Csc7wVideo Editorial of all Problems
 » 4 days ago, # |   +8 Thanks for the contest. :)I really liked problem D!
 » 4 days ago, # |   0 errorgorn, will there be a list of t-shirt recipients?
•  » » 4 days ago, # ^ |   +6 i have no idea how the ppl getting shirts are selected
 » 4 days ago, # |   +119 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)
•  » » 4 days ago, # ^ |   +10 Sad life :(
 » 4 days ago, # | ← Rev. 3 →   0 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?
 » 4 days ago, # |   0 where we can know who is winner ?
•  » » 4 days ago, # ^ |   +5 The most important question for many of the CF users who gave round today. xd
 » 4 days ago, # |   0 As a human, I'm going to die without becoming a Grandmaster :"
•  » » 4 days ago, # ^ |   -18 Nooo I'm not. Yayy
•  » » » 4 days ago, # ^ |   +10 Congrats!
 » 4 days ago, # |   +11 Enjoyed This Round clear problems statements !!
 » 4 days ago, # | ← Rev. 3 →   +61 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.
•  » » 4 days ago, # ^ |   +63 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!
•  » » 4 days ago, # ^ |   0 Why does the random shifting in the first step stop very bad things from happening WHP?
•  » » » 4 days ago, # ^ | ← Rev. 2 →   0 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)?
•  » » » » 4 days ago, # ^ |   +8 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?
•  » » » » » 4 days ago, # ^ |   +20 I didn't say that it's a correct solution.
 » 4 days ago, # |   +13 How much time does it take to update ratings?
•  » » 4 days ago, # ^ |   0 generally it take 3/4 hour in div1/2 contest... but in recent contest it's happening in short time. btw the rating has updated already.
»
4 days ago, # |
+79

Congratulations to prize winners!

Bluetooth speaker:

List place Contest Rank Name
2 1428 2 Um_nik
3 1428 3 kczno1

Bumbag:

List place Contest Rank Name
4 1428 4 ecnerwala
5 1428 5 littlelittlehorse
6 1428 6 300iq
7 1428 7 DmitryGrigorev
8 1428 8 ksun48
9 1428 9 neal
10 1428 10 maroonrk

Power Bank:

List place Contest Rank Name
11 1428 11 Benq
12 1428 12 Endagorion
13 1428 13 Errichto
14 1428 14 yosupo
15 1428 15 zeronumber
16 1428 16 Medeowex
18 1428 18 kefaa2
19 1428 19 gs18115
20 1428 20 tfg

Thermos Mugs & Raiffeisenbank t-shirt:

List place Contest Rank Name
57 1428 57 UnstoppableChillMachine
184 1428 184 Yousef_Salama
305 1428 305 LJC00118
526 1428 525 yuusanlondon
747 1428 746 reiracofage
804 1428 804 VivekUchiha
1126 1428 1126 siddhant1
1654 1428 1654 sh_mug
1841 1428 1838 sahilshelangia
1934 1428 1934 sojisan
1967 1428 1962 snowcubes
2107 1428 2105 kansal_2106
2625 1428 2625 Igorbunov
2762 1428 2757 sandeepkumar
2885 1428 2876 aniket.nsit.2000
3063 1428 3058 ab_dtu
3165 1428 3164 the_traveler_
3424 1428 3416 akash_garg
3735 1428 3732 gxy001
4225 1428 4224 rsgt24
4226 1428 4226 agarwala2512
4418 1428 4418 Joe_Goldberg
4532 1428 4532 hritik_456
4549 1428 4548 aky121
4761 1428 4760 suresh_babu
5010 1428 5010 joker2
5176 1428 5175 avinashrao
5241 1428 5240 sauraviiitp
5311 1428 5311 pako1609
5321 1428 5321 coder_rohit_r
5459 1428 5459 Vishwa_02
5589 1428 5586 evilbegin
5795 1428 5794 Mohamed_El-sayed
6020 1428 6018 Park_Min_Young
6866 1428 6866 KaoYanGou007
7055 1428 7055 Moaaz-Mahmoud
7104 1428 7104 youcef
7216 1428 7216 viven0525
7410 1428 7402 1600-1700
7644 1428 7595 brytnispiers
7861 1428 7861 B1GGersnow
7898 1428 7861 Palak_8840
8055 1428 8050 Naheed28
8131 1428 8112 biswa_990
8475 1428 8466 srinidhi21
8551 1428 8533 mr.saylander
8813 1428 8813 phoenix_1402
9351 1428 9340 Liniou

Note that it is possible that some cheaters will be removed, but we will not recompute prizes unless one of them is a cheater.

•  » » 4 days ago, # ^ |   +18 Congratulations to the Lucky 50!
•  » » » 4 days ago, # ^ |   0 THANK YOU!!
•  » » 4 days ago, # ^ |   +23 Thanks for the contest! Can I request a power bank instead of a bumbag? :)
•  » » » 4 days ago, # ^ |   +15 I'll check if it's possible.
•  » » 4 days ago, # ^ |   +11 Damn it feels good when your friend is in the list...
•  » » 4 days ago, # ^ |   +13 My rating has dropped by 100, but I won the T-shirt and Thermos! Should I be pleased? Or should I be sad?
•  » » 4 days ago, # ^ |   0 Lol
•  » » 3 days ago, # ^ |   0 Thank you.
•  » » 3 days ago, # ^ |   0 Thank You Sir!!
•  » » 3 days ago, # ^ |   0 When will we receive the gifts?
•  » » » 3 days ago, # ^ |   0 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.
•  » » » » 3 days ago, # ^ |   0 okay,thank you!!
 » 4 days ago, # |   0 Nice Job ! =)))))))
 » 4 days ago, # |   0 Why does this get WA in E ? Input43 3 2 1 Output61 12 23 32 33 41 4
•  » » 4 days ago, # ^ | ← Rev. 2 →   +5 Your output is X..X .XX. ..XX .... which would translate to 5 3 2 1 instead of your input.
•  » » » 4 days ago, # ^ |   0 got it, thank you
 » 4 days ago, # | ← Rev. 4 →   -16 nice contest
 » 4 days ago, # |   0 I thought for a long time the problem B was a strong coupling component :v
 » 4 days ago, # |   -8 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.
•  » » 4 days ago, # ^ |   0 nope..no way bro
•  » » » 4 days ago, # ^ | ← Rev. 2 →   0 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!
•  » » » » 4 days ago, # ^ |   0 if there is any 'A' before 'B' that is the only time you need to reduce 'A'. on your example you not need to reduce the last (some_number_of_A). Because that is after (some_number_of_B). You can easily check it by bruteforce.:)
•  » » » » 3 days ago, # ^ |   0 You can create a brute-force solution and Random test generate. Then you can try to give the same input for both and check their output.
 » 3 days ago, # |   +26 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).
•  » » 3 days ago, # ^ |   +20 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.
•  » » » 3 days ago, # ^ |   0 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.
 » 3 days ago, # | ← Rev. 2 →   +35 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
•  » » 3 days ago, # ^ |   +9 it wasnt public for some reason. shld be fixed now!
•  » » » 2 days ago, # ^ |   +45 It is not accessible again, can you please check?
•  » » » 2 days ago, # ^ |   +20 Please make the editoriala public.
•  » » 2 days ago, # ^ |   +22 It is still not accessible.
 » 2 days ago, # |   +34 errorgorn I guess there is a glitch with the editorial, It says the editorial is not accessable. Please check once
•  » » 2 days ago, # ^ |   +13 It is still not accessible.
•  » » » 2 days ago, # ^ |   0 I'd highly recommend watching this tutorial https://www.twitch.tv/errichto by errichto until they make the tutorial accessible.
 » 2 days ago, # |   0 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.com/contest/1428/submission/95793574
•  » » 2 days ago, # ^ |   -8 Who's this cutie pie muah muah
•  » » 2 days ago, # ^ |   0 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.
•  » » » 2 days ago, # ^ |   0 Makes sense, Thanks !
•  » » 36 hours ago, # ^ | ← Rev. 3 →   0 ..