By awoo, history, 14 months ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hello once again, Codeforces!

It’s been a week since we completed our Harbour.Space Scholarship Contest. It’s was an intense journey, but we are excited to share the results of the contest and take this time to give a word of appreciation to every participant.

One more big shout out to the authors and round coordinator who made this contest happen in a short period of time:

Thank you again for all your hard work.

Congratulations to all the winners and runner-ups who got the opportunity to go through the admissions process and who are eligible for a full scholarship.

1st-3rd Places: Ali.Kh, Yousef_Salama, antOntrygubX_y

4th-10th Places: sunyx, windazz, IMRED, Meijer, Prosto, kpw29, Huah2

11th-15th Places: dhruvsomani, adamant, Kaitokid, khiro, c8kbf

We are pleased to announce that we have reviewed all the winners and will make a final decision about additional scholarships soon. Stay tuned and keep an eye on your inbox!

Remember, to claim the scholarship you need to respond to the email sent 3-4 days ago. And just to make sure email addresses weren’t misspelt, we want to take this opportunity and ask Yousef_Salama, Huah2, adamant, c8kbf, Naseem17 to contact us via email (almaz.aubakirov@harbour.space) or directly on Codeforces platform (Harbour.Space)

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 SSRS_ 6 92
2 tourist 6 120
3 WZYYN 6 127
4 Heltion 6 131
5 Tlatoani 6 140

57 successful hacks and 612 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Geothermal 0:01
B tourist 0:03
C kaiboy 0:04
D dario2994 0:07
E tourist 0:11
F rainboy 0:30

UPD: Editorial is out

• +210

 » 14 months ago, # |   -105 i hope i can get top 10 in this contest
•  » » 14 months ago, # ^ | ← Rev. 2 →   +20 i hope i can get top 10000 in this contest
•  » » » 14 months ago, # ^ |   +40 Not achieving this goal is harder than achieving it.
•  » » » » 14 months ago, # ^ |   0 Not easy for new Learners.
•  » » » » 14 months ago, # ^ |   +5 Problem A did make it a lot easier though.
•  » » » » » 14 months ago, # ^ |   0 nope is do A every time i buy my data pack
•  » » » » 14 months ago, # ^ |   0 He was talking about 1000 , and misprinted it. Lol
 » 14 months ago, # |   +7 I hope that this contest will be as good as CF Round #735. And maybe even better
 » 14 months ago, # |   +5 Hope this educational round actually have balanced problems unlike the last edu round
•  » » 14 months ago, # ^ |   0 Agree Balance is always perfect )
 » 14 months ago, # |   +27 Please don't start hopeforces again
•  » » 14 months ago, # ^ |   +11 You hope no one hopes again.
 » 14 months ago, # | ← Rev. 2 →   +66 28/07 -> July Cook-Off 2021 29/07 -> Codeforces Round #735 30/07 -> Educational Codeforces Round 11231/07 -> July Lunchtime 202131/07 -> AtCoder Beginner Contest 21201/08 -> Leetcode Weekly Contest 25201/08 -> Codeforces Round 736Raining Contests
•  » » 14 months ago, # ^ |   0 Wow! This Weekends's gonna be really exciting!
•  » » 14 months ago, # ^ |   +9 Wow,seems like you are still living in June
•  » » » 14 months ago, # ^ |   0 My bad.Thanks :))
•  » » 14 months ago, # ^ |   +2 On 31 there is also ICPC practice contest
•  » » 14 months ago, # ^ |   +1 And my ratings are going to be washed out.
 » 14 months ago, # |   0 A chance for me to fix the damage caused by the previous contest :( Nice problems btw :)
 » 14 months ago, # | ← Rev. 2 →   +9 I hope I can break my unconditional love with FSTs in this round. :(
 » 14 months ago, # |   +3 Please get me out of this losing streak. I'm doubling in rating loss each time.
•  » » 14 months ago, # ^ |   0 You can see my rating graph so that you can get some motivation
•  » » 14 months ago, # ^ |   0 good luck to you.
 » 14 months ago, # |   -39 I think @Karry5307_AK_NOI2021 will AK this contest with his ssh because he's the best ssher.Just waiting for the result.Karry5307 & ssh forever!(just a joke)
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 What happenedKarry5307 used ssh to steal other people's code in NOI (Chinese Programming Competition) and got 100 points.
 » 14 months ago, # |   0 y would anyone waste their time going to some trash unaccredited university, beyond me tbh
 » 14 months ago, # |   0 Hoping for a good contest :)
 » 14 months ago, # |   0 hope i become pupil again
 » 14 months ago, # |   0 Good luck, guys!
 » 14 months ago, # |   +6 I hope, I won't become turquoise again ^^
•  » » 14 months ago, # ^ |   0 Same :)
 » 14 months ago, # |   +1 Good luck to everyone!
 » 14 months ago, # |   +7 My first Contest as Expert , will try my best today to move up more !!
 » 14 months ago, # |   +1 Hopefully this contest won't make you worry about your setters' safety.
 » 14 months ago, # |   0 It's time to move up.Good luck for everyone
 » 14 months ago, # |   +5 Hope that there won't be any Bitwise-operators tonight.
 » 14 months ago, # |   +15 I hope I will solve B in this contest
 » 14 months ago, # |   +21 MikeMirzayanov I think something is wrong with my registration. It shows me as a official participant. Can you please fix it? I don't want to lose master.
 » 14 months ago, # |   -11 Maybe there's sth wrong with Problem D.How can a string which length is 1 can be changed to an "beautiful" string ?
•  » » 14 months ago, # ^ |   +7 Because it is given that we have to consider only "palindrome of length greater than or equal to two".
 » 14 months ago, # |   +5 just realized why A is the hardest problem ..
 » 14 months ago, # |   -25 The announcement which came for C, should have come early. I was solving a different C, where Alice is looking for the maximum and then Bob goes with the minimum afterward.
•  » » 14 months ago, # ^ |   +39 No, you should have read the statement more carefully.
•  » » » 14 months ago, # ^ |   -10 Yeah, you are correct. But the announcement itself proves that the statement was unclear.
•  » » » » 14 months ago, # ^ |   +49 No,it proves there were more people like you who didn't read the statement properly and were bugging authors with queries.
 » 14 months ago, # |   +11 Solved D at 01:50, so happy! ^__^
•  » » 14 months ago, # ^ |   0 congratulations
 » 14 months ago, # |   +7 After giving yesterday's contest. This one feels so much better. Regained some confidence again. :)
•  » » 14 months ago, # ^ |   0 Not being able to do B yesterday was depressing tbh...
 » 14 months ago, # | ← Rev. 2 →   +1 When you solve A,C, and D but not B. Sigh...
 » 14 months ago, # |   +4 B had more cases than law courts!
•  » » 14 months ago, # ^ |   +3 upsolve it, there are at max 6 cases. for -1 for 0 other 4 for each direction R,L,U,D
•  » » 14 months ago, # ^ |   +7 Three cases: -1, can fit horizontally, can fit vertically.
•  » » » 14 months ago, # ^ |   0 Yeah i guess i complicated it a bit. I checked for both sides and found the minimum.
 » 14 months ago, # |   +20 In my opinion, C was much easier than A and B. Thanks.
 » 14 months ago, # |   +9 I think A,B is way more harder than C,D and E lol
 » 14 months ago, # |   +11 I took 47 minutes to solve problem B (+ penalty), but 9 minutes to solve problem C and 15 minutes to solve problem D....
•  » » 14 months ago, # ^ |   0 Solved B in when last 4 minutes were left . Solved C and D long ago. :((
 » 14 months ago, # |   +12 I'm so disappointed of myself Idk why my B solution is wrong :( :( I solved C easily I could have read D but I kept saying I will solve this BSubmission
•  » » 14 months ago, # ^ |   0 I might have missed it in your code but did you check x1 and y1 to the walls or the walls to x2 and y2?
•  » » » 14 months ago, # ^ |   0 nah I just realized my mistake I thought we place the second rectangle from (0,0) what a stupid understanding I did
 » 14 months ago, # |   -14 Mathforces. 4 wrong submissions for A :(
 » 14 months ago, # |   0 score distribution is same for all problems? i have solve only C and D today but ranking is same who slove only A and B.
•  » » 14 months ago, # ^ |   0 Its educational round, that's why !
•  » » » 14 months ago, # ^ |   0 How educational rounds are different from normal round?lazywitt
•  » » » » 14 months ago, # ^ |   0 They are by definition different, as in there is no semantic meaning in this difference. It's not that "oh this is educational so let's teach them how to treat all problems equally" or anything. It's just by definition. Educational and Div3 rounds follow ICPC style contest rules, where Div1, Div2 and most others follow point based score distribution rule where difficult problems are assigned higher points.
 » 14 months ago, # |   0 Nice contest, E is a very interesting problem.
•  » » 14 months ago, # ^ |   +3 how did you solve e? I tried doing a nested binary search on the minimum values to take and maximum values but it TLE'd.
•  » » » 14 months ago, # ^ |   0 I did that too initially, but binary search is actually not needed. Just use two-pointer, extend right bound until the whole interval is covered and then update the answer.
•  » » » » 14 months ago, # ^ |   0 ohh sick
•  » » » 14 months ago, # ^ |   0 How are using binary search here? After fixing the minimum value, we can do a binary search on max values that's fine. But how can you do a binary search on minimum value ... Then you will have to iterate linearly for minimum value?
•  » » » » 14 months ago, # ^ |   0 Depending on whether or not there are any valid max values(using a certain min value) I will choose to either lower or increase my min value. It sounds pretty dumb and it didn't pass either but if you are really curious you can read my code.
•  » » 14 months ago, # ^ |   +32 Is downvoting comments complimenting contests becoming a trend?
 » 14 months ago, # |   -28 Why was A and B (didn't read rest) so "heavily" math based compared to other general As and Bs? I'm surprised so many people got A, toughest A and B I've ever seen, also first time seeing both the starting two problems are math.. which is surprising considering most of the people can only do A and B (I'd expect something which has to more with programming than complete maths). IMO
•  » » 14 months ago, # ^ |   +9 Well, you can't have every A be "you have an array and you need to permutate through it and do and do x". Sometimes there has to be math involved, and let's be honest, it wasn't a lot.And "toughest A and B I've seen" seems comical when yesterday there was a B rated 1700.
•  » » 14 months ago, # ^ |   0 If this is your "toughest A and B", then 1. You haven't done many contests in CF. 2. You don't really know what is a tough problem and what is not.
 » 14 months ago, # | ← Rev. 3 →   -123 Unfair constraints for python in problem Dsame code for c++ https://codeforces.com/contest/1555/submission/124343239 got accepted butpython code got tle https://codeforces.com/contest/1555/submission/124338639Headquarters MikeMirzayanov, Round Coordinator BledDest, one of the authors Errichtoplease look into this.
•  » » 14 months ago, # ^ |   +159 1) We are not creators of Python. Go complain to them. I think that CF staff only cares about easy problems being solvable in slow languages.2) I have nothing to do with this problem. I was mentioned in the blog as an author of the previous round -_-
•  » » 14 months ago, # ^ | ← Rev. 2 →   +19 even though I am a newbie here in code forces or should I say in this whole cp genre .but i know that [1] you must not tag Authors and other GM unnecessarily in (unless you'r LGM YOURSELF). [2] you must wait for editorials to come out before asking too much question [3] be respectful. Nobody here's the homeroom teacher
•  » » » 14 months ago, # ^ |   -14 It's a valid concern. Python may have timed just around the given time limit. So asked organizers to see if time could have been higher for python based submissions. Codechef does it and so do many problems in codeforces have elevated time for problems like the one (https://codeforces.com/contest/1553/problem/B)PS: It's not unnecessary tagging. Also even with editorial there are times that solution writer didn't go with simple solution. Tagging is just one thing. If you don't think you are right person to answer, just leave it.
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 I agree with the first part of your reply regarding elevated time for problems. however, there's a place to ask such questions you don't ask them in comments here and tag people.a better way is to go into to contests "**Ask a question** section..this isn't insta or fb.
•  » » » » » 14 months ago, # ^ |   0 Didn't knew there was such a thing. I will check that out
•  » » 14 months ago, # ^ |   0 Wow. So many downvotes for no reason. I raised a valid concern for god's sake.The problem https://codeforces.com/contest/1553/problem/B. works in 500*3 (about 10**8) complexity , but my solution in today's contest has time complexity of (12*10^5 + 2*10^5) in worst case and i still got TLE.
•  » » » 14 months ago, # ^ |   +11 It's not a new issue. Many times python and java solutions get TLE due to strict time limit(Ask secondThread lol). Nothing can be done after contest.
•  » » » » 14 months ago, # ^ |   +10 By the way you can watch SecondThread raging on this here (https://youtu.be/3tE2N2PkDC8) (headphone warning*).
•  » » » » 14 months ago, # ^ |   0 Thanks for this
•  » » 14 months ago, # ^ |   +5 Use pypy with some fast io (fast io is an issue even in c++ so it's kind of fair).Your code ACs in 732ms: https://codeforces.com/contest/1555/submission/124358306
•  » » » 14 months ago, # ^ |   0 ok.I could have simply taken pypy3 instead of python to save my points. But may be in next contest
•  » » 14 months ago, # ^ |   +5 You have a choice of languages, Python is known to be slow, and Codeforces make it very clear that the time limits are the same for all languages. I normally choose to use Python, for ease of writing, in spite of this, but I know that its performance, even using PyPy, can be a problem. When you select the standard Python interpreter (cPython) as your submission language Codeforces tell that PyPy is normally faster I am not sure why your code is slow, but my Python code for this problem runs well within the time constraints using either Python or PyPy3. See my contest submission using PyPy3 and the same code run with Python 3
 » 14 months ago, # |   0 a lot of case works in B :/
•  » » 14 months ago, # ^ |   0 i don't think there will be lot of case work just have a look on my solution it was pretty short https://codeforces.com/contest/1555/submission/124301671
 » 14 months ago, # |   -40 What the heck is wrong with guy who set up problem B. Like you really want the people to stop logical coding using their thinking skills and just spend 15 minutes considering all the cases like a donkey, and spend another 30 debugging when they get a penalty on the same code. Is this the way the best coding platform wants to evaluate its participants? If yes, then good luck/bye caseforces!PS : i think the problem setters just wanted to minimize the nuumber of people who could attempt the good questions afterwards by just sticking them to this **** problem!
•  » » 14 months ago, # ^ |   +8 Cleanish Solution#include #define ll long long using namespace std; ll ans (ll W, ll H, ll x1, ll y1, ll x2, ll y2, ll w, ll h){ ll a1 = 1e9; ll dy1 = max(0ll, h - y1); ll dx1 = max(0ll, w - x1); //cout << dx1 << " " << dy1 << endl; if(dy1 + y2 <= H) a1 = dy1; if(dx1 + x2 <= W) a1 = min(a1, dx1); return a1; } void solve(){ ll H, W; cin >> W >> H; ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; ll w, h; cin >> w >> h; ll a1 = ans(W, H, x1, y1, x2, y2, w, h); //cout << a1 << endl; ll a2 = ans(W, H, W - x2, y1, W - x1, y2, w, h); ll a3 = ans(W, H, x1, H - y2, x2, H - y1, w, h); ll a4 = ans(W, H, W - x2, H - y2, W - x1, H - y1, w, h); a1 = min(min(a1, a2), min(a3, a4)); if(a1 == 1e9){ cout << "-1\n"; }else{ cout << a1 << '\n'; } } int main(){ int t; cin >> t; while(t--){ solve(); } } Nevertheless, I did not like problem B either. It was just implementation, no thinking.
•  » » » 14 months ago, # ^ |   +11 More Cleaner ig#include using namespace std; void solve(){ int W, H; int x1, y1, x2, y2; int w, h; cin >> W >> H >> x1 >> y1 >> x2 >> y2 >> w >> h; int ans = INT_MAX; // moving in x if(w <= (W - (x2 - x1) ) && h <= H) { int d_x = max(0, min(w - x1, w - (W - x2))); ans = min(d_x, ans); } // moving in y if(h <= (H - (y2 - y1)) && w <= W) { int d_y = max(0, min(h - y1, h - (H - y2))); ans = min(ans, d_y); } cout << (ans != INT_MAX ? ans : -1) << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int tc = 1; cin >> tc; for(int z = 1; z <= tc; z++) { // cout << "Case #" << z << ": "; solve(); } return 0; } Basically, you can just try moving it along only x-axis or only y-axis. There is no need to move it in both axes.
 » 14 months ago, # |   0 Problem F:I used HLD to solve it. Can somebody please tell does there exists any approach without HLD?
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 Did you use HLD to find usable edges? I'm not sure but I think the problem boils down to single usage of an edge in the tree formed from all the queries and if that's the case, we can split the tree about an edge that can't be used anymore, and re-root the smaller component with another parent? Just like small to large merging. PS : We can keep splitting a tree into forests by this process.
•  » » » 14 months ago, # ^ |   0 Initially, I made a tree by using only edges which are first time connecting any two different components, then observed that any cycle can span atmost one edge of the tree. After that, used HLD for max path queries. So after that anytime got validation for adding any edge just set all values of all edges to infinite (basically deleted). To check validation, just did a max path query.Can you please tell in your approach after splitting into forest how are you checking for any query.
•  » » » » 14 months ago, # ^ |   0 Yes I was thinking of the exact same thing. But just to confirm, please tell me if this is right. First off anytime a tree edge arrives we can add it. Otherwise I found a sum for each node in the tree that denotes the xor of the path from the root to that node. If 2 nodes are in the same tree in the current forest of trees and have xor of Node sums = (edge ^ 1), then they can be connected. Otherwise they cannot be connected. Now if they can be connected, we can disconnect each edge on the path between them using the process i described before and recalculating the sums and root Node for each Node in the smaller component.
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +9 dnshgyl21 I think your implementation does not consider the fact that it will be a HLD forest, you always start from root 0.
•  » » 14 months ago, # ^ |   +6 Model solution is without HLD. We'll describe it in editorial, but shortly, we first find the MST of the graph (using the time when the edges are added as weights, to find the edges that are definitely present in the answer), then create a logarithmic data structure like Fenwick or Segment Tree to mark the edges belonging to a cycle and/or verifying that the cycle we're adding doesn't intersect with some previously created ones.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +5 Can you please describe how can we mark edges on any path in a tree using Segment or Fenwick tree?Upd : Thanks,i got it now.
•  » » » » 14 months ago, # ^ |   +8 There is a way to range addition on the path from $v$ to $root$ and range sum on path from $v$ to $root$ using two Segment Trees, but it's not needed here.Since each edge will be marked at most once, you can mark edges one by one while asking a sum on path: all using Fenwick tree on Euler tour.
 » 14 months ago, # |   -61 could someone tell me whether i am wrong with these i have tried my own these problem link void solve(vectorv[],int src,vector&euler,unordered_map&mp,int &counter) { euler.pb(src); if(mp.find(src) == mp.end()) mp[src] = counter; for(auto i:v[src]) { counter++; solve(v,i,euler,mp,counter); counter++; euler.push_back(src); } } void storeminimum(vector&euler,int sq,vector&sqrtd) { for(int i=0;i>t; for(int kk=1;kk<=t;kk++) { int n; cin>>n; vectorv[n+1]; for(int i=1;i<=n;i++) { int m; cin>>m; for(int j=0;j>a; v[i].pb(a); } } // first occurance unordered_mapfoc; // store euler path vectoreuler; int count = 0; solve(v,1,euler,foc,count); int sq = ceil(sqrt(euler.size())); vectorsqrtd(sq,INT_MAX); storeminimum(euler,sq,sqrtd); int q; cin>>q; cout<<"Case "<>a>>b; int ans = INT_MAX; int l=foc[a],r=foc[b]; while(l<=r) { if(l%sq ==0 and l+sq-1<=r) { ans=min(ans,sqrtd[l/sq]); l+=sq; } else { ans = min(ans,euler[l]); l++; } } cout<
•  » » 14 months ago, # ^ | ← Rev. 2 →   +7 Remember to use spoiler next time :) and you are not even talking about a problem from the contest.
•  » » » 14 months ago, # ^ |   -7 sorry i didnt get you ??
•  » » » » 14 months ago, # ^ |   +6 It takes a lot of time to scroll down if people don't want to see your code.
•  » » » » » 14 months ago, # ^ |   +8 ok sorry for that , i am knew so dont know much about how to use that .
•  » » » » » » 14 months ago, # ^ |   0 Seems like you are NEW in english too
•  » » » » » » » 14 months ago, # ^ |   0 ya , but that's not the main point, the point is about my question
 » 14 months ago, # | ← Rev. 3 →   +42 Are you kidding me? I used old version of problem F statement where cycle was simple if there weren't any repeated edges. And this is the only reason why I didn't get accepted during the contest. I've got accepted in 2 minutes after the round ended, so sad(
•  » » 14 months ago, # ^ |   0 We are sorry, we actually noticed the bug in Russian version only, like, 10-15 minutes before the end of the contest :(
 » 14 months ago, # |   +6 Can somebody please explain the solution of problem A?
•  » » 14 months ago, # ^ |   0 What I did was, write down N as N = 6a + 8b + 10c. Now this can be written as N = 2 * ( 3a + 4b + 5c ). Now let's take ( a + b + c = S ) , so we equation becomes N = 2 * ( 3 * S + b + c ), and b + c = S — a. So this becomes N = 2 * ( 4 * S — a ). Now just find a and S( and one thing if N is odd take N as N + 1, don't know the reason for this but it just worked for odd numbers because they are not divisble by 2 ).Now the total time required is TIME = 15a + 20b + 25c. TIME = 5*( 4 * S — a ). This is the answer.
•  » » » 14 months ago, # ^ |   0 3*S+b+2*c
•  » » » 14 months ago, # ^ |   0 The question asks to find x, y, z, when 6x+8y+10z is greater than or equal to n, find the minimum value of 15x+20y+25zNote that 15/6=20/8=25/10=2.5Let us make an equivalent transformation for the condition 6x+8y+10z >= n.3x+4y+5z >= (n+1)/2.Note that gcd(3,5) = 1 , so all numbers greater than 7=3*5-3-5 can be formed by adding several 3 and 5.For the part less than 7, it can be solved directly by violence.
•  » » » 14 months ago, # ^ |   0 the thing N + 1 /2 works because we need "atleast" n pizza slices if n is odd we cant get exactly n slices so we cook extra
•  » » 14 months ago, # ^ |   +3 if(n<=6) we need only 1 small pizza giving ans as 15 mins Consider x small , y medium and z large pizzas : so number of slices will be n = 6x + 8y + 10z corresponding to it , time spent = 15x + 20y + 25z = 5*n/2 ( in terms of 1st equation) for odd number of slices , u can find that ans modifies to 5*(n+1)/2
•  » » 14 months ago, # ^ | ← Rev. 2 →   +4 I listed out the first 20 values of n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 15,15,15,15,15,15,20,20,25,25,30,30,35,35,40,40,45,45,50,50,55 and noticed that increases by 5 every 2 out.println(Math.max(15, ((n + 1) / 2) * 5)); 
•  » » » 14 months ago, # ^ |   0 Yeah that is also what I did, unfortunately it occurred to me after 4 WAs lol
•  » » 14 months ago, # ^ |   +1 If $n<=6$, print $15$For $n>6$, if $n$ is even, print $n*2.5$else print $(n+1)*2.5$
 » 14 months ago, # |   +5 Expected to become an expert today, will probably end up as a pupil... Spent both the hours on Problem A and got 7 WAs, lol.
•  » » 14 months ago, # ^ |   0 Almost did the same, then decided, 'hey, why not check other problems'.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +1 Can't argue with that, though I spent around an hour trying to figure out why exactly was even a brute-force solution giving me WA (Brute Force on n % 120, 120 being the LCM)... And I still don't know what exactly is wrong with my code... Edit: I finally realized that considering n / 120 and n % 120 separately doesn't always give the optimal answer. Eg: 121: My output would be 315, while the optimal answer is clearly 305. My program would waste 5 slices of pizza, while the optimal answer would only waste one.
•  » » » » 14 months ago, # ^ |   +1 I had a similar approach like this but my code also gave WA, did you try for all i in the range 1 to 16. My code was giving wrong answer in this range and correcting for this got me Accepted
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 ...
•  » » 14 months ago, # ^ |   0 If you saw the sample cases, you would've noticed the answer always being ((n+1) * 5) / 2 for n >= 6. Something to do with the fact that 15/6 = 20/8 = 25/10 = 5/2.
•  » » » 14 months ago, # ^ |   +8 Yeah, I guess the McNugget theorem can be applied to this problem as well. The McNugget Theorem 6 = 2 * 3, and 8 = 2 * 4. 3 and 4 are relatively prime, so the greatest number which cannot be formed by them is 3*4 — 3 — 4 = 5 (10, because of *2; 10 exists as the third term here, so it too is covered). Because we only need to consider even numbers (odd numbers can be converted to even), and we are working with *2 here, all the even terms above 6 will be covered. Numbers below and equal to 6 can be processed as a special case.
•  » » 14 months ago, # ^ |   0 hahahha.
 » 14 months ago, # |   +20 Solved 4 but still feeling worthless because of A and B xD
 » 14 months ago, # |   0 I spent 40 minutes on A and didn't have enough time to solve E ：(
 » 14 months ago, # |   +179
•  » » 14 months ago, # ^ |   +23 I lost B to precision today.. just changing double to integer made it pass. Significant digits turned out to be so significant today :( The pain though!
 » 14 months ago, # |   +22 B ruined my entire contest. Couldn't even read E though it was pretty doable. :((
•  » » 14 months ago, # ^ |   +3 The more I read this blog, the more correct Heliac 's comment looks
 » 14 months ago, # | ← Rev. 3 →   +2 124312667 this is my submission for problem B during the contest where i took the values float instead of long long and it gave WA. It gave a difference of 2 in one of the TC. 124345470 this is that same approach(everything same just changed float to long long) but got accepted....can any one pls explain why this happened. edit: by mistake initially i gave the link to wrong problem.
•  » » 14 months ago, # ^ |   0 precision error
•  » » » 14 months ago, # ^ |   +2 and why will float be less precise than int/long long
•  » » » » 14 months ago, # ^ |   0 Sometimes with floats, it will do things like $1.0000001 = 1$. This is why, when comparing floating point numbers, I like to do something like this: thisfloat epsilon = 1e-9; bool isEqual(float a, float b) { return abs(a - b) <= epsilon; } 
•  » » » » » 14 months ago, # ^ |   +2 yes you are absolutely correct but my point is that if i am just having floats of type f.000000 and there is no multiplication just subtraction and addition then why would it give some difference.
•  » » » » » » 14 months ago, # ^ |   0 it shouldn't
•  » » » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 actualy 3 != 2^kso even with addition you should get precision erroredit: Am I right here?Like 3.000000 != 3 right?
•  » » » » » 14 months ago, # ^ |   0 or just multiply 10000000 and compare normally
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 C++ has it's own Epsilon value. Check this. Here std::numeric_limits::epsilon()
•  » » » » 14 months ago, # ^ |   0 google "precision error"it's not something someone can easily explain to you here
 » 14 months ago, # |   0 Can we do C using dfs ? I think it is the same as Cherry pickup II of leetcode ? please help.
 » 14 months ago, # | ← Rev. 2 →   -11 But its a question afterall with a valid difficulty range for qstn. B. Also,its my fault that i assumed it to be something else. It actually didn't have much case work. Apologies..
•  » » 14 months ago, # ^ |   0 Absolutely!!
 » 14 months ago, # |   +5 Was thinking I'll regain Expert! But problem B exists lol, ate up huge amount of time :(
•  » » 14 months ago, # ^ |   +1 Problem D is wonderful.Considering that a three-letter palindrome can only beabcabcabc... acbacbacb... bacbacbac... bcabcabca... cabcabcab... cbacbacba...Each position is symmetrical in rotation. So a simple prefix sum can be done for it. Code : https://codeforces.com/contest/1555/submission/124347304
•  » » » 14 months ago, # ^ |   0 Of course it is! I came up with exact logic to compare with 3! strings and make prefix array (precompute) and answer queries in O(1) time. But sadly , time ran out and I couldn't implement it fully.
 » 14 months ago, # |   +1 A clean(ish) solution for B. Spoilerimport math for _ in range(int(input())): W, H = map(int, input().split()) x1, y1, x2, y2 = map(int, input().split()) w, h = map(int, input().split()) available_x = W + x1 - x2 available_y = H + y1 - y2 z = False ans = 1000000000000.0 if(available_x >= w): current_available = max(x1 - 0, W - x2) t1 = float(max(0, w - current_available)) ans = min(ans, t1) z = True if(available_y >= h): current_available = max(y1 - 0, H - y2) t2 = float(max(0, h - current_available)) ans = min(ans, t2) z = True if(z): print(ans) else: print(-1) We need to check for the number of free cells possible in both X and Y directions. (Free cells are the cells not occupied by the first table). If the number of free cells in ANY direction (X or Y) is greater than the number of cells needed for second table, then we can fit the second table in. The first table only needs to move horizontally or vertically to acommodate the second table, it will never have to move diagonally. SpoilerIf my approach seems wrong, hack it ;)
 » 14 months ago, # |   +5 Is the rating predictor broken?
•  » » 14 months ago, # ^ |   +12 yeah seems like it is considering previous rating
 » 14 months ago, # |   -40 In reference to problem B 3 actions can be taken: 1. Rename the website to caseforces 2. Ban the guy who set it up from setting up future contests 3. The guy should have some self respect and delete his account
•  » » 14 months ago, # ^ |   +22 What do you mean? There were only 3 cases: -1, horizontal fit, and vertical fit.
 » 14 months ago, # | ← Rev. 4 →   +54 Should we be sad or happy in this case? :(from Imgflip Meme Generator
 » 14 months ago, # | ← Rev. 3 →   0 One of the best contests I have participated at in my life. Beautiful, Balanced and the Best
 » 14 months ago, # |   +2 Actually problem B should be C and C should be B!
 » 14 months ago, # |   0 hey, guys i am new to this platform, where can i find the editorial for the questions??
•  » » 14 months ago, # ^ |   0 It will be published after some time.
 » 14 months ago, # |   0 hard contest only the first problem was easy
•  » » 14 months ago, # ^ |   +1 Everything is relative.. I thought A was hard, B and C were easy
•  » » » 14 months ago, # ^ | ← Rev. 3 →   0 :)
 » 14 months ago, # |   +8 4 Div2 (with 2 Div1) Round, 2 Div3 Round, 2 Educational Round, 2 Div(1+2) Round, and 1 Global Round, Total of 11 Rounds held in this Month. So we can say July is the perfect month for all the contestants who like and enjoy every round of Codeforces. Thanks to Mike Mirzayanov and all the problem setters of this month <3
 » 14 months ago, # |   0 wonder how many guys copy-pasted their segment_tree for E from the Internet
•  » » 14 months ago, # ^ |   0 From which part of the Internet? Do you mean that general purpose segment tree libraries are available? Or a complete solution for exactly this problem is available?
•  » » 14 months ago, # ^ |   0 Can you please explain the approach of problem E? Where do we need segment tree?
•  » » » 14 months ago, # ^ |   0 You can use two pointers with segment trees to maintain the minimum value
 » 14 months ago, # |   +5 A solution video for the first four questions of div 2https://www.youtube.com/watch?v=NMSQ-uu59mQ
 » 14 months ago, # |   0 why to even use double in problem B as shown in sample output.
•  » » 14 months ago, # ^ |   +3 it's a trick to fool people, and also it accepts solutions that somehow use doubles
•  » » » 14 months ago, # ^ |   0 yes
•  » » 14 months ago, # ^ |   +4 That was just to confuse us so that we start thinking the box both horizontally and vertically as shown in the example diagram.
•  » » 14 months ago, # ^ |   0 I wasted 5 minutes thinking that when can the answer be in double.
 » 14 months ago, # |   +3 I misread problem D and thought that input string can contain any 26 letters of Latin alphabet and it is allowed to change any character of the string to one of the first 3 letters and couldn't solve that problem. Can this problem be solved?
•  » » 14 months ago, # ^ |   +3 I think that it is possible if you spend $O(r - l)$ on each query or do precalc and spend $O(n^2)$
 » 14 months ago, # | ← Rev. 3 →   +31
 » 14 months ago, # | ← Rev. 5 →   +5 The solution to Problem A with Proof:... Trivial Cas: N <= 6: Answer = 15 Observation: 6 slices — 15 minutes => 1 slice — 2.5 minutes 8 slices — 20 minutes => 1 slice — 2.5 minutes 10 slices — 25 minutes => 1 slice — 2.5 minutesThus, each pizza slice is baked in the same time no matter if we pick 6, 8, or 10.Now, Assuming that N >= 7 Case 1: N = even Claim: we can represent N = a * 6 + b * 8 + c * 10Proof: N = 2K. so, it is the same as saying 2K = a * 6 + b * 8 + c * 10 => K = a * 3 + b * 4 + c * 5Since N >= 7, K >= 7 / 2 = 3.Now, we need to prove that K (>= 3) can be represented as a * 3 + b * 4 + c * 5.Observation: 4 = 1 mod 3, 5 = 2 mod 3. It is obvious that if K can be of the following types only:k = 0 mod 3 -> Pick only 3sk = 1 mod 3 -> Pick only 3s and a 4k = 2 mod 3 -> Pick only 3s and a 5Answer = (N) * (2.5) because each slice is now of the same value. Case 2: N = odd. Clearly, for the odd case, we cannot represent N as a * 6 + b * 8 + c * 10 as LHS is odd and RHS is even.So, we definitely need to bake more slices than required. Thus, we can just add 1 to N and get the same situation as Case 1. Hence answer = (N + 1) * (2.5)
•  » » 14 months ago, # ^ |   +11 For the claim, you can give a one line proof by induction. It's true for $6 \leq N \leq 10$ and assuming it is true for all even numbers less than $N$ with $N - 6 \geq 6$ we can write $N$ as $N - 6 + 6$ and we're done by induction.
•  » » » 14 months ago, # ^ |   0 Ohh didn't notice that. Pretty cool.
•  » » 14 months ago, # ^ |   0 I proved this using Arithmetic mean >= geometric mean
•  » » 14 months ago, # ^ |   0 here is my sol for A. #include #define ll long long using namespace std; int main(){ int tc; cin>>tc; while(tc--){ ll n,ans; cin>>n; if(n<=6){ ans=15; } else{ double a=n*2.5; ll b=a; if(a-b!=0){ a+=2.5; ans=a; } else{ ans=a; } } cout<
•  » » 14 months ago, # ^ |   0 I did like this https://codeforces.com/contest/1555/submission/124321685
 » 14 months ago, # |   -9 Nice round with not easy nor really hard tasks E is especially good!
 » 14 months ago, # |   0 Can someone guide me on how to solve extended version of today's C problem. Consider N rows and M columns with the same problem statement.PS: Constraints can be adjusted accordingly
•  » » 14 months ago, # ^ |   0 It's nice that there wasn't that version of that task)))
 » 14 months ago, # |   0 Is anybody know which testcase is in task b test 2 case 554? My solve fails on it and idk why... Here is link on it https://codeforces.com/contest/1555/submission/124358523 [](https://codeforces.com/contest/1555/submission/124358523) plz say what is wrong...
•  » » 14 months ago, # ^ |   0 You ignored the word "minimum". We need to find the minimum and when both horizontal and vertical is possible.https://www.youtube.com/watch?v=NMSQ-uu59mQ
 » 14 months ago, # |   +3 Where's the editorial?
•  » » 14 months ago, # ^ |   0 I think It will be published after the open hacking phase of 12 hr in the educational round. You can refer my video https://www.youtube.com/watch?v=NMSQ-uu59mQ
 » 14 months ago, # |   0 GreedyForces
 » 14 months ago, # |   -6 Questions about Karry5307_AK_NOI2022 again: How could he solve B in 29 seconds at 00:09:43 after he solved C at 00:09:19? How could he solve F in only 3 minutes after he solved E at 00:51? You see, SSRS_ solved it in 21 minutes, tourist solved it in 42 minutes, and WZYYN solved it in 25 minutes. These three are all LGM but they solved F in at least 20 minutes. How could this guy solved it for only 3 minutes? I think there must be something strange.
•  » » 14 months ago, # ^ |   +28 I think it is possible that he submitted B and C at the same time because of the bad Internet connection. But a more likely guess is that some people shared this account and solved these problems together.I am sure that this account's owner is not real Karry5307 because in China nearly nobody will register an ID of "I all killed a contest".
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +19 But I believe that God Karry5307 has such courage and power.
•  » » 14 months ago, # ^ |   +112 Although he(they) might cheat,he(they) can't beat me because I am much stronger than h0up1ngze!
•  » » » 14 months ago, # ^ |   0 You are much stronger than tourist :)
•  » » » 14 months ago, # ^ |   -19 You are much stronger than tourist :)DXqwq
•  » » » 14 months ago, # ^ |   +52 Yes,she is too naive.
•  » » » 14 months ago, # ^ |   +3 You are much strong than tourist :-)
•  » » » 14 months ago, # ^ |   +8 Yeah, you solved F in less time than tourist, then you'll soon become a LIGM(Legendary International Grandmaster) soon :)
•  » » » 14 months ago, # ^ |   +17 You are much stronger than tourist :)
•  » » 14 months ago, # ^ |   0 If you check his submissions you can notice that after he submitted D, he coded F for 31 minute, but then got WA, after one more submission for F, he coded E in something like 2-3 minutes (the only code he actually wrote is in main, so I believe 3 minutes were enough), and after that he returned to F. In total he spent ~34 minutes for the last problem, which is quite legit.
•  » » » 14 months ago, # ^ |   0 Oh, I finally got it. Sorry for my misunderstanding :(
•  » » 8 months ago, # ^ |   +3 he/she is LGM now.
 » 14 months ago, # |   0 Can we do C using dfs ? I think it is the same as Cherry pickup II of leetcode ? please help.
•  » » 14 months ago, # ^ |   0 DFS would be overkill here. You can simply use prefix sum and compute the result for each i (Alice will move down). Then take the minimum result.
 » 14 months ago, # |   0 Can anyone help me with problem B solution?? What I am doing wrong here? It is failing 2nd test. Here is the verdict: wrong answer 530th numbers differ - expected: '0.0000000', found: '1.0000000', error = '1.0000000' here is code: #include using namespace std; #define ll long long int main() { int tc; cin >> tc; while (tc--) { ll W, H, x1, y1, x2, y2, w, h; cin >> W >> H; cin >> x1 >> y1 >> x2 >> y2; cin >> w >> h; ll ans = 0; if ((h + (y2 - y1)) > H && (w + (x2 - x1)) > W) cout << -1 << "\n"; else if ((w + (x2 - x1)) > W) { //work vertically //cout<<"h="<
•  » » 14 months ago, # ^ |   0 please help me what I am doing wrong here
•  » » » 14 months ago, # ^ |   0 i think the problem is that you are not considering the case where u can fit it both vertically and horizontally.so i would suggest to look in both direction. Like here after going in elseif. it is not going to go in else to check if u can get a smaller ans
•  » » » » 14 months ago, # ^ |   0 yes correct. Thank you.
•  » » » 14 months ago, # ^ |   0 1 5 8 1 3 4 5 2 3 Test case for your reference it should give 0 but your code giving 1 b/c it not checking vectically.
 » 14 months ago, # |   +14 Have the solutions been rejudged yet? When will the ratings change?
 » 14 months ago, # |   +11 Interesting Round, thanks!
 » 14 months ago, # | ← Rev. 2 →   +3 Can we just appreciate that there is no pretest for D where m < n, so I got RTE. Nice.
 » 14 months ago, # |   0 what's the binary search solution for E? I am more interested in how to write the predicate function in o(logn) or so ?
 » 14 months ago, # |   +7 MikeMirzayanov My submissions of this round skipped getting an unexpected warning that my submission to the problem C 124303153 coincides with the submission 124301236 by NZB. This is totally unexpected. The solution to problem C is super simple. I request you to manually check the submissions and the solution to problem C. I'm totally disappointed with this kind of wrong warnings from such a reputed platform like codeforces. Because this is the second time I have been convicted without doing any kind of violations. I wrote a detailed blog on this after getting my first warning but nothing changed. Please read the blog Unexpected warnings from CodeForces. Hope you will look into the matter. Thanks.
•  » » 14 months ago, # ^ |   +5 MikeMirzayanov same thing happened with me for Question C. The problem was a very simple one.Please look into this
•  » » 14 months ago, # ^ |   +3 The idea and code of problem C are really quite simple. So, the chances of having similarities in codes are high. Even, my submission's main function has a lot of similarities with you: 124324875. It's quite unfortunate and saddening to see such false-positive cases. I hope, MikeMirzayanov will look into this matter and sort out this thing.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +1 MikeMirzayanov This same thing happened to me too... I received an unexpected message from System saying that my submission was similar to some 10+ other submissions for this problem? This was purely coincidental at least on my end, since the problem's solution was so short.Here is mine: 124296686.Also my submission ID was earlier than every other submission mine was considered similar to, so there's no way I could've copied/cheated from any of these people.
 » 14 months ago, # |   0 Someone, please explain the first test case of question 5
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 The following segments are sufficient enough to reach from 1 to 12. However, you can additionally take other segments. But they will not minimise the answer. 1 5 5 4 10 6 10 12 3 
 » 14 months ago, # |   0 Check out this tutorial for problem C: https://youtu.be/L7AhdGhO2v4
 » 14 months ago, # |   0 Please post the editorial asap
 » 14 months ago, # |   0 Did anyone who solved F use lca,dsu & merge small into large?
 » 14 months ago, # |   0 How A can be solved using chicken nugget theorem .
 » 14 months ago, # |   0 How can we solve C using dp?
 » 14 months ago, # |   0 When I tried solving problem B using long double for output, I was getting WA on Test 3. But when I used long long instead of long double in the same solution, it got accepted. Why? Can someone please explain?
•  » » 14 months ago, # ^ |   0 I think it's because of your output format. You used cout for printing double value. But you didn't set any precision or width. A good way to print double/floating value using cout is: cout<
•  » » » 14 months ago, # ^ |   0 Thanks a lot for replying. It worked.
 » 14 months ago, # | ← Rev. 2 →   +3 One constructive feedback : It would be really nice if educational rounds had atleast one problem with a high upsolve value for Div2 contestants, i.e. problem that is slightly out of reach for majority of Blue/Purple contestants.In this contest, E is a very standard lazy segtree problem and F is (seems ?) too hard.
 » 14 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 14 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 14 months ago, # |   0 Can anyone please advise how is it possible to pass the TL5 challenge in problem D? Here is my submission, cannot yet figure out the bottleneck. Thank you!
•  » » 14 months ago, # ^ |   0 It turns out changing vector p : r to auto& p : r` solves the problem.