### Ahmed_Hosssam's blog

By Ahmed_Hosssam, history, 13 days ago,
عيد سعيد(Happy Eid), Codeforces!

I'm glad to invite you to Codeforces Round #788 (Div. 2), which will be held on 06.05.2022 17:35 (Московское время).

This round is rated for the participants with rating lower than 2100.

You will be given 6 problems and 2 hours to solve them. All problems were prepared by me, Hemose and ZerooCool.

I would like to thank:

• Monogon, for a lot of things (awesome coordination, helping in preparation, rejecting only not interesting tasks and a lot of useful discussions).

• I_Love_Slim for teaching us BLABIZO useful concepts.

• MikeMirzayanov, for the amazing Codeforces and Polygon platforms.

The statements are short and we have tried to make the pretests strong. I encourage you to read all the problems.

For people who don't like stories, you will find all the stories written in italic you can skip them safely.

We are sincerely looking forward to your participation. We hope everyone will enjoy it.

Good luck and see you in the standings!

UPD: The score distribution is 500-1000-1750-2250-2750-3000.

UPD: We hope you liked the problems, here is the Editorial

• +575

 » 13 days ago, # |   +76 GUC gang!
•  » » 11 days ago, # ^ |   +13 Eid mubarak everyone.
•  » » 3 days ago, # ^ | ← Rev. 2 →   +14 GUC orz
 » 12 days ago, # |   +108 As a tester, I'd like to say that no java coders were hurt in the making of this contest.
 » 12 days ago, # |   +150 As a tester, I will give you hints to the problems
•  » » 12 days ago, # ^ |   -7 So happy to see you here our coach . you are a source of pride
•  » » » 11 days ago, # ^ |   -33
•  » » 11 days ago, # ^ |   0 Why is there > 100 upvote on a rick roll link?
•  » » 11 days ago, # ^ |   0 As a participant, I'll give you solutions to all the hints
•  » » 11 days ago, # ^ |   0 I deleted youtube!
•  » » 11 days ago, # ^ |   0 These hints are very useful, thank you
•  » » 10 days ago, # ^ |   0 Why there is a Huge jump from B to C ?
 » 12 days ago, # |   0 As a possible contestant if time permits, I would like to present my sincerest congratulations and best wishes to the GUC team for the kind endeavors.Heartbeat
 » 12 days ago, # |   +3 This is the first Egyptian round after a long time! Our congratulations!
•  » » 11 days ago, # ^ |   +34 The pharaohs are back
 » 12 days ago, # |   +4 Eid ul Fitr Mubarak to you and your family.
 » 12 days ago, # |   +3 Score distribution? (:
 » 12 days ago, # | ← Rev. 2 →   +14 As a GUCian, I'd like to say that those people are wonderful. Hope it will be a nice contest!
 » 12 days ago, # |   +9 EID Mubarak
 » 12 days ago, # |   +9 Eid Mubarak
 » 12 days ago, # |   +2 distribution?
 » 12 days ago, # |   +2 Egyptian round? Long time no see)
 » 12 days ago, # |   +16 Hemose is back yayy! :D
 » 12 days ago, # | ← Rev. 2 →   +39 congratulations Bakry qualifying to ioi https://www.facebook.com/eoi.eg/photos/a.288097731292115/4626081414160370/
•  » » 11 days ago, # ^ |   +10 Thanks :D
 » 11 days ago, # |   +10 Looking forward to participate! Eid Mubarak
 » 11 days ago, # | ← Rev. 2 →   +24 Coders(>1600 rated) : Finally we can participate ;-;
 » 11 days ago, # | ← Rev. 2 →   -55 .
 » 11 days ago, # |   +30 As a GUCIAN tester, I am proud of you and your great round.)
 » 11 days ago, # |   0 Pharaohs' Contest is back OwO
 » 11 days ago, # |   +9 "You cannot vote twice. You have already voted for this topic before."x10
 » 11 days ago, # |   +6 We're so proud of u guys. Keep going and make us proud in ICPC too , ISA
 » 11 days ago, # |   +16 GUC on fire
 » 11 days ago, # |   0 Maybe Egyptian round is full of Bitwise and Math problem hahaha :)
 » 11 days ago, # | ← Rev. 3 →   0 It's my first time to participate the div 2 contest unofficially.
 » 11 days ago, # |   +3 EID Mubarak
 » 11 days ago, # |   0 Never give any contest for increasing your rating. Just give it to learn something new, and rating will definitely increase sometime.
 » 11 days ago, # |   0 GUC on The TOP of STANDINGS <3
 » 11 days ago, # |   0 thank you problems author
 » 11 days ago, # |   0 As this is an egyptian round, being the egyptian king I must perform great in this round. Hoping for good fat +ve delta.
•  » » 11 days ago, # ^ |   0 how did u get out of the sarcophagus?
 » 11 days ago, # |   0 3id s3id!
 » 11 days ago, # |   +5 i hope be pupil in this round
•  » » 11 days ago, # ^ |   0 why you practice so many problems，but still newbi？
•  » » » 11 days ago, # ^ |   +1 Because in a long period in my training I was solving easy problems and I did not benefit from them, and another reason was that I had to solve problems from training beginners in order to help them solve them because I am mentor
•  » » » » 11 days ago, # ^ |   +1 wow, I really hope you could be more and more exctllent! As for me, I just learn algorithm for three months, ans I hope I can be a master one day! Best wishes for you!
•  » » » » » 11 days ago, # ^ |   +1 thanks
 » 11 days ago, # |   0 how cool man
 » 11 days ago, # | ← Rev. 2 →   0 will try to solve atleast 3 questions today.
 » 11 days ago, # |   +4 Eid Mubarak(⦁ᴗ⦁)
 » 11 days ago, # |   +1 As an Arab contestant, I am always glad to see Egyptian rounds on CodeForces. Well done GUC, keep it up guys!
 » 11 days ago, # |   +6 Good luck everyone
 » 11 days ago, # |   +10 "For people who don't like stories, you will find all the stories written in italic you can skip them safely." — Whoa cool!
 » 11 days ago, # |   +1 Good luck everyone!
 » 11 days ago, # |   +1 Wish you all a great rating gain.
 » 11 days ago, # |   +2 Eid Mubarak to everyone
 » 11 days ago, # |   0 EID MUBARAK & GOOD LUCK !!
 » 11 days ago, # |   0 Eid mubarak everyone.
 » 11 days ago, # |   0 All the best!! :)
 » 11 days ago, # |   0 Meme
 » 11 days ago, # |   +16 I enjoy problem E but I hate problem D!
•  » » 11 days ago, # ^ | ← Rev. 2 →   +3 n lines would make these many triangles = 2 * (n)^2 / 3
•  » » » 11 days ago, # ^ |   +7 what is the the proof?
•  » » » 11 days ago, # ^ |   +24 I did it like this :- we can have 3 directions for lines to draw ,each time we draw a line in one direction then it intersects all the lines in other two direction and thus creates 2*X more equilateral triangle where X is the total number of lines in other two directions.
 » 11 days ago, # |   0 Does GNU C++17 7.3.0 allow __int128? I met this compilation error: Can't compile file: program.cpp: In function 'int main()': program.cpp:266:17: error: template argument 1 is invalid vector<__int128> limit(60, 0); 
•  » » 11 days ago, # ^ |   +5 I think it need 64bit compiler
•  » » 11 days ago, # ^ |   0 GNU G++20 11.2.0 (64 bit, winlibs) is fine
 » 11 days ago, # |   +4 Dang, I think I was really close to solving E for the first time. It's a pity I now have to wait for system test to end in order to test my solution :(
 » 11 days ago, # |   -8 Points of C should be 1500
 » 11 days ago, # | ← Rev. 2 →   +6 Problem C was a modification of 1534C - Little Alawn's Puzzle
•  » » 11 days ago, # ^ |   +3 yes that problem came to my mind too when I saw problem C.Btw your pfp is cute
•  » » 10 days ago, # ^ |   0 true ^_^
 » 11 days ago, # |   +3 I just don't know why D had so tight constraints and the fact that I used some random optimization was able to pass the pretest is insane.
•  » » 11 days ago, # ^ |   +3 because it's one time sqrt(N) initialization.
•  » » » 11 days ago, # ^ |   +1 I've solved it with binary search, without any initialization (preprocessing). You can see my code 156115088.
•  » » » » 11 days ago, # ^ |   0 why don't you consider the points where three lines intersect and will create 6 equilateral triangles in a hexagon?
 » 11 days ago, # | ← Rev. 2 →   +9 In E we can choose any vertex to be root, right? And max xor will always be n, where n is number of vertices?
•  » » 11 days ago, # ^ |   0 Yes
•  » » 11 days ago, # ^ |   0 Yes. I think you mean E?
•  » » » 11 days ago, # ^ |   0 yes, E, my bad :)
 » 11 days ago, # |   +11 I really enjoyed this round, thx to everyone who participated to make this contest! :)
 » 11 days ago, # |   0 Pretest 4 in problem B is a mystery for myself :)
•  » » 11 days ago, # ^ |   0 Me too, but I made some changes i thought it will not do anything, i passed :)
 » 11 days ago, # |   +6 Was F digit dp?
•  » » 11 days ago, # ^ | ← Rev. 2 →   +10 yup, slightly modified tho
 » 11 days ago, # |   +43 In my opinion, I think problem D is more like a math puzzle than a cp problem.
•  » » 11 days ago, # ^ |   +8 In programming contest ICPC style are many full math problems, with many theorems, it's a good way to train for it. However, I think it's more an Ad Hoc problem than a full math problem. And you need binary search too
 » 11 days ago, # |   0 No idea with Problem E & F after solving A~D in ~1h :(
•  » » 11 days ago, # ^ |   0 E is also a math puzzle, like D :)
•  » » » 11 days ago, # ^ |   0 I solved a similar problem which asked how many area can be divided by $n$ lines in a infinite plane before. So I came up with that idea for D immediately. But no clue for E hh, maybe need more practice.
•  » » » » 11 days ago, # ^ |   +4 We can't avoid the Nth bit appear in the final cost. So the answer of maximum cost is 1 << N. assign this number to root node. Then for any other node x, if its depth is even (depth of root is 0), assign x and x | (1 << N) to it and the path linking it to its parent node, otherwise assign x | (1 << N) and x.
•  » » » » » 11 days ago, # ^ |   0 that logic is so clear..! I didn't even figure out the root can be fixed as 1 << N.. thanks for given clue..!
 » 11 days ago, # | ← Rev. 3 →   0 I have only a few words to say about this: damn it i cant attach pictures Although E and F were very nice
 » 11 days ago, # |   +12 Q4 is Guessforces
 » 11 days ago, # | ← Rev. 2 →   0 A simple testcase could hack my solution of B, and I was so anxious that my analysis of the time complexity is wrong :(
•  » » 11 days ago, # ^ |   0 looks you got TLE.
•  » » 11 days ago, # ^ |   0 So am I...
 » 11 days ago, # |   0 my python code for Q4 was giving TLE but it was only O(1). Can someone tell me what’s the problem?
•  » » 11 days ago, # ^ |   +19 Damn you commented with the wrong account
 » 11 days ago, # |   +17 Thanks for the strong pretests!!
•  » » 11 days ago, # ^ |   0 Yeah very strong pretests : https://codeforces.cc/contest/1670/submission/156081443
 » 11 days ago, # |   +13 Glad that you provided so many samples in the questions...
•  » » 11 days ago, # ^ | ← Rev. 3 →   +2 Seriously bro? Look at question (Edit: C), I took wrong modulo and got wrong answer on Test 2 and was going to leave contest. In such problems, it better to give atleast 1 case where number is larger than the modulo
•  » » » 11 days ago, # ^ |   0 I suppose you meant problem C?
 » 11 days ago, # |   +16 I didn't like the contest to be honest, and Here's my opinion: A is a normal problem. B is a bad problem and it has many details as a "B" problem. C is a bit standard problem (but with checking some cases), I think it's an okay problem but its score should be like 1250 or at most 1500, not 1750 D seems a non-sense problem to me and it was guessable, I think since E-F aren't that hard, D should be a harder problem and not guessable to balance the round. E has many details but it's a normal problem and I think its score should have been less than 2750. I think F is easy for "F" and its score should have been less than 3000. I think it is a bit standard problem too.
•  » » 11 days ago, # ^ |   0 what is the trick behind D, it got decent submissions! I couldn't find any pattern.
•  » » » 11 days ago, # ^ |   0 Every new line creates two triangles with each existing line.
•  » » » » 11 days ago, # ^ |   +3 just a clean drawing on a paper can help me lead to the solution?
•  » » » » » 11 days ago, # ^ |   +15 There are three types of line depending on the orientation of the line, so let the number of each be x, y, z. The total number of triangles created by those lines is equal to $2(xy + yz + zx)$ which has to be greater or equal to n. To minimize the sum x + y + z, the difference between x, y, z has to be minimized (I think you can prove it via fixing one of the values), so the triplet should be in a form of (x, x, x), (x, x, x-1), or (x, x-1, x-1). Hope this makes sense
•  » » » » » » 11 days ago, # ^ |   0 sum i.e (a + b + c) would yield maximum value only when their absolute difference is minimum right i.e just do (a + b + c)/3 and distribute the remainders among them! But how I would reach the conclusion that our total number of triangles is 2(a*b + b*c + c*a)? Can you give me some thinking approach?
•  » » » » » » » 11 days ago, # ^ |   +10 Consider the intersections of these three types of lines. It is easy to see that if two lines are of different types, they will intersect as they are not parallel, and also each intersection of two lines creates two triangles. Now you might wonder what would happen if three lines intersect at the same hexagon. You can consider it as three separate intersections that each contribute two triangles, making in total 6 triangles, so we can count the number triangles as two times the number of pairs of lines that are from different types, thus, $2(xy + yz + zx)$.
•  » » » » » » » » 11 days ago, # ^ |   +1 Man you are awesome. Loved the approach!
•  » » » » » 11 days ago, # ^ |   +9 Well I used the given image and Paint. That works too.
•  » » 11 days ago, # ^ |   +39 If you think "A problem has too many details", then you may solve it in a wrong way.
•  » » » 11 days ago, # ^ |   +5 I said "B" has many details not "A".
•  » » » » 11 days ago, # ^ |   0 I said "One" not "The first".
•  » » » » » 11 days ago, # ^ |   +8 Oh Okay, I meant details in the statement not in the solution.My opinion is "B" and "A" problems should have little details in the statement and be simple. For example the easy problems in "ARC" has difficulty like div2A,B but they're simple in their statement.
•  » » » 11 days ago, # ^ | ← Rev. 2 →   +36 He has a point. The statement is way too long and can be simplifed. The entire part about special characters is useless and can be replaced by giving input as a binary string instead. Probably shorter way to write the statementYou are given a binary string $s$ of length $n$.In one operation you will perform the following: let $t$ be an empty string for all positions $1 \leq i \leq |s|$, append $s_i$ to $t$ if $i=|s|$ or $s_{i+1} = \texttt{1}$ replace $s$ with $t$ How many distinct binary strings can be made by performing the operation some times?
•  » » 11 days ago, # ^ |   +23 E surely doesn't have much details.
•  » » » 11 days ago, # ^ |   +9 It has details in the statement, I mean many things got mixed together and then we have this problem.For example, nodes have weight and edges also have weights, A path can start at a node and ends at an edge and also it can end at a node.I'm not against that type of problems but I just like the problems to be more natural.
•  » » 11 days ago, # ^ |   +17 +1 to every point
•  » » 10 days ago, # ^ |   +1 Is the technique used for solving F pretty well known? I couldn't get the part where they are generating bits and maintaining a difference as they go over each bit position. Can someone explain what they (almost all solvers?) are trying to do?
•  » » 7 days ago, # ^ |   0 Mr_Solution If C is a bit standard problem, Where can I find/practice those types of problems?
 » 11 days ago, # |   +3 They should have kept round 786 on Eid ;)
 » 11 days ago, # |   +7 What an amazing Round Thank you to all the Problem Setters and Testers
•  » » 11 days ago, # ^ |   +16 Your account seems suspicious. How you were only solving one to two problems in Div2 and in matter of days you are solving 5 problems today. You should be reported.
•  » » » 11 days ago, # ^ |   -24 Does that make any sense ? I solved all on my own or is it a preassumption a newbie cannot do problems beyond Div2 A.
•  » » » » 11 days ago, # ^ |   +5 Ohkk so what happened in last Div3 and Div2 rounds
•  » » » » » 11 days ago, # ^ |   0 Ran out of brain if that is what makes you feel better
•  » » » » » » 11 days ago, # ^ |   +2 Ran out of brain in 5 consecutive contests. Common that doesn't happen to anyone, just accept it.
•  » » » » » » » 11 days ago, # ^ |   -15 @Mike will decide who is and who is not
•  » » » » 11 days ago, # ^ |   +21 Obviously You are a cheater buddy
•  » » » » » 11 days ago, # ^ |   +6 sus
•  » » 10 days ago, # ^ | ← Rev. 4 →   +6 Ok let me tell you something. If you can't solve more than 3 problems on Div3, how tf do you expect us to believe you solved today dive2 D,E. They are like 1800+ rating problems. Only a newbie(like you described yourself) would not know how unlikely this is.People like you are what ruining Codeforces. Keep this up, and Indians will have cheating reputation and no one would believe us. I already start hearing complain about Indians mass cheating during interview and programming contest. This would make it much harder to get jobs in India or in the US(I'm sure people wouldn't tell this to our face, but we will face more scrutiny)I'd imagine IITers know better, but apparently it seems like it'd make it even easier for you to cheat since you could pass around solutions among your peers.
•  » » » 10 days ago, # ^ |   0 Your expectations are none of my business but you have no right to accuse me without proof . You have around 250 subs for E tell me one which matches with my submission
•  » » » » 10 days ago, # ^ |   +6 cheaters stink
•  » » » » » 10 days ago, # ^ |   0 "Some people are mad because you're not suffering the way they expected you to do"
•  » » » » 10 days ago, # ^ |   +5 So how can you AC E even faster than you AC C ? It is nonsense
•  » » » » » 10 days ago, # ^ | ← Rev. 2 →   0 Hey if someone is doing nonsense things it is you First of all in C I forgot to add if child == parent then continue which meant infinite loop and my VS code where my code hanged afterwards so i had to restart wasted around 10-15 minutes there , then i got WA answer so i decided to go for a slight different approach although i preserved the original components Btw a almost 80% similar problem appeared in one of LATOKEN rounds last year so it isn’t a completely new problem E problem is fairly simple if one you assign 2^p to root node it isn’t that hard and a standard problem Btw who you are to talk about me when you yourself in your life only gave 1 contest
•  » » » » » 9 days ago, # ^ |   0 Solved 4 again . What would you say now ?Get lost and hope someone taught in your childhood that bullying is bad Hope you never go through this experience again
•  » » » 10 days ago, # ^ |   0 very true , some strict step must be taken against such cheaters otherwise they will make honest ppl suffer .
 » 11 days ago, # |   +9 In problem D, I figure out that drawing lines gives you {+0, +2, +4, +4, +6, +8, +8, +10, +12, +12, +14, ...} more equilateral triangles. With this pattern, it is easy to binary search the minimum number of lines needed to make at least n equilateral triangles.
•  » » 11 days ago, # ^ |   +3 ohh noice ! i have a differnt approach for D!! as we can see there are only 3 differnt slopes of the lines possible and any two lines with different slopes will intersect for sure hence every two lines with different slopes will intersect and will give rise to 2 equilateral triangles ,now its not dificult to see that if i have x lines then i should make lines with differnt slopes in such a way that differnce between there fequency is as small as possible to maximize the intersections and thus triangles ... with this i moved forward , precomputed all the required values and then its just lower_bound!
•  » » 10 days ago, # ^ |   0 oeis may help you
 » 11 days ago, # |   -15 Weak Pretests in Question BGot TLE on TC29 in system testing. What a waste!!
 » 11 days ago, # |   0 my python code for Q4 was giving TLE but it was only O(1). Can someone tell me what’s the problem?
•  » » 11 days ago, # ^ |   0 Slow input/output, Trying using a fast i/o template.
 » 11 days ago, # | ← Rev. 2 →   +10 156110044 is it anti-anti-cheat approach? :D
•  » » 11 days ago, # ^ |   0 A wise man, xQc once said "Cheeto"
 » 11 days ago, # | ← Rev. 2 →   +43 Earlier I noticed just how many people got TLE on problem B at test 29.Turns out that test 29 was actually my test...Sorry guys :(
•  » » 10 days ago, # ^ |   0 s.. sir...
 » 11 days ago, # |   0 what is the logic for problem A ?
•  » » 11 days ago, # ^ |   0 Move all the negative sign to the left
•  » » » 10 days ago, # ^ |   0 Okay got it thanks
 » 11 days ago, # |   +11 Just realized that I got WA in problem C cause i forgot to mod the answer by 10^9+7 :')
 » 11 days ago, # |   0 What is wrong with problem B in the second testcase? I am not able to read the input.
 » 10 days ago, # |   +73 To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!
 » 10 days ago, # |   0 https://codeforces.cc/contest/1670/submission/156220559 This is submission link of my code for B problem . Why i am Getting TLE in this solution? Can anyone tell me.
•  » » 9 days ago, # ^ |   0 You should use fast I/O code to get input\output faster.. put the fast I/O lines in your main function before getting any input. Example :int main(){ std::ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); \\your_code } 
•  » » » 9 days ago, # ^ |   0 Thanks It works learned New Concept!!!!!!
 » 9 days ago, # |   0 I'm curious what is the rejected problem is. Maybe revealing it after this contest end is nice.
 » 9 days ago, # | ← Rev. 2 →   0 Hi, I have been accused of cheating on problem B of this round. It doesn't make any sense because it was a trivial solution. I do see that the people mentioned do have similar solutions (one of them has even contacted me a few minutes back), but since it's just one line of code that gives the solution and the chance of that being similar is fairly high. Is there anything I could do to reverse this? There are no "pre-published" resources, but I request you to take a look this verdict once again.Thanks.
 » 9 days ago, # |   0 Hi, I have been accused of cheating on problem B of this round. It doesn't make any sense because it was a trivial solution. I do see that the people mentioned do have similar solution , but since it's just one line of code that gives the solution and the chance of that being similar is fairly high. Is there anything I could do to reverse this? There are no "pre-published" resources, but I request you to take a look this verdict once again.Thanks.